尧图网页设计 
如果你学C学到容器这一层一定绕不开哈希表。面试八股爱问它工程代码里用它对键值做快速存取就连不少数据库索引的底层设计也脱胎于这一套思路。我最初觉得哈希表不就是数组加一个哈希函数嘛直到自己动手完整实现了一遍才发现水很深哈希函数选型、冲突处理、扩容时的节点搬运、迭代器失效规则每一个点都能写出一篇踩坑实录。这篇文章先从哈希表的基本原理讲起再带你用C手写一个可用的哈希表版本代码我会逐段拆解说明每一步为什么这么设计。无论你是刚学完C基础、想知道容器内部机制的新手还是准备面试想把手写哈希表讲清楚的同学这份笔记应该都能帮到你。1. 先弄懂四个核心概念哈希函数、冲突、负载因子、rehash1.1 数组下标就是最朴素的哈希表很多人第一次接触哈希表的概念时容易把它想得很玄。其实它的最简形态就是数组你给一个数组下标它能在O(1)时间内返回那个位置上的元素。之所以能做到这一点是因为内存里元素是连续排布的CPU算一下首地址加偏移量就能直接跳过去。关键问题是现实世界的键往往不是非负整数。我们要查张三的成绩处理的是字符串张三不可能直接拿字符串当数组下标。于是就有了一个自然的想法写一个函数把任意类型的键key转换成数组下标然后去那个下标位置存取数据。这个函数就是哈希函数这套数据结构就是哈希表。用生活类比来理解假设宿舍楼有100个房间你给每名学生分配一个房间号就能凭名字找到房间。最理想的情况是每个名字对应唯一房间号但现实没那么完美——总有两个名字会撞进同一个房间这就叫哈希冲突。哈希表要解决的就是怎么尽可能让键均匀散开以及在撞车之后怎么处理。1.2 哈希函数到底在干什么哈希函数是一个映射输入一个键输出一个无符号整数这个整数再经过取模等操作变成合法的数组下标。它有几个硬性要求缺一不可。第一是确定性。同一个键任何时候调用哈希函数必须得到同一个结果否则查着查着就找不到数据了。第二是高效性。哈希函数本身的计算开销必须很低如果哈希一次要跑几微秒那哈希表比线性查找还慢就失去意义了。第三是散列均匀性。不同的键尽量映射到不同位置分布得越均匀冲突越少哈希表性能就越好。举个例子对整数键直接用取模是最常见的做法index key % bucket_count。看起来简单但如果bucket_count选得不好比如等于10而你的键全是10的倍数那所有键都会挤在同一个桶里哈希表直接退化成链表查找复杂度变成O(n)。后面第3章我会详细讲桶数量怎么选。1.3 冲突哈希表躲不开的宿命不管你哈希函数写得多好只要待存储的键数量超过桶的数量冲突就一定会发生。这个结论在数学上是很强的假设有365个桶往里面随机丢233个人出现至少一对冲突的概率就超过50%这就是著名的生日问题。工程上的哈希桶数量通常是小于元素数量的所以冲突不是会不会发生而是发生之后怎么处理。主流的冲突处理方案有两类。第一类是链地址法也就是每个桶后面挂一个链表。新元素算出来落在某个桶就头插进这个桶的链表里。查找时先定位桶再沿着链表逐个比较键。第二类是开放地址法冲突发生后去寻找下一个空闲的桶比如线性探测就是逐个往后找空位。两类方案各有取舍我这次实现采用的是链地址法理由见第2章这里先记住结论链地址法实现直观删除简单对负载因子的容忍度高适合通用容器。1.4 负载因子什么时候该扩容哈希表里有个重要指标叫负载因子load_factor 元素数量 / 桶数量。它反映了哈希表的拥挤程度。负载因子越小冲突越少但浪费的内存越多负载因子越大内存利用率越高但冲突急剧增加查一次可能要把一个长链表扫完性能明显下滑。标准库unordered_map一般把默认负载因子控制在1.0附近也就是说元素数量和桶数量差不多时才开始扩容。工程实践里0.75是一个很常见的阈值超过这个值就触发扩容把桶数组扩大一倍再把已有节点全部重新分配到新桶里。这个重新分配的过程就是rehash。从设计动机上讲负载因子不是越高越好。链地址法里链表长度如果平均超过1每次查找平均就要多比较几次。而0.75这个值在时间和空间上能达到一个不错的平衡。后面我的实现就完全按这个思路来做。2. 为什么要自造轮子unordered_map它不香吗2.1 std::unordered_map已经把事做完了还有必要自己写这是很多人面对的第一个疑问。C标准库里的std::unordered_map功能完善、久经考验日常开发直接调用它当然是最合理的选择。但能用和懂它是两回事。面试官最爱问请实现一个哈希表不是因为他真想让你在生产环境重造一个而是想看你知不知道节点结构、扩容机制、冲突处理这些底层细节。另外自己实现哈希表在实际工程里也有实用价值。比如你可以在哈希函数上完全自定义可以用紧凑的节点布局减少缓存miss可以去掉迭代器、const版本等通用容器必须携带的额外负担做一个只满足当前场景的轻量版本。我见过不少游戏服务端、嵌入式项目里就是这么干的。对于教育和面试场景自己写一遍的收获远大于背一百遍unordered_map平均O(1)。2.2 链地址法还是开放地址法动手之前要先定方案这里我把两套主流方案摆出来对比。维度链地址法开放地址法实现难度简单节点用链表串起来即可中等探测序列要设计好删除操作简单摘掉一个链表节点就行麻烦直接置空会破坏探测链需要墓碑标记内存开销每个节点多一个next指针无指针但桶数组必须留空位缓存友好性差节点散落堆中链表跳跃访问好数据集中在数组里负载因子容忍度可以接近1甚至超过1一般不超过0.7否则探测链会越来越长我这次选择链地址法。理由很现实文章的目的是基本介绍自我实现链地址法的代码逻辑最贴合教科书上的讲解删除一个节点不会影响其他节点的探测路径出错概率低。如果你后续有兴趣可以再挑战开放地址法那又是一个新世界。2.3 我这次实现的设计目标敲代码之前先把目标定清楚这个哈希表要做到什么程度。泛型模板同时支持键值对类型类似std::unordered_mapKey, Value。自动扩容当负载因子超过0.75时桶数组翻倍并把旧节点搬过去。提供insert、find、erase、operator[]、size、empty等常用接口。提供最简单的迭代器能支持begin()、end()和遍历方便验证正确性。处理好异常安全rehash过程中如果内存分配失败不能让原哈希表处于半破坏状态。至于const迭代器、异质查找、桶操作接口这类完整版功能本文不展开代码里会注明属于可以扩展的加分项。3. 动手之前的三个关键设计桶数量、哈希函数、扩容3.1 桶数量用2的幂还是随便一个数哈希函数算出来的通常是无符号整数要落到具体的桶最常见的就是取模。如果用index hash(key) % bucket_count那bucket_count取什么都行。但很多人为了让取模更快会把桶数量固定成2的幂这样取模就能用位运算hash(key) (bucket_count - 1)代替速度确实快一点。2的幂有个明显弱点它只使用了哈希值的低位比特。如果哈希函数的低比特分布不均匀冲突会明显增多。举个典型的坑如果键都是偶数的整数桶数量是16那么所有元素只会落进0、2、4、6、8、10、12、14这8个桶一半的桶空着。所以这里有一个取舍。标准库的实现各自有选择有的用质数桶有的用2的幂桶配合高质量的哈希。我在下面的实现里直接用取模不强制桶数量是2的幂这样代码更通用也方便你理解核心逻辑。如果你要针对极端性能做优化再考虑2的幂加位运算但前提是自定义哈希函数质量足够高。3.2 默认哈希够用吗乘法哈希又是什么C里std::hashKey给基本类型提供了默认特化对int、double、string这些都能直接用。那就用默认的够不够答案是基本够用但你要是想写一个追求极致均匀的哈希表默认哈希不一定让你满意。原因是很多整数哈希函数在映射到小范围桶时表现取决于低比特的随机性。如果键的分布规律性很强比如都是等差数列取模后可能会聚集到少数桶。一个经典的优化是乘法哈希用Knuth 提出的黄金分割乘法散列对32位无符号整数取key * 2654435761然后只保留高位。这个乘数大约等于2^32除以黄金分割比能让乘积的高比特充分混合键的各个位。size_t knuth_hash(uint32_t key) { return static_castsize_t(key * 2654435761u) (32 - 4); }上面这个例子把32位键映射到16个桶的范围。乘法的低位噪音被移位丢掉留下的是充分混合后的高几位比单纯取模更抗规律性输入。对哈希表来说哈希函数的输出再配合负载因子控制冲突率能达到一个可接受的水平。我的实现里为了通用性仍然以std::hash取模为主但理解这些细节对你面试聊八股很有帮助。3.3 扩容和rehash唯一需要操心的异常安全点哈希表扩容的本质是新开一块更大的桶数组把旧桶里的每个节点重新计算桶号搬到新桶里最后再释放旧桶数组。这里有一个很重要的设计决策——节点的移动必须移动指针而不是删除重造。如果扩容时把旧节点全部delete再在桶里new一批新节点那么节点内存地址全部变了所有还在用这些节点的迭代器立即失效而且额外增加大量堆分配开销。正确的做法是节点本身不动只把节点的next指针重新连接。扩容后节点仍然存在于堆上只是归属桶变了迭代器指向的节点内存还是有效的。异常安全处理也在这里。新桶数组的分配通过std::vectorNode*来完成这一步可能抛出std::bad_alloc。我的写法是先把新桶数组构建完成void rehash里先std::vectorNode* new_buckets(new_bucket_count, nullptr)如果这里分配失败函数直接抛出旧buckets_完好无损。后续搬运节点全部是指针操作不会抛异常最后buckets_.swap(new_buckets)生效。这个顺序是刻意的先分配、再搬运、最后替换保证任何一步失败都不会破坏原哈希表。3.4 删除节点单链表的前驱之痛链地址法删除一个节点本质上是从单链表里摘掉一个节点。单链表删除的经典困境是你要找到待删除节点的前驱节点把前驱的next指向待删除节点的next。如果待删除节点恰好是桶的第一个节点它没有前驱那就要特殊处理把buckets_[idx]直接指向cur-next。这个细节看起来简单实际操作时非常容易漏。我见过很多初版手写哈希表插入和查找都写对了唯独删除只维护了链表内部的prev指针忽略了桶头指针本身需要更新结果一删除头节点下一次访问这个桶就直接崩溃。这就是我第4章erase实现里为什么要把是否删除桶头单独判断出来的原因。写哈希表细节点往往决定生死。4. 完整实现从节点定义到迭代器逐段拆给你看4.1 节点与类骨架先看节点定义。哈希表的基本存储单元就是节点链地址法下每个节点必须包含键、值、指向同桶下一个节点的指针。template typename Key, typename Value, typename Hash std::hashKey class HashMap { private: struct Node { std::pairconst Key, Value data; Node* next; Node(const Key key, const Value value, Node* n nullptr) : data(key, value), next(n) {} }; std::vectorNode* buckets_; size_t size_ 0; float max_load_factor_ 0.75f; Hash hasher_;注意data的类型是std::pairconst Key, Value键值对里的Key用const修饰。这是模仿std::unordered_map的语义外部可以修改已插入元素的值但不能修改它的键。一旦修改键哈希值就变了哈希表就再也找不到这个元素了。类内部维护三样东西桶数组、当前元素个数、负载因子阈值。这里的buckets_用std::vectorNode*管理生命周期vector析构时会把指针数组本身释放掉但节点是new出来的必须由我们自己负责删除于是析构函数一定要调用清空函数释放所有节点~HashMap() { clear(); } void clear() { for (Node* head : buckets_) { Node* cur head; while (cur) { Node* next cur-next; delete cur; cur next; } } buckets_.assign(buckets_.size(), nullptr); size_ 0; }清空函数里逐个桶遍历链表先把cur-next保存下来再delete当前节点。这个保存next的写法是必须的不然delete之后你永远找不到下一个节点了。这也是一个非常经典的内存管理细节。4.2 insert一次插入把关三个东西插入是哈希表最核心的操作它要处理三件事要不要扩容、键是否已存在、新节点放到哪里。std::pairiterator, bool insert(const Key key, const Value value) { if (size_ 1 static_castsize_t(max_load_factor_ * buckets_.size())) { rehash(buckets_.size() * 2); } size_t idx bucket_index(key); Node* cur buckets_[idx]; while (cur) { if (cur-data.first key) { return { iterator(this, cur, idx), false }; } cur cur-next; } Node* inserted new Node(key, value, buckets_[idx]); buckets_[idx] inserted; size_; return { iterator(this, inserted, idx), true }; }返回类型设计成std::pairiterator, bool是和标准库对齐的。第一个值指向已经存在的节点或刚刚插入的节点第二个值表示本次插入是否成功。如果键已存在不需要也不能再插一个直接返回false把已有节点指给调用者。扩容判断写在插入之前用size_ 1和当前桶数乘负载因子比较。这里刻意在插入前判断保证插入完成后负载因子一定不会超过阈值。扩容后桶数翻倍执行一次rehash原来的桶数组被替换成新的大数组。新节点采用头插法直接放在桶链表最前面也就是new Node(key, value, buckets_[idx])把旧表头作为新节点的next再把buckets_[idx]更新为新节点。头插的好处是O(1)而且新插入的元素通常很快会被再次访问放链表头部能少走几步。4.3 find和operator[]读数据也有门道查找的逻辑和插入前半部分几乎一致计算桶号沿链表比较键。iterator find(const Key key) { size_t idx bucket_index(key); Node* cur buckets_[idx]; while (cur) { if (cur-data.first key) { return iterator(this, cur, idx); } cur cur-next; } return end(); }找不到就返回end()和标准库一致。这里哈希表的平均查找复杂度是O(1)但链表比较这个动作不可避免。所以哈希函数质量直接决定链表平均长度也就决定了查找性能。operator[]的语义值得单独讲一下。它用来既读又写比如scores[alice] 90。但标准库规定如果用operator[]访问一个不存在的键会自动插入该键并返回默认值的引用。所以我实现时直接复用insert传入一个默认构造的ValueValue operator[](const Key key) { std::pairiterator, bool result insert(key, Value()); return result.first-second; }这里隐含一个要求Value类型必须默认可构造否则编译不过。如果你写一个HashMapstring, vectorintvector可以默认构造没问题但如果Value是个没有默认构造函数的自定义类就只能用insert而不能用operator[]。4.4 erase最考验基本功的地方删除逻辑直接对应前面3.4讲的前驱问题。我把代码写出来你看它怎么处理删除桶头和删除非桶头两条分支bool erase(const Key key) { size_t idx bucket_index(key); Node* cur buckets_[idx]; Node* prev nullptr; while (cur) { if (cur-data.first key) { if (prev nullptr) { buckets_[idx] cur-next; } else { prev-next cur-next; } delete cur; --size_; return true; } prev cur; cur cur-next; } return false; }遍历时用一个prev指针记录前驱。找到目标节点后判断prev nullptr——如果为空说明目标就是这个桶的链表头桶头必须更新为cur-next否则把前驱的next跨过目标节点指向目标节点的next。两种情况的本质都是让链表的上一环绕过目标节点只不过桶头的上一环是桶数组本身不能不用特殊方式处理。删除后要delete cur并--size_。返回bool表示是否真的删掉了。这套逻辑你修为能半小时正确写出来的程度手写哈希表的半条腿就算落地了。4.5 iterator跨桶遍历的细节标准库容器的遍历是最能证明实现自洽的部分。哈希表的迭代器逻辑是从某个桶的链表头出发先顺着链表走链表走到头就要跳到下一个非空桶继续。class iterator { private: HashMap* map_; Node* node_; size_t bucket_; public: iterator(HashMap* map, Node* node, size_t bucket) : map_(map), node_(node), bucket_(bucket) {} std::pairconst Key, Value operator*() const { return node_-data; } std::pairconst Key, Value* operator-() const { return node_-data; } iterator operator() { if (node_) { node_ node_-next; if (node_) return *this; } bucket_; while (bucket_ map_-buckets_.size()) { node_ map_-buckets_[bucket_]; if (node_) break; bucket_; } return *this; } iterator operator(int) { iterator old *this; (*this); return old; } bool operator(const iterator other) const { return map_ other.map_ node_ other.node_ bucket_ other.bucket_; } bool operator!(const iterator other) const { return !(*this other); } };operator是迭代器最容易写错的地方。先试着往前走当前桶的链表一步如果走完链表发现node变成nullptr说明这个桶已经空了接下来桶号自增继续找下一个非空桶。bucket_到达buckets_.size()时停下来node保持nullptr这就是end()。迭代器要持有map_指针因为跳到下一个桶时需要访问map内部的桶数组。前向迭代器语义足够了不实现反向迭代器这是教学简化。4.6 完整源码和简单测试把上面所有部分拼起来加上构造函数、析构、reserve、begin、end和桶号计算就是一份可以编译运行的手写哈希表。完整代码如下。#include vector #include utility #include functional #include iostream template typename Key, typename Value, typename Hash std::hashKey class HashMap { private: struct Node { std::pairconst Key, Value data; Node* next; Node(const Key key, const Value value, Node* n nullptr) : data(key, value), next(n) {} }; std::vectorNode* buckets_; size_t size_ 0; float max_load_factor_ 0.75f; Hash hasher_; size_t bucket_index(const Key key) const { return hasher_(key) % buckets_.size(); } public: class iterator { private: HashMap* map_; Node* node_; size_t bucket_; public: iterator(HashMap* map, Node* node, size_t bucket) : map_(map), node_(node), bucket_(bucket) {} std::pairconst Key, Value operator*() const { return node_-data; } std::pairconst Key, Value* operator-() const { return node_-data; } iterator operator() { if (node_) { node_ node_-next; if (node_) return *this; } bucket_; while (bucket_ map_-buckets_.size()) { node_ map_-buckets_[bucket_]; if (node_) break; bucket_; } return *this; } iterator operator(int) { iterator old *this; (*this); return old; } bool operator(const iterator other) const { return map_ other.map_ node_ other.node_ bucket_ other.bucket_; } bool operator!(const iterator other) const { return !(*this other); } }; HashMap() : buckets_(8, nullptr) {} ~HashMap() { clear(); } HashMap(const HashMap) delete; HashMap operator(const HashMap) delete; size_t size() const { return size_; } bool empty() const { return size_ 0; } void clear() { for (Node* head : buckets_) { Node* cur head; while (cur) { Node* next cur-next; delete cur; cur next; } } buckets_.assign(buckets_.size(), nullptr); size_ 0; } void reserve(size_t expected_elements) { size_t need static_castsize_t(expected_elements / max_load_factor_) 1; if (need buckets_.size()) { rehash(need); } } void rehash(size_t new_bucket_count) { std::vectorNode* new_buckets(new_bucket_count, nullptr); for (Node* head : buckets_) { Node* cur head; while (cur) { Node* next cur-next; size_t idx hasher_(cur-data.first) % new_buckets.size(); cur-next new_buckets[idx]; new_buckets[idx] cur; cur next; } } buckets_.swap(new_buckets); } std::pairiterator, bool insert(const Key key, const Value value) { if (size_ 1 static_castsize_t(max_load_factor_ * buckets_.size())) { rehash(buckets_.size() * 2); } size_t idx bucket_index(key); Node* cur buckets_[idx]; while (cur) { if (cur-data.first key) { return { iterator(this, cur, idx), false }; } cur cur-next; } Node* inserted new Node(key, value, buckets_[idx]); buckets_[idx] inserted; size_; return { iterator(this, inserted, idx), true }; } iterator find(const Key key) { size_t idx bucket_index(key); Node* cur buckets_[idx]; while (cur) { if (cur-data.first key) { return iterator(this, cur, idx); } cur cur-next; } return end(); } Value operator[](const Key key) { std::pairiterator, bool result insert(key, Value()); return result.first-second; } bool erase(const Key key) { size_t idx bucket_index(key); Node* cur buckets_[idx]; Node* prev nullptr; while (cur) { if (cur-data.first key) { if (prev nullptr) { buckets_[idx] cur-next; } else { prev-next cur-next; } delete cur; --size_; return true; } prev cur; cur cur-next; } return false; } iterator begin() { for (size_t i 0; i buckets_.size(); i) { if (buckets_[i] ! nullptr) { return iterator(this, buckets_[i], i); } } return end(); } iterator end() { return iterator(this, nullptr, buckets_.size()); } }; int main() { HashMapstd::string, int scores; scores[alice] 90; scores[bob] 85; scores[carol] 78; auto [it, ok] scores.insert(alice, 95); if (!ok) { std::cout alice already exists, value it-second std::endl; } for (auto iter scores.begin(); iter ! scores.end(); iter) { std::cout iter-first : iter-second std::endl; } scores.erase(bob); std::cout after erase, size scores.size() std::endl; return 0; }这里我禁用了拷贝构造和赋值操作因为它们对指针容器的默认行为是浅拷贝会让两个对象指向同一批节点析构时双重释放。真实生产环境的版本应该实现深拷贝或者移动语义本文为了专注核心逻辑做了简化特此说明。5. 常见问题与调优自定义类型、字符串哈希和性能实测5.1 自定义类型放入哈希表两条硬性原则把自定义类型当键是使用哈希表时最常遇到的需求。这里一定要守住两条原则。第一条是强制原则相等的对象哈希值必须相等。比如你定义一个Student结构两个Student只要name和id相同就认为相等那么它们的哈希值必须一样。否则插入一个对象后再用相等的另一个对象去find算出来的桶号不同根本找不到。这是哈希表正确性的基石。第二条是经验原则尽量让哈希值分布均匀。很多人图省事直接对某个字段做哈希容易出现大量对象集中到少数桶里的问题。一个常用的组合技巧是把多个字段的哈希值混合起来类似Boost库里的hash_combine思路struct Student { std::string name; int id; bool operator(const Student other) const { return name other.name id other.id; } }; struct StudentHash { size_t operator()(const Student s) const { size_t h1 std::hashstd::string{}(s.name); size_t h2 std::hashint{}(s.id); return h1 ^ (h2 0x9e3779b9 (h1 6) (h1 2)); } };那个0x9e3779b9是黄金分割比例的32位表示用在混合两个哈希值时能避免简单异或导致的对称性问题。你用的时候把StudentHash作为第三个模板参数传给HashMap即可。5.2 字符串哈希FNV-1a等靠谱方案字符串作为哈希表的键出现频率高得吓人。直接使用std::hashstd::string没问题但如果你自己实现哈希函数我推荐FNV-1a。它简单、速度快、散布效果好在很多标准库输出重定向、文件路径缓存场景里被广泛使用。size_t fnv1a(const char* data, size_t len) { size_t hash 14695981039346656037ULL; // 64位偏移基数 for (size_t i 0; i len; i) { hash ^ static_castunsigned char(data[i]); hash * 1099511628211ULL; // 64位素数 } return hash; }它的核心操作只有两步异或当前字符乘以一个固定大素数。每一步都在让整个哈希值发生扰动最终把每个字符的信息扩散到所有位上。注意这里强制把char转成unsigned char再异或是为了避免有符号char对高位的影响这是字符串哈希很容易被忽略的隐蔽细节。实际替换到HashMap里很简单把Hash模板参数传成hashstring的自定义仿函数或者直接让Key类型自己提供哈希专门函数。写测试时你会发现FNV-1a对短字符串的哈希速度比某些重量级加密哈希快一个数量级关键在于它循环内部没有复杂运算。5.3 实测手写版和unordered_map差多少我拿刚才这份代码在开启-O2优化后简单测了一下插入100万个随机的uint64_t键然后再逐个查找一遍。结论是手写版和libstdc的std::unordered_map差距很小大概率在个位数百分比以内。因为核心结构本来就和标准库是同一类设计——链地址法、按负载因子扩容、桶数组加链表。但有几个变量会影响结论测试时一定要控制住。第一是reserve策略预先reserve足够的空间可以消除扩容带来的波动。上面的代码里我的reserve语义是按元素数量预留先算出需要的桶数再扩容和标准库一致不做reserve的话测试结果会有明显噪声。第二是哈希函数两边都使用std::hash时公平。第三是迭代器遍历手写哈希表时桶越多越可能跳过空桶遍历开销略高但插入和查找核心影响不大。手写版最大优势在于你可以针对具体场景魔改。比如我知道键都是连续整数就可以直接把哈希函数省掉用键本身当桶号的一部分又比如我知道只插入不删除可以把erase相关的逻辑全部剥掉。这种减负能力是黑盒的unordered_map给不了你的。5.4 我踩过的四个坑内存、迭代器、reserve、误用自己动手写哈希表最大的收获来自踩坑。我复盘一下写这个版本时遇到的几个典型问题希望你避开。第一个是内存泄漏。早期版本忘了写析构函数或者写完析构却忘了在clear里逐个delete节点结果是程序运行过程中内存只涨不降。哈希表持有大量堆节点不手动管理必漏无疑。写类时一定要第一时间确认谁负责delete在哪个函数里delete析构路径覆盖不覆盖所有分支第二个是迭代器失效。链地址法下扩容会把所有桶重新分配所以扩容后所有迭代器全部失效删除一个节点后指向该节点的迭代器失效但指向同桶其他节点的迭代器仍然有效。这和vector、deque这种连续内存容器的失效规则完全不一样面试常考。第三个是reserve的误用。有些人直接把reserve(n)理解成把桶数组扩到n个结果真正插入n个元素时触发多次扩容开销反而更大。标准库的reserve语义是预留能容纳n个元素而不rehash的空间我实现的版本也照这个语义处理先按负载因子把元素数换算成桶数。使用时要注意区分这两种表述。第四个是operator[]误用。很多人手写哈希表时只提供find后来又为了省事加上operator[]结果在查一下某个键在不在的代码里不小心用下标访问把一个不存在的键插入成了默认值数据凭空多出一大堆。如果只是判断存在性一定用find不要用operator[]。这一点在真实工程里也是经典教训我见过线上代码因为这个原因搞出大量脏数据。回到整个实现上来我个人最大的体会是哈希表不是一个背一背就懂的数据结构里面每设计细节都和你最终能踩的坑数量直接相关。写一遍、跑一遍、故意写错一遍比看十遍教科书都管用。如果你正在准备面试或者想扎实理解STL容器我建议别只看这段代码而是自己从头敲一遍把桶数量从8改成3把负载因子从0.75改成1.5把头插改成尾插再跑一遍测试你就能清楚看到每个设计决策带来的性能差异和正确性影响。这比记任何八股结论都深刻。 C++手写哈希表：从原理到实现，详解冲突处理与扩容机制
如果你学C学到容器这一层一定绕不开哈希表。面试八股爱问它工程代码里用它对键值做快速存取就连不少数据库索引的底层设计也脱胎于这一套思路。我最初觉得哈希表不就是数组加一个哈希函数嘛直到自己动手完整实现了一遍才发现水很深哈希函数选型、冲突处理、扩容时的节点搬运、迭代器失效规则每一个点都能写出一篇踩坑实录。这篇文章先从哈希表的基本原理讲起再带你用C手写一个可用的哈希表版本代码我会逐段拆解说明每一步为什么这么设计。无论你是刚学完C基础、想知道容器内部机制的新手还是准备面试想把手写哈希表讲清楚的同学这份笔记应该都能帮到你。1. 先弄懂四个核心概念哈希函数、冲突、负载因子、rehash1.1 数组下标就是最朴素的哈希表很多人第一次接触哈希表的概念时容易把它想得很玄。其实它的最简形态就是数组你给一个数组下标它能在O(1)时间内返回那个位置上的元素。之所以能做到这一点是因为内存里元素是连续排布的CPU算一下首地址加偏移量就能直接跳过去。关键问题是现实世界的键往往不是非负整数。我们要查张三的成绩处理的是字符串张三不可能直接拿字符串当数组下标。于是就有了一个自然的想法写一个函数把任意类型的键key转换成数组下标然后去那个下标位置存取数据。这个函数就是哈希函数这套数据结构就是哈希表。用生活类比来理解假设宿舍楼有100个房间你给每名学生分配一个房间号就能凭名字找到房间。最理想的情况是每个名字对应唯一房间号但现实没那么完美——总有两个名字会撞进同一个房间这就叫哈希冲突。哈希表要解决的就是怎么尽可能让键均匀散开以及在撞车之后怎么处理。1.2 哈希函数到底在干什么哈希函数是一个映射输入一个键输出一个无符号整数这个整数再经过取模等操作变成合法的数组下标。它有几个硬性要求缺一不可。第一是确定性。同一个键任何时候调用哈希函数必须得到同一个结果否则查着查着就找不到数据了。第二是高效性。哈希函数本身的计算开销必须很低如果哈希一次要跑几微秒那哈希表比线性查找还慢就失去意义了。第三是散列均匀性。不同的键尽量映射到不同位置分布得越均匀冲突越少哈希表性能就越好。举个例子对整数键直接用取模是最常见的做法index key % bucket_count。看起来简单但如果bucket_count选得不好比如等于10而你的键全是10的倍数那所有键都会挤在同一个桶里哈希表直接退化成链表查找复杂度变成O(n)。后面第3章我会详细讲桶数量怎么选。1.3 冲突哈希表躲不开的宿命不管你哈希函数写得多好只要待存储的键数量超过桶的数量冲突就一定会发生。这个结论在数学上是很强的假设有365个桶往里面随机丢233个人出现至少一对冲突的概率就超过50%这就是著名的生日问题。工程上的哈希桶数量通常是小于元素数量的所以冲突不是会不会发生而是发生之后怎么处理。主流的冲突处理方案有两类。第一类是链地址法也就是每个桶后面挂一个链表。新元素算出来落在某个桶就头插进这个桶的链表里。查找时先定位桶再沿着链表逐个比较键。第二类是开放地址法冲突发生后去寻找下一个空闲的桶比如线性探测就是逐个往后找空位。两类方案各有取舍我这次实现采用的是链地址法理由见第2章这里先记住结论链地址法实现直观删除简单对负载因子的容忍度高适合通用容器。1.4 负载因子什么时候该扩容哈希表里有个重要指标叫负载因子load_factor 元素数量 / 桶数量。它反映了哈希表的拥挤程度。负载因子越小冲突越少但浪费的内存越多负载因子越大内存利用率越高但冲突急剧增加查一次可能要把一个长链表扫完性能明显下滑。标准库unordered_map一般把默认负载因子控制在1.0附近也就是说元素数量和桶数量差不多时才开始扩容。工程实践里0.75是一个很常见的阈值超过这个值就触发扩容把桶数组扩大一倍再把已有节点全部重新分配到新桶里。这个重新分配的过程就是rehash。从设计动机上讲负载因子不是越高越好。链地址法里链表长度如果平均超过1每次查找平均就要多比较几次。而0.75这个值在时间和空间上能达到一个不错的平衡。后面我的实现就完全按这个思路来做。2. 为什么要自造轮子unordered_map它不香吗2.1 std::unordered_map已经把事做完了还有必要自己写这是很多人面对的第一个疑问。C标准库里的std::unordered_map功能完善、久经考验日常开发直接调用它当然是最合理的选择。但能用和懂它是两回事。面试官最爱问请实现一个哈希表不是因为他真想让你在生产环境重造一个而是想看你知不知道节点结构、扩容机制、冲突处理这些底层细节。另外自己实现哈希表在实际工程里也有实用价值。比如你可以在哈希函数上完全自定义可以用紧凑的节点布局减少缓存miss可以去掉迭代器、const版本等通用容器必须携带的额外负担做一个只满足当前场景的轻量版本。我见过不少游戏服务端、嵌入式项目里就是这么干的。对于教育和面试场景自己写一遍的收获远大于背一百遍unordered_map平均O(1)。2.2 链地址法还是开放地址法动手之前要先定方案这里我把两套主流方案摆出来对比。维度链地址法开放地址法实现难度简单节点用链表串起来即可中等探测序列要设计好删除操作简单摘掉一个链表节点就行麻烦直接置空会破坏探测链需要墓碑标记内存开销每个节点多一个next指针无指针但桶数组必须留空位缓存友好性差节点散落堆中链表跳跃访问好数据集中在数组里负载因子容忍度可以接近1甚至超过1一般不超过0.7否则探测链会越来越长我这次选择链地址法。理由很现实文章的目的是基本介绍自我实现链地址法的代码逻辑最贴合教科书上的讲解删除一个节点不会影响其他节点的探测路径出错概率低。如果你后续有兴趣可以再挑战开放地址法那又是一个新世界。2.3 我这次实现的设计目标敲代码之前先把目标定清楚这个哈希表要做到什么程度。泛型模板同时支持键值对类型类似std::unordered_mapKey, Value。自动扩容当负载因子超过0.75时桶数组翻倍并把旧节点搬过去。提供insert、find、erase、operator[]、size、empty等常用接口。提供最简单的迭代器能支持begin()、end()和遍历方便验证正确性。处理好异常安全rehash过程中如果内存分配失败不能让原哈希表处于半破坏状态。至于const迭代器、异质查找、桶操作接口这类完整版功能本文不展开代码里会注明属于可以扩展的加分项。3. 动手之前的三个关键设计桶数量、哈希函数、扩容3.1 桶数量用2的幂还是随便一个数哈希函数算出来的通常是无符号整数要落到具体的桶最常见的就是取模。如果用index hash(key) % bucket_count那bucket_count取什么都行。但很多人为了让取模更快会把桶数量固定成2的幂这样取模就能用位运算hash(key) (bucket_count - 1)代替速度确实快一点。2的幂有个明显弱点它只使用了哈希值的低位比特。如果哈希函数的低比特分布不均匀冲突会明显增多。举个典型的坑如果键都是偶数的整数桶数量是16那么所有元素只会落进0、2、4、6、8、10、12、14这8个桶一半的桶空着。所以这里有一个取舍。标准库的实现各自有选择有的用质数桶有的用2的幂桶配合高质量的哈希。我在下面的实现里直接用取模不强制桶数量是2的幂这样代码更通用也方便你理解核心逻辑。如果你要针对极端性能做优化再考虑2的幂加位运算但前提是自定义哈希函数质量足够高。3.2 默认哈希够用吗乘法哈希又是什么C里std::hashKey给基本类型提供了默认特化对int、double、string这些都能直接用。那就用默认的够不够答案是基本够用但你要是想写一个追求极致均匀的哈希表默认哈希不一定让你满意。原因是很多整数哈希函数在映射到小范围桶时表现取决于低比特的随机性。如果键的分布规律性很强比如都是等差数列取模后可能会聚集到少数桶。一个经典的优化是乘法哈希用Knuth 提出的黄金分割乘法散列对32位无符号整数取key * 2654435761然后只保留高位。这个乘数大约等于2^32除以黄金分割比能让乘积的高比特充分混合键的各个位。size_t knuth_hash(uint32_t key) { return static_castsize_t(key * 2654435761u) (32 - 4); }上面这个例子把32位键映射到16个桶的范围。乘法的低位噪音被移位丢掉留下的是充分混合后的高几位比单纯取模更抗规律性输入。对哈希表来说哈希函数的输出再配合负载因子控制冲突率能达到一个可接受的水平。我的实现里为了通用性仍然以std::hash取模为主但理解这些细节对你面试聊八股很有帮助。3.3 扩容和rehash唯一需要操心的异常安全点哈希表扩容的本质是新开一块更大的桶数组把旧桶里的每个节点重新计算桶号搬到新桶里最后再释放旧桶数组。这里有一个很重要的设计决策——节点的移动必须移动指针而不是删除重造。如果扩容时把旧节点全部delete再在桶里new一批新节点那么节点内存地址全部变了所有还在用这些节点的迭代器立即失效而且额外增加大量堆分配开销。正确的做法是节点本身不动只把节点的next指针重新连接。扩容后节点仍然存在于堆上只是归属桶变了迭代器指向的节点内存还是有效的。异常安全处理也在这里。新桶数组的分配通过std::vectorNode*来完成这一步可能抛出std::bad_alloc。我的写法是先把新桶数组构建完成void rehash里先std::vectorNode* new_buckets(new_bucket_count, nullptr)如果这里分配失败函数直接抛出旧buckets_完好无损。后续搬运节点全部是指针操作不会抛异常最后buckets_.swap(new_buckets)生效。这个顺序是刻意的先分配、再搬运、最后替换保证任何一步失败都不会破坏原哈希表。3.4 删除节点单链表的前驱之痛链地址法删除一个节点本质上是从单链表里摘掉一个节点。单链表删除的经典困境是你要找到待删除节点的前驱节点把前驱的next指向待删除节点的next。如果待删除节点恰好是桶的第一个节点它没有前驱那就要特殊处理把buckets_[idx]直接指向cur-next。这个细节看起来简单实际操作时非常容易漏。我见过很多初版手写哈希表插入和查找都写对了唯独删除只维护了链表内部的prev指针忽略了桶头指针本身需要更新结果一删除头节点下一次访问这个桶就直接崩溃。这就是我第4章erase实现里为什么要把是否删除桶头单独判断出来的原因。写哈希表细节点往往决定生死。4. 完整实现从节点定义到迭代器逐段拆给你看4.1 节点与类骨架先看节点定义。哈希表的基本存储单元就是节点链地址法下每个节点必须包含键、值、指向同桶下一个节点的指针。template typename Key, typename Value, typename Hash std::hashKey class HashMap { private: struct Node { std::pairconst Key, Value data; Node* next; Node(const Key key, const Value value, Node* n nullptr) : data(key, value), next(n) {} }; std::vectorNode* buckets_; size_t size_ 0; float max_load_factor_ 0.75f; Hash hasher_;注意data的类型是std::pairconst Key, Value键值对里的Key用const修饰。这是模仿std::unordered_map的语义外部可以修改已插入元素的值但不能修改它的键。一旦修改键哈希值就变了哈希表就再也找不到这个元素了。类内部维护三样东西桶数组、当前元素个数、负载因子阈值。这里的buckets_用std::vectorNode*管理生命周期vector析构时会把指针数组本身释放掉但节点是new出来的必须由我们自己负责删除于是析构函数一定要调用清空函数释放所有节点~HashMap() { clear(); } void clear() { for (Node* head : buckets_) { Node* cur head; while (cur) { Node* next cur-next; delete cur; cur next; } } buckets_.assign(buckets_.size(), nullptr); size_ 0; }清空函数里逐个桶遍历链表先把cur-next保存下来再delete当前节点。这个保存next的写法是必须的不然delete之后你永远找不到下一个节点了。这也是一个非常经典的内存管理细节。4.2 insert一次插入把关三个东西插入是哈希表最核心的操作它要处理三件事要不要扩容、键是否已存在、新节点放到哪里。std::pairiterator, bool insert(const Key key, const Value value) { if (size_ 1 static_castsize_t(max_load_factor_ * buckets_.size())) { rehash(buckets_.size() * 2); } size_t idx bucket_index(key); Node* cur buckets_[idx]; while (cur) { if (cur-data.first key) { return { iterator(this, cur, idx), false }; } cur cur-next; } Node* inserted new Node(key, value, buckets_[idx]); buckets_[idx] inserted; size_; return { iterator(this, inserted, idx), true }; }返回类型设计成std::pairiterator, bool是和标准库对齐的。第一个值指向已经存在的节点或刚刚插入的节点第二个值表示本次插入是否成功。如果键已存在不需要也不能再插一个直接返回false把已有节点指给调用者。扩容判断写在插入之前用size_ 1和当前桶数乘负载因子比较。这里刻意在插入前判断保证插入完成后负载因子一定不会超过阈值。扩容后桶数翻倍执行一次rehash原来的桶数组被替换成新的大数组。新节点采用头插法直接放在桶链表最前面也就是new Node(key, value, buckets_[idx])把旧表头作为新节点的next再把buckets_[idx]更新为新节点。头插的好处是O(1)而且新插入的元素通常很快会被再次访问放链表头部能少走几步。4.3 find和operator[]读数据也有门道查找的逻辑和插入前半部分几乎一致计算桶号沿链表比较键。iterator find(const Key key) { size_t idx bucket_index(key); Node* cur buckets_[idx]; while (cur) { if (cur-data.first key) { return iterator(this, cur, idx); } cur cur-next; } return end(); }找不到就返回end()和标准库一致。这里哈希表的平均查找复杂度是O(1)但链表比较这个动作不可避免。所以哈希函数质量直接决定链表平均长度也就决定了查找性能。operator[]的语义值得单独讲一下。它用来既读又写比如scores[alice] 90。但标准库规定如果用operator[]访问一个不存在的键会自动插入该键并返回默认值的引用。所以我实现时直接复用insert传入一个默认构造的ValueValue operator[](const Key key) { std::pairiterator, bool result insert(key, Value()); return result.first-second; }这里隐含一个要求Value类型必须默认可构造否则编译不过。如果你写一个HashMapstring, vectorintvector可以默认构造没问题但如果Value是个没有默认构造函数的自定义类就只能用insert而不能用operator[]。4.4 erase最考验基本功的地方删除逻辑直接对应前面3.4讲的前驱问题。我把代码写出来你看它怎么处理删除桶头和删除非桶头两条分支bool erase(const Key key) { size_t idx bucket_index(key); Node* cur buckets_[idx]; Node* prev nullptr; while (cur) { if (cur-data.first key) { if (prev nullptr) { buckets_[idx] cur-next; } else { prev-next cur-next; } delete cur; --size_; return true; } prev cur; cur cur-next; } return false; }遍历时用一个prev指针记录前驱。找到目标节点后判断prev nullptr——如果为空说明目标就是这个桶的链表头桶头必须更新为cur-next否则把前驱的next跨过目标节点指向目标节点的next。两种情况的本质都是让链表的上一环绕过目标节点只不过桶头的上一环是桶数组本身不能不用特殊方式处理。删除后要delete cur并--size_。返回bool表示是否真的删掉了。这套逻辑你修为能半小时正确写出来的程度手写哈希表的半条腿就算落地了。4.5 iterator跨桶遍历的细节标准库容器的遍历是最能证明实现自洽的部分。哈希表的迭代器逻辑是从某个桶的链表头出发先顺着链表走链表走到头就要跳到下一个非空桶继续。class iterator { private: HashMap* map_; Node* node_; size_t bucket_; public: iterator(HashMap* map, Node* node, size_t bucket) : map_(map), node_(node), bucket_(bucket) {} std::pairconst Key, Value operator*() const { return node_-data; } std::pairconst Key, Value* operator-() const { return node_-data; } iterator operator() { if (node_) { node_ node_-next; if (node_) return *this; } bucket_; while (bucket_ map_-buckets_.size()) { node_ map_-buckets_[bucket_]; if (node_) break; bucket_; } return *this; } iterator operator(int) { iterator old *this; (*this); return old; } bool operator(const iterator other) const { return map_ other.map_ node_ other.node_ bucket_ other.bucket_; } bool operator!(const iterator other) const { return !(*this other); } };operator是迭代器最容易写错的地方。先试着往前走当前桶的链表一步如果走完链表发现node变成nullptr说明这个桶已经空了接下来桶号自增继续找下一个非空桶。bucket_到达buckets_.size()时停下来node保持nullptr这就是end()。迭代器要持有map_指针因为跳到下一个桶时需要访问map内部的桶数组。前向迭代器语义足够了不实现反向迭代器这是教学简化。4.6 完整源码和简单测试把上面所有部分拼起来加上构造函数、析构、reserve、begin、end和桶号计算就是一份可以编译运行的手写哈希表。完整代码如下。#include vector #include utility #include functional #include iostream template typename Key, typename Value, typename Hash std::hashKey class HashMap { private: struct Node { std::pairconst Key, Value data; Node* next; Node(const Key key, const Value value, Node* n nullptr) : data(key, value), next(n) {} }; std::vectorNode* buckets_; size_t size_ 0; float max_load_factor_ 0.75f; Hash hasher_; size_t bucket_index(const Key key) const { return hasher_(key) % buckets_.size(); } public: class iterator { private: HashMap* map_; Node* node_; size_t bucket_; public: iterator(HashMap* map, Node* node, size_t bucket) : map_(map), node_(node), bucket_(bucket) {} std::pairconst Key, Value operator*() const { return node_-data; } std::pairconst Key, Value* operator-() const { return node_-data; } iterator operator() { if (node_) { node_ node_-next; if (node_) return *this; } bucket_; while (bucket_ map_-buckets_.size()) { node_ map_-buckets_[bucket_]; if (node_) break; bucket_; } return *this; } iterator operator(int) { iterator old *this; (*this); return old; } bool operator(const iterator other) const { return map_ other.map_ node_ other.node_ bucket_ other.bucket_; } bool operator!(const iterator other) const { return !(*this other); } }; HashMap() : buckets_(8, nullptr) {} ~HashMap() { clear(); } HashMap(const HashMap) delete; HashMap operator(const HashMap) delete; size_t size() const { return size_; } bool empty() const { return size_ 0; } void clear() { for (Node* head : buckets_) { Node* cur head; while (cur) { Node* next cur-next; delete cur; cur next; } } buckets_.assign(buckets_.size(), nullptr); size_ 0; } void reserve(size_t expected_elements) { size_t need static_castsize_t(expected_elements / max_load_factor_) 1; if (need buckets_.size()) { rehash(need); } } void rehash(size_t new_bucket_count) { std::vectorNode* new_buckets(new_bucket_count, nullptr); for (Node* head : buckets_) { Node* cur head; while (cur) { Node* next cur-next; size_t idx hasher_(cur-data.first) % new_buckets.size(); cur-next new_buckets[idx]; new_buckets[idx] cur; cur next; } } buckets_.swap(new_buckets); } std::pairiterator, bool insert(const Key key, const Value value) { if (size_ 1 static_castsize_t(max_load_factor_ * buckets_.size())) { rehash(buckets_.size() * 2); } size_t idx bucket_index(key); Node* cur buckets_[idx]; while (cur) { if (cur-data.first key) { return { iterator(this, cur, idx), false }; } cur cur-next; } Node* inserted new Node(key, value, buckets_[idx]); buckets_[idx] inserted; size_; return { iterator(this, inserted, idx), true }; } iterator find(const Key key) { size_t idx bucket_index(key); Node* cur buckets_[idx]; while (cur) { if (cur-data.first key) { return iterator(this, cur, idx); } cur cur-next; } return end(); } Value operator[](const Key key) { std::pairiterator, bool result insert(key, Value()); return result.first-second; } bool erase(const Key key) { size_t idx bucket_index(key); Node* cur buckets_[idx]; Node* prev nullptr; while (cur) { if (cur-data.first key) { if (prev nullptr) { buckets_[idx] cur-next; } else { prev-next cur-next; } delete cur; --size_; return true; } prev cur; cur cur-next; } return false; } iterator begin() { for (size_t i 0; i buckets_.size(); i) { if (buckets_[i] ! nullptr) { return iterator(this, buckets_[i], i); } } return end(); } iterator end() { return iterator(this, nullptr, buckets_.size()); } }; int main() { HashMapstd::string, int scores; scores[alice] 90; scores[bob] 85; scores[carol] 78; auto [it, ok] scores.insert(alice, 95); if (!ok) { std::cout alice already exists, value it-second std::endl; } for (auto iter scores.begin(); iter ! scores.end(); iter) { std::cout iter-first : iter-second std::endl; } scores.erase(bob); std::cout after erase, size scores.size() std::endl; return 0; }这里我禁用了拷贝构造和赋值操作因为它们对指针容器的默认行为是浅拷贝会让两个对象指向同一批节点析构时双重释放。真实生产环境的版本应该实现深拷贝或者移动语义本文为了专注核心逻辑做了简化特此说明。5. 常见问题与调优自定义类型、字符串哈希和性能实测5.1 自定义类型放入哈希表两条硬性原则把自定义类型当键是使用哈希表时最常遇到的需求。这里一定要守住两条原则。第一条是强制原则相等的对象哈希值必须相等。比如你定义一个Student结构两个Student只要name和id相同就认为相等那么它们的哈希值必须一样。否则插入一个对象后再用相等的另一个对象去find算出来的桶号不同根本找不到。这是哈希表正确性的基石。第二条是经验原则尽量让哈希值分布均匀。很多人图省事直接对某个字段做哈希容易出现大量对象集中到少数桶里的问题。一个常用的组合技巧是把多个字段的哈希值混合起来类似Boost库里的hash_combine思路struct Student { std::string name; int id; bool operator(const Student other) const { return name other.name id other.id; } }; struct StudentHash { size_t operator()(const Student s) const { size_t h1 std::hashstd::string{}(s.name); size_t h2 std::hashint{}(s.id); return h1 ^ (h2 0x9e3779b9 (h1 6) (h1 2)); } };那个0x9e3779b9是黄金分割比例的32位表示用在混合两个哈希值时能避免简单异或导致的对称性问题。你用的时候把StudentHash作为第三个模板参数传给HashMap即可。5.2 字符串哈希FNV-1a等靠谱方案字符串作为哈希表的键出现频率高得吓人。直接使用std::hashstd::string没问题但如果你自己实现哈希函数我推荐FNV-1a。它简单、速度快、散布效果好在很多标准库输出重定向、文件路径缓存场景里被广泛使用。size_t fnv1a(const char* data, size_t len) { size_t hash 14695981039346656037ULL; // 64位偏移基数 for (size_t i 0; i len; i) { hash ^ static_castunsigned char(data[i]); hash * 1099511628211ULL; // 64位素数 } return hash; }它的核心操作只有两步异或当前字符乘以一个固定大素数。每一步都在让整个哈希值发生扰动最终把每个字符的信息扩散到所有位上。注意这里强制把char转成unsigned char再异或是为了避免有符号char对高位的影响这是字符串哈希很容易被忽略的隐蔽细节。实际替换到HashMap里很简单把Hash模板参数传成hashstring的自定义仿函数或者直接让Key类型自己提供哈希专门函数。写测试时你会发现FNV-1a对短字符串的哈希速度比某些重量级加密哈希快一个数量级关键在于它循环内部没有复杂运算。5.3 实测手写版和unordered_map差多少我拿刚才这份代码在开启-O2优化后简单测了一下插入100万个随机的uint64_t键然后再逐个查找一遍。结论是手写版和libstdc的std::unordered_map差距很小大概率在个位数百分比以内。因为核心结构本来就和标准库是同一类设计——链地址法、按负载因子扩容、桶数组加链表。但有几个变量会影响结论测试时一定要控制住。第一是reserve策略预先reserve足够的空间可以消除扩容带来的波动。上面的代码里我的reserve语义是按元素数量预留先算出需要的桶数再扩容和标准库一致不做reserve的话测试结果会有明显噪声。第二是哈希函数两边都使用std::hash时公平。第三是迭代器遍历手写哈希表时桶越多越可能跳过空桶遍历开销略高但插入和查找核心影响不大。手写版最大优势在于你可以针对具体场景魔改。比如我知道键都是连续整数就可以直接把哈希函数省掉用键本身当桶号的一部分又比如我知道只插入不删除可以把erase相关的逻辑全部剥掉。这种减负能力是黑盒的unordered_map给不了你的。5.4 我踩过的四个坑内存、迭代器、reserve、误用自己动手写哈希表最大的收获来自踩坑。我复盘一下写这个版本时遇到的几个典型问题希望你避开。第一个是内存泄漏。早期版本忘了写析构函数或者写完析构却忘了在clear里逐个delete节点结果是程序运行过程中内存只涨不降。哈希表持有大量堆节点不手动管理必漏无疑。写类时一定要第一时间确认谁负责delete在哪个函数里delete析构路径覆盖不覆盖所有分支第二个是迭代器失效。链地址法下扩容会把所有桶重新分配所以扩容后所有迭代器全部失效删除一个节点后指向该节点的迭代器失效但指向同桶其他节点的迭代器仍然有效。这和vector、deque这种连续内存容器的失效规则完全不一样面试常考。第三个是reserve的误用。有些人直接把reserve(n)理解成把桶数组扩到n个结果真正插入n个元素时触发多次扩容开销反而更大。标准库的reserve语义是预留能容纳n个元素而不rehash的空间我实现的版本也照这个语义处理先按负载因子把元素数换算成桶数。使用时要注意区分这两种表述。第四个是operator[]误用。很多人手写哈希表时只提供find后来又为了省事加上operator[]结果在查一下某个键在不在的代码里不小心用下标访问把一个不存在的键插入成了默认值数据凭空多出一大堆。如果只是判断存在性一定用find不要用operator[]。这一点在真实工程里也是经典教训我见过线上代码因为这个原因搞出大量脏数据。回到整个实现上来我个人最大的体会是哈希表不是一个背一背就懂的数据结构里面每设计细节都和你最终能踩的坑数量直接相关。写一遍、跑一遍、故意写错一遍比看十遍教科书都管用。如果你正在准备面试或者想扎实理解STL容器我建议别只看这段代码而是自己从头敲一遍把桶数量从8改成3把负载因子从0.75改成1.5把头插改成尾插再跑一遍测试你就能清楚看到每个设计决策带来的性能差异和正确性影响。这比记任何八股结论都深刻。