什么是哈希表哈希表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: vectorlistint table_; // 底层结构数组 链表 size_t useBucketNum_; // 记录已使用的桶数量 double loadFactor_; // 装载因子阈值行业标准 0.75 // 素数表使用素数作为桶大小能让哈希分布更均匀减少冲突 const vectorint 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_castdouble(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_]; vectorlistint 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) 。3Swap 优化扩容时通过 swap 交换新旧表的底层指针避免了内存深拷贝。