用c++写一个简单哈希表

什么是哈希表？
哈希表（Hash Table）是一种空间换时间的极致体现。
它的核心思想是映射。通过一个哈希函数，把数据的键（Key）直接转换成数组的下标。
理想情况：你想找数据，直接用函数算出下标，一步到位，时间复杂度直接降到 O(1)常数时间
现实挑战（哈希冲突）：因为数组空间是有限的，不同的 Key 经过哈希函数计算后，可能会得到相同的下标。这就叫哈希冲突（Hash Collision）。如何解决冲突？
业界最经典、最常用的方案是链地址法（也叫拉链法）。
它的结构是：数组 + 链表。
数组的每个位置（称为“桶”）存放一个链表的头指针。如果多个 Key 算出了相同的下标，它们就会像火车车厢一样，挂在同一个桶的链表上。
C++ 实现：手写一个链式哈希表
下面我用 C++ 为你手搓一个支持自动扩容、素数桶优化的链式哈希表。为了让你能直接运行，我们以最基础的整数键值对为例：

#include <iostream> #include <vector> #include <list> #include <algorithm> // 用于 std::find using namespace std; class HashTable { private: vector<list<int>> table_; // 底层结构：数组 + 链表 size_t useBucketNum_; // 记录已使用的桶数量 double loadFactor_; // 装载因子阈值（行业标准 0.75） // 素数表：使用素数作为桶大小，能让哈希分布更均匀，减少冲突 const vector<int> primes_ = {53, 97, 193, 389, 769, 1543, 3079, 6151}; size_t primeIdx_ = 0; public: // 构造函数 HashTable(int size = 53, double loadFactor = 0.75) : useBucketNum_(0), loadFactor_(loadFactor) { // 选择大于等于用户指定大小的最小素数 for (; primeIdx_ < primes_.size(); ++primeIdx_) { if (primes_[primeIdx_] >= size) break; } if (primeIdx_ == primes_.size()) primeIdx_--; table_.resize(primes_[primeIdx_]); } // 插入元素 void insert(int key) { // 1. 检查装载因子，决定是否扩容 double factor = static_cast<double>(useBucketNum_) / table_.size(); if (factor > loadFactor_) expand(); // 2. 计算哈希下标 int idx = key % table_.size(); // 3. 检查是否已存在，避免重复插入 auto& bucket = table_[idx]; auto it = find(bucket.begin(), bucket.end(), key); if (it == bucket.end()) { if (bucket.empty()) useBucketNum_++; bucket.emplace_front(key); // 头插法，效率极高 O(1) } } // 查找元素 bool find(int key) { int idx = key % table_.size(); auto& bucket = table_[idx]; return find(bucket.begin(), bucket.end(), key) != bucket.end(); } // 删除元素 void erase(int key) { int idx = key % table_.size(); auto& bucket = table_[idx]; auto it = find(bucket.begin(), bucket.end(), key); if (it != bucket.end()) { bucket.erase(it); if (bucket.empty()) useBucketNum_--; } } private: // 扩容 + 重新哈希（核心） void expand() { if (primeIdx_ + 1 >= primes_.size()) return; // 已达最大容量 primeIdx_++; size_t newSize = primes_[primeIdx_]; vector<list<int>> oldTable; table_.swap(oldTable); // 高效交换，避免深拷贝开销 table_.resize(newSize); useBucketNum_ = 0; // 将旧数据重新哈希到新表 for (auto& bucket : oldTable) { for (int key : bucket) { insert(key); } } } }; // 简单测试 int main() { HashTable ht(10); ht.insert(10); ht.insert(63); // 63 % 53 = 10，与 10 冲突，挂在同一个链表 cout << "查找 63: " << (ht.find(63) ? "存在" : "不存在") << endl; ht.erase(10); cout << "删除后查找 10: " << (ht.find(10) ? "存在" : "不存在") << endl; return 0; }

代码中有以下模块：

1：自动扩容与素数表：当表中元素太多（装载因子超过 0.75）时，会自动扩容。并且扩容时，容量不是随便乘 2，而是取下一个素数。这在数学上能最大程度打散数据，减少哈希冲突。

2：头插法：发生冲突时，新元素直接插在链表头部（emplace_front），不需要遍历到尾部，插入操作依然是 O(1) 。
3：Swap 优化：扩容时，通过 swap 交换新旧表的底层指针，避免了内存深拷贝。