#include <iostream>
#include <vector>
#include <list>
using namespace std;

class HashTable {
private:
    vector<list<int>> table;   // 底层：每个桶是一个链表
    int numElements;           // 当前哈希表中的元素个数
    int capacity;              // 桶的数量（数组长度）
    const double LOAD_FACTOR_THRESHOLD = 0.75;  // 负载因子阈值

    // 哈希函数：将键映射为桶下标
    int hashFunction(int key) {
        // 假设 key 为非负，取模得到下标
        return key % capacity;
    }

    // 重新哈希：当负载因子超标时调用
    void rehash() {
        int oldCapacity = capacity;                  // 保存旧容量
        capacity = capacity * 2;                     // 通常翻倍
        // 实际工程中建议找下一个质数，此处简化直接翻倍
        vector<list<int>> oldTable = move(table);    // 转移旧表资源
        table.resize(capacity);                      // 重置新表，所有桶为空
        numElements = 0;                             // 重置计数器，插入时会重新增加
        // 遍历旧表的每个桶，重新插入所有键
        for (int i = 0; i < oldCapacity; ++i) {
            for (int key : oldTable[i]) {
                insert(key);   // 调用 insert，它可能会再次检查负载因子，但此时元素少不会触发
            }
        }
    }

public:
    // 构造函数，初始容量设为7（质数），numElements 为0
    HashTable(int initialCapacity = 7) : capacity(initialCapacity), numElements(0) {
        table.resize(capacity);   // 表初始化为 capacity 个空链表
    }

    // 插入键
    void insert(int key) {
        // 检查负载因子，达到阈值则扩容
        if ((double)numElements / capacity >= LOAD_FACTOR_THRESHOLD) {
            rehash();
        }
        int index = hashFunction(key);    // 计算桶下标
        // 检查该桶中是否已存在该键（避免重复）
        for (int k : table[index]) {
            if (k == key) return;        // 已存在，不插入
        }
        table[index].push_back(key);     // 插入链表尾部
        numElements++;                   // 元素个数加1
    }

    // 查找键：返回 true 表示找到，false 表示不存在
    bool search(int key) {
        int index = hashFunction(key);
        for (int k : table[index]) {
            if (k == key) return true;
        }
        return false;
    }

    // 删除键：成功删除返回 true，不存在则返回 false
    bool remove(int key) {
        int index = hashFunction(key);
        // 遍历链表查找
        for (auto it = table[index].begin(); it != table[index].end(); ++it) {
            if (*it == key) {
                table[index].erase(it);  // 删除该节点
                numElements--;           // 元素个数减1
                return true;
            }
        }
        return false;
    }

    // 打印哈希表的内容（用于调试）
    void print() {
        for (int i = 0; i < capacity; ++i) {
            cout << "桶 " << i << ": ";
            for (int k : table[i]) {
                cout << k << " ";
            }
            cout << endl;
        }
    }

    // 返回当前元素个数
    int size() { return numElements; }
};

// 测试函数
int main() {
    HashTable ht;   // 默认容量7
    // 插入 0, 3, 6, 9, ..., 57 共20个元素
    for (int i = 0; i < 20; ++i) {
        ht.insert(i * 3);
    }
    cout << "元素个数: " << ht.size() << endl;
    cout << "哈希表内容（可能已扩容）:" << endl;
    ht.print();

    cout << "\n查找 30: " << (ht.search(30) ? "找到" : "未找到") << endl;
    ht.remove(30);
    cout << "删除 30 后查找 30: " << (ht.search(30) ? "找到" : "未找到") << endl;
    return 0;
}

class HashTable:
    def __init__(self, initial_capacity=7):
        self.capacity = initial_capacity          # 桶的数量
        self.table = [[] for _ in range(self.capacity)]  # 每个桶是一个列表
        self.num_elements = 0                     # 当前元素个数
        self.threshold = 0.75                     # 负载因子阈值

    # 哈希函数
    def _hash(self, key):
        return key % self.capacity

    # 重新哈希（扩容）
    def _rehash(self):
        old_capacity = self.capacity
        old_table = self.table                     # 保存旧表
        self.capacity = self.capacity * 2          # 容量翻倍
        self.table = [[] for _ in range(self.capacity)]  # 新表
        self.num_elements = 0                      # 重置计数器
        # 遍历旧表每个桶，重新插入所有键
        for bucket in old_table:
            for key in bucket:
                self.insert(key)  # 注意：insert会再次检查负载，但此时元素少，不会触发rehash

    # 插入键
    def insert(self, key):
        # 检查负载因子
        if self.num_elements / self.capacity >= self.threshold:
            self._rehash()
        index = self._hash(key)
        # 避免重复插入
        if key not in self.table[index]:
            self.table[index].append(key)
            self.num_elements += 1

    # 查找键
    def search(self, key):
        index = self._hash(key)
        return key in self.table[index]

    # 删除键
    def remove(self, key):
        index = self._hash(key)
        if key in self.table[index]:
            self.table[index].remove(key)
            self.num_elements -= 1
            return True
        return False

    # 打印哈希表
    def print_table(self):
        for i, bucket in enumerate(self.table):
            print(f"桶 {i}: {bucket}")

    # 返回元素个数
    def size(self):
        return self.num_elements

# 测试
ht = HashTable()
for i in range(20):
    ht.insert(i * 3)   # 插入 0,3,6,...,57

print("元素个数:", ht.size())
print("哈希表内容（可能已扩容）:")
ht.print_table()

print("\n查找 30:", "找到" if ht.search(30) else "未找到")
ht.remove(30)
print("删除 30 后查找 30:", "找到" if ht.search(30) else "未找到")