我一直觉得哈希表是那种看起来特别简单、一旦自己动手却很容易翻车的数据结构。数组按下标访问是 O(1)哈希表把任意键转换成下标思路也不难可一旦牵扯到冲突处理、扩容策略、哈希函数设计很多教程都轻描淡写地略过了。这篇文章我就用 C 从零实现一个泛型哈希表并且把实现过程中真正踩过的坑、做过的取舍一并讲清楚。无论你是刚学 C 的新手还是准备面试想深挖底层原理还是工作中偶尔要写自定义容器这篇内容都值得花十分钟看完。1. 为什么数组这么好用大家还要哈希表散列的本质是空间换时间1.1 数组的下标是天然哈希直接寻址的局限要理解哈希表先看数组。数组之所以快是因为它把「下标」直接当成了地址偏移量arr[i]就是arr i一次加减法和一次访存所以是 O(1)。但数组有个硬伤下标必须是非负整数而且为了 O(1) 访问必须开出从 0 到最大下标之间的全部空间。假设你的键是英文单词字符串总共有几十万个可能但你实际只存了百来个词难道要为每个可能的字符串都分配一个数组位置显然不现实。哈希表的核心思路就是设计一个哈希函数把任意类型的键整数、字符串、结构体映射成一个整数再对这个整数取模得到桶的下标。桶的数量比实际元素的数量大得多所以元素能均匀散落在不同的桶里。代价是内存占用比直接顺序存储高这就是所谓的空间换时间。数组是「下标即键」哈希表是「键经过计算得到下标」本质思想一脉相承。1.2 均匀性、确定性与雪崩效应哈希函数的质量直接决定哈希表的生死。它必须满足两个最基本的性质确定性同一个键无论调用多少次哈希值必须一样。均匀性不同键的哈希值应该尽量分散避免大量键挤进同一个桶。打个比方电话簿按姓氏的首字母分成 26 个组A 组、B 组、C 组……这种分法也算哈希但姓氏 Z 开头的很少S 开头的可能特别多分布不够均匀。更极端的例子是如果你用字符串的长度当哈希值那 cat 和 dog 都会落在长度为 3 的桶里桶内链表越来越长查找越来越慢。C 的std::hashint通常直接把整数本身作为哈希值取值已经很均匀std::hashstd::string则会做一轮字节混合。对于自己定义的结构体往往需要手动组合多个字段的哈希值最好用一个经典的哈希组合函数比如h h * 131 field_hash这类带权重的方式避免不同字段相同组合导致的碰撞。1.3 冲突不是 Bug而是一种必然有人会问如果设计一个足够好的哈希函数是不是就能让每个键都对应一个不同的桶答案是不能。因为桶的数量总是有限的而键可以来自一个远大于桶数量的空间。根据鸽巢原理如果 n1 只鸽子放进 n 个笼子至少有一个笼子有两只鸽子。哈希函数把无限可能性的键压缩到有限个桶里冲突就是数学上的必然任何哈希函数都无法避免。所以哈希表真正的设计重点从来都不是「消灭冲突」而是「冲突发生之后怎么高效处理」。后面我会详细对比两种主流冲突处理方案。2. 动手写之前先想清楚这四个设计决策写代码之前不把设计决策定下来写到一半就会反复推翻。我自己第一次手写哈希表时就是边写边改结果代码越改越乱。后来我总结出开始写之前至少要拍板四件事。2.1 冲突处理选链地址法而不是开放定址法主流方案有两大类链地址法每个桶保存一条链表或一棵树插入时先定位到桶再在链表里追加节点。开放定址法冲突时按某种探测序列线性探测、二次探测去找下一个空闲位置。我这次选择链地址法原因有三个删除简单。链地址法删除就是链表节点删除不需要额外标记。而开放定址法删除被占用的槽位时不能直接置空否则会切断后续探测的链条必须引入「墓碑」标记实现复杂度立刻上了一个台阶。对装载因子更宽容。开放定址法为了保证探测效率装载因子通常要控制在 0.5 到 0.7 以内链地址法则可以容忍 1.0 甚至更高因为即使有冲突链表通常很短。实现更符合人体直觉。链地址法用「桶数组 链表节点」的物理结构每一步操作都能在脑海里画出内存图。当然链地址法也有缺点节点是分散分配的CPU 缓存命中率不如开放定址法每个节点还要多存一个 next 指针。这个代价在大多数场景下可以接受。2.2 哈希函数怎么来std::hash 不够用时自己写C 标准库提供了std::hash对整型、浮点、指针、std::string等类型有默认实现。所以我的类模板可以直接这样声明template typename Key, typename Value, typename Hash std::hashKey class HashTable;第三个模板参数就是哈希仿函数类型默认用std::hashKey。这样内置类型和字符串开箱即用。但如果键是自定义结构体比如二维坐标点struct Point { int x; int y; bool operator(const Point other) const { return x other.x y other.y; } };std::hashPoint是没有特化的直接编译会报错。你需要自己写一个仿函数struct PointHash { size_t operator()(const Point p) const { size_t h std::hashint()(p.x); // 经典哈希组合加入第二个字段时用黄金比例相关的常数错开 h ^ std::hashint()(p.y) 0x9e3779b9 (h 6) (h 2); return h; } };这个0x9e3779b9是黄金分割比例对应 32 位精度的值在 Boost 的hash_combine等库函数里被广泛使用能有效打散两个字段的排列组合。这里有个最容易踩的坑operator判断相等的两个对象哈希函数必须也返回相同的哈希值。否则你在哈希表里插入了键 A用与 A 相等但哈希不同的键 B 去查找会定位到另一个桶自然什么都找不到。2.3 装载因子与扩容时机0.75 这个经验值装载因子定义为装载因子 α 元素个数 / 桶的数量α 越大桶越满链表越长查找性能越差。链地址法虽然容忍 α 1但也不能无限增长。通常 C 实践里取 0.75 作为扩容阈值这是一个空间和时间的折中空间利用率不算太低平均链表长度也不至于太长。当插入一个元素后如果size_ bucketCount_ * 3 / 4就触发扩容。我采用的扩容策略是桶数量直接翻倍rehash(bucketCount_ * 2)。扩容不是简单地把数组变大因为桶数量变了原来所有元素所在的桶下标都变了。比如原来有 8 个桶键 17 落到桶 117 % 8扩容到 16 个桶后17 应该落到桶 117 % 16看起来没变但键 25 原来在桶 1现在应该落到桶 9。所以必须把每个已有节点重新计算哈希值放到新桶里。扩容的代价是 O(n)把 n 个元素全部重新散列一次。但因为我们采用翻倍策略均摊下来每次插入只需 O(1) 的扩容成本所以整体性能依然是 O(1) 级别的。2.4 键的不可变性与相等语义哈希表里键一旦插入绝对不能再修改。原因很直观如果你把键从Point{1, 2}改成了Point{3, 4}但它在桶里的位置还是按(1,2)的哈希值算出来的那么用(3,4)去查就会走错桶。所以在类的公开接口里我只暴露find返回的是Value*外部可以修改值但永远拿不到键的引用。内部节点里 key 虽然是普通成员但我不会提供任何修改它的途径。相等语义也一样operator必须严格对应哈希函数覆盖的字段。哈希函数可以用多个字段组合但千万不要只取其中一部分来做哈希另一部分只在operator里判断。否则两个对象成立但哈希值不同哈希表会直接失去正确性。3. 从空表到可用的泛型哈希表完整实现与关键代码注释设计决策定了我们直接写代码。这里给出一个可用于教学和生产参考的HashTable类完整的核心代码我会拆成几段并逐段解释。3.1 类骨架与节点设计底层用一个 bucket 数组每个 bucket 是一条单链表。链表节点结构如下#include cstddef #include functional #include utility template typename Key, typename Value, typename Hash std::hashKey class HashTable { public: explicit HashTable(size_t bucketCount 16) : bucketCount_(bucketCount), buckets_(new Bucket[bucketCount]()), size_(0), hash_() {} ~HashTable() { clear(); delete[] buckets_; } HashTable(const HashTable) delete; HashTable operator(const HashTable) delete; HashTable(HashTable other) noexcept : bucketCount_(other.bucketCount_), buckets_(other.buckets_), size_(other.size_), hash_(std::move(other.hash_)) { other.bucketCount_ 0; other.buckets_ nullptr; other.size_ 0; } HashTable operator(HashTable other) noexcept { if (this ! other) { clear(); delete[] buckets_; bucketCount_ other.bucketCount_; buckets_ other.buckets_; size_ other.size_; hash_ std::move(other.hash_); other.bucketCount_ 0; other.buckets_ nullptr; other.size_ 0; } return *this; } private: struct Node { Key key; Value value; Node* next; Node(const Key k, const Value v, Node* n) : key(k), value(v), next(n) {} }; struct Bucket { Node* head; Bucket() : head(nullptr) {} }; size_t bucketCount_; Bucket* buckets_; size_t size_; Hash hash_; size_t hashKey(const Key key) const { return hash_(key) % bucketCount_; } };为什么用裸指针加手动管理因为「自我实现」的重点就是要能理解内存归属。每个节点的生命周期由哈希表独占析构时逐个释放不会出现共享所有权的问题。拷贝构造和拷贝赋值我直接禁止了只保留移动构造和移动赋值理由放到后面讲。3.2 插入、查找、删除三个核心操作的实现细节先看插入和查找public: void insert(const Key key, const Value value) { size_t index hashKey(key); Node* node buckets_[index].head; while (node) { if (node-key key) { node-value value; // 键已存在更新值 return; } node node-next; } Node* newNode new Node(key, value, buckets_[index].head); buckets_[index].head newNode; size_; // 超过装载因子阈值扩容 if (size_ bucketCount_ * 3 / 4) { rehash(bucketCount_ * 2); } } Value* find(const Key key) { size_t index hashKey(key); Node* node buckets_[index].head; while (node) { if (node-key key) { return node-value; } node node-next; } return nullptr; } const Value* find(const Key key) const { size_t index hashKey(key); Node* node buckets_[index].head; while (node) { if (node-key key) { return node-value; } node node-next; } return nullptr; }插入时先在对应桶的链表里线性查找。如果键已经存在我选择直接更新 value如果你希望和std::unordered_map::insert一样「已存在则不插入」可以把更新那一行改成返回 false逻辑也很简单。新节点用头插法插入链表。头插的好处是 O(1) 且不需要额外记录尾节点。对于哈希表操作链表的元素顺序本来就无所谓。删除用双指针技巧避免了记录前驱节点bool erase(const Key key) { size_t index hashKey(key); Node** pp buckets_[index].head; while (*pp) { if ((*pp)-key key) { Node* toDelete *pp; *pp toDelete-next; delete toDelete; --size_; return true; } pp (*pp)-next; } return false; }这里pp是一个指向Node*的指针。每次移动它时它指向的是上一个节点的 next 成员的地址。删除时直接把*pp改成下一个节点前驱和后继就自然连上了。这是写链表删除最不容易出错的方式比维护prev变量干净得多。3.3 扩容与重哈希移动节点而不是重新分配扩容实现如下private: void rehash(size_t newBucketCount) { Bucket* newBuckets new Bucket[newBucketCount](); for (size_t i 0; i bucketCount_; i) { Node* node buckets_[i].head; while (node) { Node* next node-next; size_t newIndex hash_(node-key) % newBucketCount; node-next newBuckets[newIndex].head; newBuckets[newIndex].head node; node next; } } delete[] buckets_; buckets_ newBuckets; bucketCount_ newBucketCount; }注意一个关键点我重哈希时并没有new出来新的节点而是把旧节点直接从旧桶里摘下来挂到新桶里。这样既省了一次内存分配又保证了指针指向的节点仍在使用只是它的 next 指针被重新连接了。重哈希后size_ 不变不需要调整。由于新桶数量翻倍所有节点重新散列后分布自然更稀疏平均链表长度减半。3.4 拷贝、移动与析构选择 move-only 的权衡上面代码里我删除了拷贝构造和拷贝赋值。为什么不实现深拷贝因为裸指针类实现拷贝不是不行而是额外代码量不小而且容易写错异常安全。如果每个节点都用new Node(cur-key, cur-value, nullptr)深拷贝理论上没有问题但拷贝构造需要逐桶复制链表移动构造则只需要搬走成员指针。对于一个教学核心来说提供移动语义已经足够展示现代 C 的资源管理思路。实际工程里如果要给HashTable增加拷贝我建议实现一个私有copyFrom方法遍历源表每个桶的链表逐个节点复制到新桶中保持桶数量一致即可。有一点要注意拷贝时必须为每个新节点分配内存如果中途抛出bad_alloc需要清理已复制的部分否则会内存泄漏。这也是裸指针容器最容易出的异常安全bug。析构函数调用clear()然后delete[] buckets_逻辑清楚void clear() { for (size_t i 0; i bucketCount_; i) { Node* node buckets_[i].head; while (node) { Node* next node-next; delete node; node next; } buckets_[i].head nullptr; } size_ 0; } size_t size() const { return size_; } bool empty() const { return size_ 0; }move 之后源对象的bucketCount_设为 0buckets_设为nullptr。析构函数的clear()对bucketCount_为 0 的表来说循环不会执行delete[] nullptr也是安全的不会崩溃。4. 把哈希表用坏功能测试、退化场景与性能观察代码写完不算完必须真的拿数据去测。我习惯从三个层次验证最基本的正确性、刻意制造的恶意场景、以及和标准库的对比。4.1 基本功能用例与边界测试先用一个小例子把增删查全部跑一遍#include iostream #include string int main() { HashTablestd::string, int table; table.insert(apple, 3); table.insert(banana, 5); table.insert(cherry, 7); if (int* v table.find(apple)) { std::cout apple - *v \n; } table.insert(apple, 30); // 更新已有键 std::cout apple - *table.find(apple) \n; std::cout erase banana: table.erase(banana) \n; std::cout erase banana again: table.erase(banana) \n; std::cout size table.size() \n; return 0; }边界用例至少要多测这几项空表删除不存在的键返回 false不崩溃。插入一个键后立即查找能拿到正确的 value。扩容之后之前插入的所有键都还能被查找到。连续删除到空表size 归零再插入仍然正常。很多人写哈希表最大隐患就是扩容后忘了重新散列导致扩容前的键查不到。我在 rehash 里通过遍历旧桶重新计算下标这种问题就不会出现。4.2 恶意制造冲突当一万个元素挤进同一个桶哈希表最怕哈希函数退化成常数。测试一下struct AlwaysZeroHash { size_t operator()(const int) const { return 0; } }; HashTableint, int, AlwaysZeroHash badTable; for (int i 0; i 10000; i) { badTable.insert(i, i); }这个表的所有元素都在桶 0 的一条链表上查找第 9999 个元素需要遍历 9999 个节点。复杂度从 O(1) 退化成了 O(n)。用它做 10 万次find耗时能明显感觉到卡顿。这个测试说明哈希函数均匀性强不强不是玄学而是直接落到性能上的。实际开发里很少会遇到故意返回 0 的哈希函数但很容易遇到「哈希值分布不均匀」的情况比如 String 的哈希实现只取字符的后几位或者自定义结构体的哈希组合写得不好。4.3 和 std::unordered_map 的简单对比我把自己的 HashTable 和std::unordered_map放在同一批随机数据下对比。插入 100 万个整数键然后随机查找 100 万次。在我的测试环境里标准库大约比自实现快 30% 到 50%。差距来自几个方面标准库的 bucket 通常做得更精细扩容阈值和桶数量计算更优化。标准库对节点分配做了内存池化减少了 malloc 次数。我在插入时使用头插法查找是遍历链表标准库可能根据装载因子调整桶大小。取模运算本身也有成本标准库会尝试用位运算优化桶索引计算当桶数量是 2 的幂时。不过差距并没有到数量级的程度说明自实现的基本思路是对的。如果你在面试中被问到哈希表能够亲手实现并分析性能差异这个点是很加分的。4.4 一个隐藏问题遍历时扩容会让你的迭代器失效我这份实现没有提供迭代器但如果你在遍历过程中插入了大量元素导致触发 rehash就会遇到迭代器失效。原因很简单rehash 时旧节点被移动到新桶节点的 next 指针被重新赋值原来保存的桶地址可能已经不再指向有效链表。标准库的unordered_map也有类似的失效规则。所以不管用标准库还是自实现遍历时尽量避免插入可能触发扩容的操作如果一定要边遍历边插入可以先记录需要的键值等遍历结束后再统一插入。5. 自己写哈希表值不值常见误区和几条实战建议写了这么多回到一个务实的问题既然std::unordered_map现成的就能用为什么要自己写我的看法是写一遍的价值不在产出成品而在于把几个概念彻底搞清楚。5.1 自定义 key 时哈希与相等必须同步这是我见过最多的真实翻车现场。有人写了一个结构体struct User { int id; std::string name; bool operator(const User u) const { return id u.id; } };他只用id判断相等但在哈希函数里把id和name全部算进去了。结果两个 User 分别叫 a 和 bid 都是 100按operator是同一个用户但因为 name 不同哈希值也不同。第二个insert居然能成功放进去表里出现两个相等的键后续find和erase行为彻底混乱。正确做法是operator里用到哪些字段哈希函数里就必须覆盖哪些字段反过来哈希函数覆盖了额外字段operator却不能忽略它们。保持同步是哈希表正确性的基础。5.2 什么时候真的需要自己实现哈希表虽然标准库足够好但我遇到下面几种情况时会倾向自己写需要在固定大小的哈希表里工作不允许扩容。比如嵌入式环境内存紧张预分配好 bucket用开放定址法实现一个紧凑映射。需要定制哈希语义。比如一致性哈希、按地理位置分片这类哈希不是简单的键到桶而是需要「键到节点」的稳定映射。需要深度控制内存布局。例如把节点连续存储、按 CPU 缓存行对齐来提高缓存命中率这在标准库上难以做到。教学和面试需要。手写哈希表几乎是算法面试保留题目能独立完成并讲清楚扩容、冲突处理才算真正掌握。如果只是普通业务代码std::unordered_map或std::map够用我不建议重复造轮子。但理解底层原理永远不亏。5.3 还可以继续扩展的方向学会了这份基础实现后面有几条路可以走都不难把单链表改成自平衡树解决极端哈希冲突下的退化类似 Java 8 的树化。改用开放定址法加线性探测配合 tombstone 删除标记写一个缓存更友好的变体。增加迭代器支持注意 rehash 时的失效规则。实现真正的深拷贝版本并保证异常安全。使用无锁链地址法往并发哈希表方向探索。我自己写哈希表最大的体会是很多看似「理所当然」的细节比如erase用双指针rehash复用节点装载因子为何取 0.75只有亲手实现一遍才能真正有手感。哪怕你平时只用标准库也强烈建议找个周末下午把这个类完整敲一遍、跑一遍测试再故意制造几个冲突场景看看退化效果。这个过程比读十篇 哈希表原理 的文章都管用。