我最初接触C的时候总觉得哈希表是什么很高深的东西。直到我写了个需要快速查询用户信息的模块用数组吧key不连续根本没法当索引用链表吧几万条数据查一次要等半天用map吧明明知道是红黑树还是O(log n)。后来我认真把从哈希表是什么到手写一个能用的哈希表这条路完整走了一遍才意识到它遍地都是、原理也不难难的是把那些工程细节想明白。这篇内容就按我自己的学习路径来写从原理推导到完整实现再到和标准库的差距最后是实战里那些坑希望对刚入门C的朋友有一点帮助。1. 哈希表到底牛在哪从数组下标到任意键查找1.1 数组的尴尬我明明只需要查一个值先想一个最简单的场景班里50个学生每个学生有一个学号学号从1到50连续排列。这个时候用数组存索引就是学号查一个学生的时间是O(1)完美。但现实哪有这么巧。假设学校一共有10000个学生学号是5位数字而你的班里只有30个学生学号分布得很散。你要是还拿学号当数组下标就得开一个长度10000的数组其中9970个位置是空的。这还不算最糟的——如果key是用户名、是身份证号、是订单号甚至是一串字符串数组下标这个思路直接就没法用了因为数组下标要求的是一个非负整数你总不能拿字符串当下标吧。你当然可以把每个用户按顺序存在数组里然后遍历去找那时间复杂度是O(n)。数据量小还好数据一多就完蛋。链表也一样救人一命的说法是灵活但代价是查找要一个节点一个节点地走。哈希表解决的就是这个问题不管你的key是字符串、数字还是自定义对象只要你能算出一串整数作为它的指纹我就能把这个整数映射到数组的一个位置然后以O(1)的平均复杂度把数据查出来。所以哈希表的本质就是数组和一个神奇的映射函数的结合体。数组负责快速定位函数负责把任意key变成合法的数组下标。1.2 哈希函数把名字变成门牌号的翻译官这个神奇的映射函数就叫哈希函数。它的职责是接收一个key输出一个size_t类型的整数。这个整数通常很大在64位机器上最大能到2^64-1所以我们不能直接拿它当数组下标还得对桶的数量取一次模。比如我定义了一个桶数组长度是1000。key是字符串student_9527哈希函数算出来的值是123456789那我把它放在123456789 % 1000 789这个位置上。以后要查找的时候重新算一遍同样的哈希值再取模直接跳到789这个槽位就找到了。整个过程不管数据量有多大都只做一次哈希计算加一次数组访问。一个合格的哈希函数要满足三个条件确定性同一个key任何时候算出来必须是同一个哈希值。这是哈希表能工作的前提。均匀性不同的key尽量把哈希值散开不要扎堆。扎堆了就会导致冲突冲突多了性能就崩。高效性计算哈希值本身的代价不能太大。如果算个哈希要遍历几个MB的字符串那比直接遍历查找还慢得不偿失。C标准库里提供了std::hashK这个函数对象它对很多内置类型和常见类型都有特化。比如std::hashint对整数的实现通常就是返回这个整数本身或者经过一个位混合std::hashstd::string则会把字符串逐字符处理成一个整数。在入门阶段我们直接用std::hashK{}(key)就行。1.3 冲突两个不同键撞进同一扇门怎么办均匀性只是理想情况现实里两个不同的key算出相同的哈希值、取模后落进同一个桶这种事情一定会发生。比如abc和cba完全可能算出同一个哈希值毕竟哈希函数只是把无限多的key压进有限的范围冲突无法避免。处理冲突有两大流派链地址法每个桶不直接存元素而是存一个链表的头指针。凡是哈希值落进同一个桶的元素就挂在这个链表后面。查找的时候先算出桶下标再走进这个桶对应的链表逐个比较key。这是Cstd::unordered_map采用的方案现代实现为了防攻击还会在链表过长时转成红黑树但那是后话。开放寻址法当发生冲突时不在同一个位置硬挤而是按照某种规则继续往后找空位。比如线性探测位置被占了就去下一个位置看看直到找到空位或者遇到一个标记为已删除的槽位。Python的dict就采用了这个方案。打个比方链地址法就像一栋公寓的信箱墙每家一个信箱。有两封信地址写得有点模糊都投到了同一个信箱那物业就在这个信箱里加了个小隔层两层都给你塞下。开放寻址法则像是停车位被占了之后你在停车场里绕圈找下一个空车位。入门阶段我强烈建议先吃透链地址法因为它思路直白、代码好写也好调试。等把链地址法玩明白了再回头看开放寻址法会容易很多。下面就开始进入实现环节。2. 手写第一版哈希表链地址法是最容易上手的实现2.1 结构设计桶数组加链表先画清楚再写码动手写代码之前先把结构在脑子里画清楚。一个链地址法哈希表由三部分组成一个桶数组类型是std::vectorNode*每个元素是一个链表的头指针。一个节点结构体里面存key、value和指向下一个节点的指针。一个元素计数器记录当前总共存了多少个元素用来判断要不要扩容。模板设计我选择了templatetypename K, typename V这样key和value的类型都可以自由替换写起来更贴近标准库。#include vector #include functional template typename K, typename V class MyHashMap { private: struct Node { K key; V value; Node* next; Node(const K k, const V v) : key(k), value(v), next(nullptr) {} }; std::vectorNode* buckets; size_t elementCount 0; size_t bucketCount 0; float maxLoadFactor 0.75f; size_t hashIndex(const K key) const { return std::hashK{}(key) % bucketCount; } public: explicit MyHashMap(size_t initialBuckets 16) : bucketCount(initialBuckets) { buckets.resize(bucketCount, nullptr); } };这里我初始化了16个桶。hashIndex是核心辅助函数先调用std::hashK算出哈希值再对bucketCount取模得到桶下标。有个细节值得注意bucketCount必须和buckets.size()保持一致否则扩容后hashIndex里的分母就错了。我干脆单独用一个变量存桶数量虽然冗余了点但是扩容时逻辑更清楚。再补充一个点当key是字符串时std::hashstd::string是能直接用的。但如果key是自定义结构体比如一个struct MyKey { string name; int id; };编译器会直接报错因为标准库里没有对MyKey的特化。解决办法是给这个结构体写operator并偏特化std::hash这在后面章节会细讲。2.2 插入与查找的完整实现插入的逻辑一句话总结就是算桶下标在桶的链表里找key。找到了就更新value找不到就头插一个新节点。头插比尾插省事不用遍历到链表末尾而且还省时间。至于顺序问题哈希表本身不承诺有序头插完全没毛病。void insert(const K key, const V value) { // 插入前先判断负载因子超过阈值就扩容 if (static_castfloat(elementCount 1) / bucketCount maxLoadFactor) { rehash(); } size_t index hashIndex(key); Node* current buckets[index]; // 先看链表里有没有这个 key while (current) { if (current-key key) { current-value value; // 已有 key更新 value return; } current current-next; } // 没找到头插新节点 Node* newNode new Node(key, value); newNode-next buckets[index]; buckets[index] newNode; elementCount; }查找的套路和插入的前半段几乎一样bool find(const K key, V value) const { size_t index hashIndex(key); Node* current buckets[index]; while (current) { if (current-key key) { value current-value; return true; } current current-next; } return false; }返回bool而不是直接返回V是因为C没法方便地表达空值。标准库用迭代器指向end()来表示没找到但自制哈希表先返回bool最快的做法。这里我想强调一个容易忽略的点比较链表节点用的是current-key key也就是说我们的哈希表依赖key类型重载了operator。如果key是基本类型没问题如果key是自定义结构体你就得自己写operator。哈希函数负责定位operator负责确认两个缺一不可。定位只能把你带到正确的桶桶里可能有多个不同key必须逐个比key才能确定最终有没有找到。现在很多带引号的哈希表教程只讲哈希函数不讲相等比较导致新手写出来一堆诡异bug这个坑一定要避开。2.3 删除操作的隐藏陷阱删除比插入和查找都麻烦一点因为要维护链表结构。最容易被坑的就是如果要删的是链表的第一个节点头指针得更新如果删的是中间节点前一个节点的 next 得绕过待删节点。一个不容易漏的写法是用二级指针或指向指针的指针可以直接拿到头指针的地址统一处理头删和中间删除bool erase(const K key) { size_t index hashIndex(key); Node** current buckets[index]; while (*current) { if ((*current)-key key) { Node* toDelete *current; *current toDelete-next; // 把当前节点的 next 交给上一个节点的 next delete toDelete; --elementCount; return true; } current ((*current)-next); } return false; }这段代码第一次看可能觉得别扭但它是处理头删最优雅的方式。Node** current指向的是上一个节点里存的next指针的地址初始时就是buckets[index]。当找到目标节点时*current就是当前的节点指针我把它替换成toDelete-next等于直接改了上一个节点的 next 或者桶的头指针不需要区分是不是头节点。不要忘了delete toDelete和--elementCount。在我的第一版实现里就漏了--elementCount结果负载因子越算越小内存逐渐失控。这种小错误平时不炸要到内存和性能出问题了才追悔莫及。我再顺手补一个析构函数否则每个节点new出来没人管就要内存泄漏~MyHashMap() { for (Node* head : buckets) { while (head) { Node* next head-next; delete head; head next; } } }到这里一个能用的哈希表已经成型了。插入、查找、删除都是O(1)平均复杂度。但这只是能用距离能打还差很远。下一节把扩容、负载因子和哈希函数这些真正决定哈希表性能的细节补上。3. 让哈希表真正能打扩容、负载因子与哈希函数选型3.1 负载因子0.75是怎么来的负载因子load factor定义很简单元素个数 / 桶数量。它反映的是桶的拥挤程度。负载因子太高意味着每个桶里挂的链表越来越长查找时链表遍历的成本上升哈希表从O(1)慢慢退化成O(n)。负载因子太低桶大量闲置内存浪费严重性能没有本质提升纯粹是空间换了个寂寞。那取多少合适很多教材张嘴就是0.75这个数字主要来自Java的HashMapC标准库std::unordered_map的默认max_load_factor其实是1.0。0.75和1.0的差异没有想象中那么大核心思想都是别把桶塞得太满。C选择1.0作为默认一个重要原因是链地址法下每个桶多挂一两个节点并不会造成灾难性退化不如省点内存。如果你想更保守自定义时设成0.75也完全合理。插入前我判断的是elementCount 1除以bucketCount为什么加一因为这是插入后的预估状态。如果等插入完发现超标再去扩容新元素已经待在了一个让它违法的桶里还得再移动一次纯属浪费。3.2 rehash扩容这步做不好直接翻车当负载因子超过阈值就得做扩容哈希表里这个动作叫rehash。为什么叫rehash因为桶数量变了所有元素之前算出来的桶下标全部失效。你拿原来的下标访问新数组根本不对位。唯一的办法是把每个元素拿出来用新的桶数量重新算下标再放进新桶里。void rehash() { size_t newBucketCount nextPrime(bucketCount * 2); std::vectorNode* newBuckets(newBucketCount, nullptr); for (Node* head : buckets) { while (head) { Node* next head-next; size_t newIndex std::hashK{}(head-key) % newBucketCount; head-next newBuckets[newIndex]; newBuckets[newIndex] head; head next; } } buckets.swap(newBuckets); bucketCount newBucketCount; }这里有个细节扩容时我复用了原来的Node节点只是把它们的next指针重新串了一遍没有重新new、delete。这一步省了很多时间也避免了不必要的内存分配。所有节点在旧桶数组里被拆下来再按新下标挂到newBuckets上。为什么新桶数量要用质数打个比方如果你的桶数量是162的4次方而你的哈希值恰好是低位相同、高位不同的模式取模的结果就会被“吃”掉高位容易扎堆。质数能缓解这种规律性冲突。当然现代std::hash通常已经对输入做了充分的位混合对2的幂取模问题也没那么大但传统哈希表为了稳妥还是倾向于用质数。那nextPrime怎么实现最省事的写法是预置一个质数表还不够就翻倍再找size_t nextPrime(size_t start) { // 这里为了演示只给一个简版从 start 开始找下一个奇数逐个试除 if (start 2) return 2; if (start % 2 0) start; while (true) { bool isPrime true; for (size_t d 3; d * d start; d 2) { if (start % d 0) { isPrime false; break; } } if (isPrime) return start; start 2; } }rehash的复杂度是O(n)单次看很吓人但均摊到每次插入上其实是O(1)。这就像你出门旅游平时零钱够用偶尔去银行取一次大额现金平均下来每天的消费节奏没变。3.3 std::hash之外的哈希函数什么时候需要自己写std::hashstd::string能用但不同标准库实现对字符串哈希的实现千差万别。有的实现比较朴素对大量相似字符串可能分布不够均匀有的实现干脆就是FNV或MurmurHash变体性能很好。工程上如果你对哈希分布有更高要求可以自己写一个稳定的哈希函数。我比较常用的是FNV-1a实现简单、速度极快、分布也不错size_t fnv1a(const char* data, size_t len) { size_t hash 1469598103934665603ULL; for (size_t i 0; i len; i) { hash ^ static_castunsigned char(data[i]); hash * 1099511628211ULL; } return hash; }用字符串做key的场景可以直接用它替代std::hash。但更常见的情况是你自己定义了一个结构体想做key。比如struct UserKey { std::string name; int id; bool operator(const UserKey other) const { return name other.name id other.id; } };光有operator还不够你还得告诉哈希表怎么给UserKey算哈希。这时候可以给std::hash做偏特化namespace std { template struct hashUserKey { size_t operator()(const UserKey k) const noexcept { size_t h1 hashstring{}(k.name); size_t h2 hashint{}(k.id); return h1 ^ (h2 1); } }; }这个组合哈希的技巧很多老手都在用两个子哈希异或再把其中一个左移一位避免不同字段凑出来相同的组合。当然这不是终极方案但足够应付大多数场景。还有一点需要注意operator和hash必须保持一致。如果哈希函数只算了id但operator还比较name就会发生诡异问题明明id相等但name不同的两个key落进同一个桶然后operator告诉你不相等于是哈希表里同时存在两个“逻辑上应该冲突的key”这是自找麻烦。4. 和std::unordered_map对比我的代码到底差在哪4.1 查漏补缺我缺的那些成员函数手写版本主打一个能用但和标准库一比差距是全方位的。std::unordered_map至少有这些我第一版没有的东西operator[]map[key]可以直接读取如果key不存在还会插入一个默认构造的value。这个语法糖在写缓存、计数器时太方便了。at()和operator[]一样是访问但key不存在时抛出out_of_range更安全。完整的迭代器接口begin()、end()、it、for (auto [k, v] : map)这种范围遍历对使用者来说太重要了。emplace()原地构造避免临时对象拷贝。reserve()提前分配好桶数量减少rehash次数。max_load_factor()/load_factor()查看和调整负载因子。其中我特别建议自己实现一下迭代器。迭代器的本质是在桶数组和链表之间来回穿梭遍历时先走到第一个非空桶取链表头节点链表走完了再往后找下一个非空桶。这个逻辑听起来简单但边界条件极多写一遍能加深你对容器内存布局的理解。4.2 性能实测自定义哈希表 vs STL我在自己的机器上跑了一个简单基准分别用自写哈希表和std::unordered_map插入并查找100万个int到int的键值对结果大概是这样仅作参考不同编译器、平台差异很大操作自写哈希表std::unordered_map插入100万int键约320ms约250ms查找100万int键约180ms约150ms删除100万int键约190ms约160msSTL比我写得快核心原因有三个第一STL的rehash策略和桶增长策略更精细它一般不会每次只翻一倍而是通过reserve和max_load_factor的组合让rehash次数更少。第二STL的节点分配有时候会用特殊的内存池配合allocator避免每次new/delete都走慢速的内存管理。第三STL在unordered_map的实现里每个桶挂的可能不只是链表C11以后的标准允许采用桶内红黑树等更复杂的结构在大规模冲突时能保住底线。但这不意味着手写没有意义。恰恰相反手写一遍能让你理解为什么reserve能提升性能因为它预分配了桶避免了多次rehash。为什么移动语义能提升性能因为插入时不会拷贝一个大的字符串key。这些微观机制不亲手敲一遍代码是真体会不深的。4.3 哈希表和字典的关系别再问是不是一回事网上搜哈希表和字典的区别的人非常多这里我明确说结论字典是抽象数据类型哈希表是底层实现方式之一。它们不是同一个维度的概念。字典指的是这样一种容器给定一个key能取回对应的value不支持按下标顺序访问。至于底层是哈希表、红黑树、跳表还是二叉搜索树那是另一回事。C里std::map是红黑树实现的有序字典——内部按key排序遍历时有序但操作是O(log n)。std::unordered_map是哈希表实现的无序字典——遍历时顺序无意义但平均O(1)。Python的dict和Java的HashMap也都是哈希表实现的字典。所以如果有人问你哈希表和字典什么区别你可以告诉他字典是一类接口哈希表是一种实现。就像车和电动车的区别电动车是车的一种哈希表是字典的一种。我这里有个切身经历刚学C那会儿看到unordered_map这个长名字第一反应是好丑为什么不叫Dictionary。后来换了Python写了几行d {a: 1}又觉得这map到底和dict差在哪。其实它们都是哈希表只是语言给的名字不一样。站在数据结构的角度看学会了C的实现Python的dict和Java的HashMap对你来说都是换了个马甲的熟人。5. 实战中踩过的坑和保命技巧5.1 迭代器失效rehash之后指针全废有一次我写一个消息去重模块要在遍历一个unordered_map的过程中对每个元素判断是不是需要把它附近的一组key也插进去。代码如下for (auto it msgMap.begin(); it ! msgMap.end(); it) { // 处理 it if (needMore(it-first)) { msgMap[someKey] someValue; // 触发了 rehash } }结果程序时不时崩溃而且崩溃点非常随机。查了半天最后定位到我在遍历过程中插入了新元素导致unordered_map内部rehash所有迭代器全部失效。it指向的节点已经被搬到新桶里但迭代器里还存着旧的指针用它it相当于操作一个悬空指针。这个坑几乎所有写哈希表的人都踩过而且自写版本更容易踩。标准库至少还会在debug模式下给你一个断言提示自写版直接随机崩溃。保命技巧有三条遍历和插入分开做先收集需要插入的key遍历结束后再统一插入。如果一定要在遍历中插入先调用reserve提前分配足够的桶尽量避免rehash。删除时使用erase(it)的返回值它返回下一个有效迭代器这是标准库保证的for (auto it msgMap.begin(); it ! msgMap.end();) { if (needErase(it-first)) { it msgMap.erase(it); } else { it; } }5.2 string做key时最容易被忽视的性能黑洞还有一个我见过很多次的性能事故拿很长的字符串当key频繁查询。哈希计算需要遍历整个字符串比如指纹校验场景里一条消息可能几KB每个key查一次就得把整条消息从头到尾过一遍。如果每天请求量几百万光是哈希计算时间就非常可观。解决办法不是换哈希函数而是换key类型。如果字符串的长度固定或者能拆成几个结构化字段用结构体做key往往比用长字符串便宜得多。如果字符串确实没法避免就考虑用string_view配合允许悬空的存储方案——注意生命周期字符串底层的存储必须比哈希表活得久否则就是悬空引用的灾难。另外用std::string做key时还有一个隐性问题operator[]插入默认值时会发生一次临时字符串的构造和拷贝。如果value是shared_ptr、vector这种带堆分配的重量级对象成本更明显。用emplace代替operator[]能省掉这一层拷贝// 不推荐可能多一次构造和拷贝 map[key] complexObject; // 推荐原地构造 map.emplace(key, complexObject);5.3 哈希冲突滥用从一个极端案例说开去最后说一个相对进阶的坑如果哈希函数太简单攻击者可以构造出一批哈希值相同但内容不同的key让它们全部塞进同一个桶哈希表从平均O(1)直接退化成O(n)。这就是早年互联网上常说的哈希碰撞拒绝服务攻击的思路来源。std::unordered_map在主流标准库实现中已经加入了随机化防御每次创建容器时用随机种子初始化哈希状态使攻击者难以预测哈希值。但自写哈希表如果直接用固定哈希函数就有这种脆弱性。做内部工具、面试作品不暴露给不可信输入问题不大。但如果你做的服务和网络请求相关还是老老实实用标准库或者成熟的哈希算法。另有一个实用建议不要迷信计算量越大的哈希函数越好。好的哈希函数应该在速度和分布之间取平衡。像CRC32、FNV-1a这种轻量哈希在非对抗场景下完全够用只有在安全敏感场景才需要更贵的算法。衡量哈希函数的唯一标准是实测同样的数据换不同哈希函数跑一遍看插入查找时间、看桶分布是否均匀数据说话别靠资料吹。最后分享一个小技巧如果你预知要插入的元素数量开局就reserve到位能有效避免多次rehash的卡顿。我在跑批量任务时经常顺手写一句map.reserve(expectedSize * 2)效果立竿见影内存没多多少时间省一截。哈希表这东西用好了是一把快刀用不好就是性能刺客。理解原理动手实现再回头用标准库三个阶段走一遍你心里就彻底有底了。