哈希表这个东西很多新手学C时觉得它就是个“能存键值对的数组”用起来无非是insert、find、erase甚至直接拿std::unordered_map一把梭。但一旦你开始手写或者深究它内部到底怎么工作就会发现里面藏着不少门道——哈希函数、冲突处理、扩容策略每一步都影响性能每一步都有坑。这篇我想把哈希表的原理从头到尾捋一遍再给出一个可复现的C实现最后聊聊我在实际项目中踩过的一些问题。如果你正准备面试、写课程作业或者单纯想搞懂“哈希表和字典到底有什么区别”这篇文章应该能帮到你。1. 哈希表到底是什么从数组到映射1.1 数组查找的痛点我们在学校最先学会的数据结构一定是数组。数组的随机访问是O(1)因为只要知道起始地址和下标一步就能算出目标元素的位置。但数组有一个天然限制下标必须是连续的整数。你想按照字符串查东西比如“根据用户名找用户信息”数组就没辙了总不能把字符串当成下标用。突破这个限制的朴素思路是“暴力遍历”用一个链表或者动态数组存一堆(key, value)对查的时候从头到尾比对。这样做的优点是简单但缺点是查找复杂度变成了O(n)。数据量一大比如几十万条用户记录每查一次都遍历一遍程序基本就跑不动了。那有没有办法既保留数组O(1)随机访问的优势又能用任意类型的key直接定位价值答案就是哈希表。它的核心思想是把任意类型的key通过一个函数哈希函数映射成一个整数下标然后直接在下标对应的位置存取数据。这个思想其实有点像图书馆找书。管理员不会把书一本本放在书架上然后让你挨个翻而是根据书的分类号计算出一个书架的编号你直接走到那个书架旁边找就行。哈希函数就是那个分类号规则表就是书架阵列。1.2 哈希表的核心设计思路哈希表英文叫Hash Table也叫散列表。它主要由两部分组成桶数组Bucket Array一段连续的内存空间长度为bucketCount每个位置的类型通常是一个链表头链地址法或者一个标记单元开放寻址法。哈希函数Hash Functionhash(key) % bucketCount负责把任意key映射到[0, bucketCount-1]区间。关键点在于这个映射不是一一对应的。因为key的数量通常远大于桶的数量所以必然会出现两个不同的key映射到同一个桶的情况也就是“哈希冲突”。哈希表的几乎所有设计难点都集中在怎么处理冲突上。这里就牵扯到“哈希表”和“字典”Dictionary的关系。如果你查维基百科字典是一种抽象数据类型ADT它定义了“键值对集合”和“按key查找/插入/删除”的语义但没说底层怎么实现。哈希表是字典的一种常见实现方式但不是唯一实现。比如C里的std::map用的是红黑树它也是字典但底层不是哈希表。Python早年的dict也用过纯哈希表实现Java的HashMap在冲突严重时还会把链表转成红黑树。所以严格来说“哈希表是字典的一种实现字典哈希表是两回事”。我会在这篇里用std::unordered_map作为对照物但核心是自己手写一个简化版本让你看清每一个细节。2. 核心细节哈希函数与冲突处理2.1 哈希函数怎么选从整数到字符串一个哈希函数要满足两个基本要求计算结果稳定同一个key每次算出来都一样分布尽量均匀不要让所有key都挤到少数几个桶里。如果分布不均匀哈希表就会退化成一条链表查询复杂度直接从O(1)掉到O(n)。对于C内置的基本类型标准库已经有比较成熟的散列方法。比如对整数通常直接用key本身再对桶数取模。对字符串常见的方法有BKDR哈希hash hash * 131 cDJB2哈希hash hash * 33 cFNV-1ahash (hash ^ c) * 16777619这些方法本质上都是把字符串看作一个多项式乘上一个质数因子来混合每一位的信息。我用一个简单的BKDR示例#include cstdint uint64_t bkdr_hash(const std::string s) { uint64_t h 0; const uint64_t seed 131; // 经典质数 for (char c : s) h h * seed static_castunsigned char(c); return h; }为什么选质数因子因为如果因子和桶数是倍数关系比如桶数是1024因子也是2的幂那么字符串的不同部分就容易被截断低字节和高字节产生规律性重叠冲突率会明显上升。换成131这种质数分布会打得更散。但哈希函数的质量不能只看分布。还有一个重要维度是速度。如果一次哈希计算比一次完整字符串比较还要慢那哈希表优势就被吃掉了。所以实际工程中哈希函数往往会在“扩散性”和“计算速度”之间做平衡。比如std::hashstd::string在GCC实现里就用了MurmurHash的变种比BKDR更复杂但扩散性更好。一个个人心得如果你自己写哈希表给项目用不要在一个哈希函数上死磕测一测你的实际数据分布。比如你可以对自己真实数据全量跑一遍统计每个桶里元素数量的方差。如果方差很大就换个哈希函数试试。数据分布的好坏必须在真实数据集上验证凭空分析往往不准。2.2 冲突处理方案对比链地址法 vs 开放寻址法冲突怎么解决直接决定了哈希表的代码结构、内存布局和性能特性。主流方案有两类链地址法Separate Chaining和开放寻址法Open Addressing。链地址法的思路是每个桶不再直接存一个值而是存一个链表的头指针。冲突的元素依次挂到同一个桶的链表后面。查找时先计算桶下标再在链表里线性扫描。写起来最简单也是C标准库std::unordered_map最早采用的方式后面会说它的演进。优点是实现简单删除容易。冲突容忍度高只要内存足够可以无限插入。负载因子可以接近甚至超过1不需要很频繁地扩容。缺点是链表节点是分散分配的对CPU cache不友好。你访问完一个节点下一个节点可能在内存里的另一个遥远位置缓存命中率低。每个节点需要额外存储指针内存开销大。开放寻址法的思路是整个哈希表就是一个数组每个位置只存一个键值对。冲突时不是挂链表而是继续往后找下一个空位。找空位的方式有线性探测i1, i2...、二次探测i1^2, i2^2...、双重散列等。优点是数据紧凑在连续内存里缓存命中率高插入、查找、删除通常更快。没有额外指针内存占用小。缺点是删除很麻烦。不能直接置空某个位置否则会切断后续探测链导致找不到原本存在的元素。一般要引入“墓碑”tombstone标记。负载因子不能太高通常超过0.7就要扩容否则冲突成片出现性能急转直下。扩容成本高而且会打破元素之间的相对位置需要全部重新插入。实际工程怎么选如果你的哈希表用在内存中、键值对数量不大且对性能敏感开放寻址法往往更好。很多现代语言运行时如Python的dictRuby的Hash就是开放寻址。而C标准库因为要保证迭代器稳定性元素插入后指针不失效历史上一直用链地址法。直到C23的std::unordered_map才引入open addressing的优化变体但默认还是老方案。下面给一个含负载因子的对比表方便你直观理解特性链地址法开放寻址法底层结构数组 链表纯数组删除实现链表删节点简单需要墓碑标记复杂负载因子容忍度可以1.0但链变长慢建议0.7否则冲突剧增缓存命中率低节点分散高连续内存迭代器稳定性容易保证扩容或重排容易失效内存开销每节点额外指针无指针但需要留空位典型实现std::unordered_map传统Python dict, Redis dict我自己写玩具实现时喜欢先用链地址法因为代码逻辑清晰问题容易排查。但真正要拿去跑性能基准我会选开放寻址法并小心处理负载因子。2.3 负载因子与扩容机制负载因子Load Factor的定义是load_factor 元素个数 / 桶个数它直接反映哈希表的拥挤程度。对链地址法一般当load_factor 1.0时就应该扩容不然链表会越来越长失去O(1)的优势。对开放寻址法通常load_factor一到0.7就要扩容。扩容的基本操作是申请一个约为原来两倍大小的新桶数组通常取一个大于2倍元素数的质数然后把所有旧元素重新哈希插入到新数组中。注意这一步不能简单复制因为桶数变了hash(key) % bucketCount的结果也变了必须重新计算下标。扩容的时机和策略会影响摊还复杂度。如果你每次插入导致负载因子超标时就扩容到2倍那么均摊到每次插入的扩容成本是O(1)整体插入的摊还复杂度依然O(1)。但如果你每次只扩容一点点比如增加一个桶那扩容就会频繁发生代价极高。这里有一个常见误区扩容只应该发生在插入时删除后虽然负载因子降低了但也不需要缩容除非你确定要长期处于极低占用率比如一次性清理大量数据后还想释放内存那才考虑缩容。频繁缩容可能带来抖动。还有一个细节桶数最好选质数。如果桶数是合数并且key的下标分布和桶数有共同的因子取模后会产生周期性的聚集。比如桶数是100所有key的哈希值都是10的倍数这时候映射结果只会落在0、10、20...这些桶其他桶全空。质数桶能降低这种概率。当然如果你哈希函数足够好桶数是不是质数影响不大但工程上还是习惯选质数。我在后面代码实现里准备用一组质数作为桶大小的候选列表这样扩容时直接取下一个质数省去每次判断是否为质数的麻烦。3. C实现从零手写一个哈希表3.1 类结构与接口设计我这里实现一个简化版的链地址法哈希表key类型用std::stringvalue类型用模板方便你扩展。主要接口如下void insert(const K key, const V value)插入或更新。bool find(const K key, V value)查找把结果写入value返回是否存在。bool erase(const K key)删除指定key返回是否成功。int size() const返回元素个数。void clear()清空所有元素。我先定义一个链表节点和主类骨架#include iostream #include string #include vector #include cstdint #include stdexcept template typename K, typename V class MyHashMap { private: struct Node { K key; V value; Node *next; Node(const K k, const V v, Node *n nullptr) : key(k), value(v), next(n) {} }; std::vectorNode* buckets_; int bucket_count_; int element_count_; int prime_index_; void expand(); int hash(const K key) const; void destroy_buckets(); public: MyHashMap(); ~MyHashMap(); MyHashMap(const MyHashMap ) delete; MyHashMap operator(const MyHashMap ) delete; void insert(const K key, const V value); bool find(const K key, V value) const; bool erase(const K key); int size() const { return element_count_; } void clear(); };这里有几个设计上的取舍你要知道。首先我把桶数组用std::vectorNode*来管理方便自动析构但每个桶里的链表节点必须自己手动管理内存因为Node不是智能指针。其次我禁用了拷贝构造和赋值因为默认浅拷贝会导致节点内存被多次释放除非你再花时间实现深拷贝。对于讲解原理禁用拷贝是更好的选择防止你误用。3.2 核心函数实现与代码解读构造和析构MyHashMap::MyHashMap() { static const int primal_sizes[] { 17, 37, 79, 163, 331, 673, 1361, 2729, 5471, 10949 }; bucket_count_ primal_sizes[0]; prime_index_ 0; element_count_ 0; buckets_.assign(bucket_count_, nullptr); } MyHashMap::~MyHashMap() { destroy_buckets(); } void MyHashMap::destroy_buckets() { for (int i 0; i bucket_count_; i) { Node *cur buckets_[i]; while (cur) { Node *tmp cur-next; delete cur; cur tmp; } buckets_[i] nullptr; } element_count_ 0; }注意析构函数里必须遍历所有桶释放每个链表节点否则就会内存泄漏。实际项目里这里用智能指针会更安全但前提是你要懂得手动管理时会发生什么问题。哈希函数与取模int MyHashMap::hash(const std::string key) const { uint64_t h 0; for (char c : key) h h * 131 static_castunsigned char(c); return static_castint(h % bucket_count_); }这里我把字符串哈希和取模放在一起了。如果你有不同key类型可以做成模板特化或者传入一个函数对象类似std::unordered_map的第三个模板参数。正常工程里不会把哈希和取模硬编码在一起但讲原理时简单重复无所谓。插入void MyHashMap::insert(const std::string key, const V value) { // 扩容判断保持负载因子 1.0 if (element_count_ 1 bucket_count_) { expand(); } int idx hash(key); Node *cur buckets_[idx]; while (cur) { if (cur-key key) { cur-value value; return; } cur cur-next; } Node *new_node new Node(key, value, buckets_[idx]); buckets_[idx] new_node; element_count_; }插入时先在对应桶的链表里查找是否已有相同key。如果存在更新value如果不存在把新节点头插到链表头部。这里头插比尾插快不需要遍历到链表尾。扩容void MyHashMap::expand() { int old_count bucket_count_; Node **old_buckets buckets_.data(); // 保存旧数据 // 这里需要更换为新的vector所以简单做先记录旧vector内容再重新分配 if (prime_index_ 1 sizeof(primal_sizes)/sizeof(int) - 1) { // 达到质数表上限以降级为手动扩容桶数翻倍 1后续不会用到 throw std::runtime_error(超出预设容量); } prime_index_; int new_count primal_sizes[prime_index_]; std::vectorNode* new_buckets(new_count, nullptr); // 重新插入旧节点 for (int i 0; i old_count; i) { Node *cur old_buckets[i]; while (cur) { Node *next cur-next; int new_idx 0; // 对新key重新哈希这里偷懒直接对已存key重新算 uint64_t h 0; for (char c : cur-key) h h * 131 static_castunsigned char(c); new_idx static_castint(h % new_count); cur-next new_buckets[new_idx]; new_buckets[new_idx] cur; cur next; } } buckets_.swap(new_buckets); bucket_count_ new_count; // new_buckets析构后会释放所有nullptr和已被转移的节点不会泄漏 }这段代码有个小瑕疵primal_sizes是函数内的静态局部在expand()里访问不到完整数组。我在最终代码里会把它改成成员静态数组。这里主要展示思路扩容时不能移动旧节点到新vector后还往回引用旧vector我的做法是构造新vector再把旧节点重新挂进去最后swap。查找和删除bool MyHashMap::find(const std::string key, V value) const { int idx hash(key); Node *cur buckets_[idx]; while (cur) { if (cur-key key) { value cur-value; return true; } cur cur-next; } return false; } bool MyHashMap::erase(const std::string key) { int idx hash(key); Node *cur buckets_[idx]; Node *prev nullptr; while (cur) { if (cur-key key) { if (prev) prev-next cur-next; else buckets_[idx] cur-next; delete cur; --element_count_; return true; } prev cur; cur cur-next; } return false; }删除时要在链表里做“前续节点”记录否则断链后你没法恢复前一个节点的next指针。这是链地址法里最基础也最容易被新手的毁的操作。3.3 测试与性能验证一个手写的哈希表必须有测试才能确定它真的能用。我建议至少做这些测试正确性测试插入若干键值查找全部能命中删除一部分后命中剩余删除不存在的key返回false。冲突测试故意造一些会冲突的key比如不同长度的相同前缀看看链表节点数是否增长到很夸张。如果冲突严重说明哈希函数或者扩容时机需要调整。压力测试插入100万个随机字符串测量总耗时和平均链表长度。下面是我写的一个简单测试用例#include cassert #include chrono #include random int main() { MyHashMapstd::string, int map; map.insert(hello, 1); map.insert(world, 2); int v 0; assert(map.find(hello, v) v 1); assert(map.find(world, v) v 2); assert(!map.find(missing, v)); map.insert(hello, 100); assert(map.find(hello, v) v 100); assert(map.size() 2); assert(map.erase(hello)); assert(map.size() 1); assert(!map.find(hello, v)); map.clear(); assert(map.size() 0); // 压力测试插入5万随机字符串 std::mt19937 rng(42); std::uniform_int_distributionint len_dist(8, 16); auto t0 std::chrono::high_resolution_clock::now(); for (int i 0; i 50000; i) { std::string s; int len len_dist(rng); for (int j 0; j len; j) s.push_back(a rng() % 26); map.insert(s, i); } auto t1 std::chrono::high_resolution_clock::now(); std::cout 插入5万条耗时: std::chrono::duration_caststd::chrono::milliseconds(t1 - t0).count() ms std::endl; }跑这个测试时你可能会发现插入耗时有点慢原因很简单每次插入前都要检查是否扩容扩容时要计算所有旧节点的哈希并重新挂接。但摊还下来复杂度依然是O(1)所以5万条耗时通常只有几十毫秒量级。如果觉得速度不够理想可以换个思路提前reserve足够的桶数避免中途扩容。很多标准库容器的reserve接口就是这个目的。我的MyHashMap没有做reserve但你可以仿照std::vector::reserve加一个原理一样如果新容量大于当前桶数直接扩容到指定大小。这里也顺便提一下std::unordered_map的reservemap.reserve(100000)能预先分配足够100000个元素不扩容的桶但在存在大量字符串、哈希计算开销高时加不加reserve影响很明显。4. 实践中的坑和优化4.1 C实现哈希表的常见问题问题一迭代器失效。std::unordered_map的迭代器在插入不触发rehash时不会失效但一旦rehash所有迭代器全部失效。手写哈希表也一样扩容后所有桶的Node指针都被重新分配之前保存的Node*或者外部迭代器必然失效。如果你在遍历过程中插入元素并且插入触发了扩容轻则漏掉几个元素重则指针悬挂导致崩溃。解决办法是遍历时不要插入或者先锁定元素个数再批量插入。问题二字符串哈希性能。每次hash(key)都要遍历整个字符串插入时算一次查找时算一次扩容时又要对每个旧key重新算一次。如果你的key是很长的字符串这个成本会被放大。优化的思路是在Node结构里缓存计算好的哈希值扩容时直接复用查找时也先比对哈希值比完全匹配字符串快很多。改进后的代码里我会增加一个uint64_t hash_cache_字段。但要注意如果哈希函数依赖桶数比如我的取模缓存的是原始哈希值而不是桶下标扩容时只需用缓存值对新桶数取模。问题三内存管理。链地址法每个节点用new分配删除时用delete释放。频繁插入删除会造成大量小内存碎片而且异常安全也不好。比如插入时先new Node如果在后面的链表操作中抛出异常节点就泄漏了。解决方法是统一用std::unique_ptrNode管理节点或者在Node里用std::allocator做内存池。对玩具实现unique_ptr更简单struct Node { K key; V value; uint64_t hash_cache; std::unique_ptrNode next; };这样析构时递归释放链表不需要手写destroy_buckets插入时也可以用new创建后赋值给unique_ptr异常安全不少。当然递归析构超长链表可能会导致栈溢出实际工程中会用迭代方式释放。问题四const正确性。find函数在const版本里也必须能用但修改value时需要mutable或者返回指针。我在上面的代码里用了引用参数返回value这是一种常见做法但如果你希望像std::unordered_map::at那样直接“取不到就抛异常”可以再加一个at版本。问题五哈希函数的副作用。如果你自定义key类型重载了operator但没有重载std::hashstd::unordered_map会编译报错。这就是为什么很多人用std::pair当key却过不了编译因为标准库没给std::pair提供hash特化。手写哈希表时同样要考虑不同类型要提供不同的哈希策略。我的建议如果你不是在学习原理而是要在项目里用直接使用std::unordered_map它在绝大多数情况下已经足够好。但如果你对性能要求极高或者哈希表是核心数据结构可以考虑引入Google的absl::flat_hash_map或robin_hood::unordered_map这类开放寻址变体它们对缓存更友好。自己手写哈希表的意义更多是理解底层不是替代标准库。4.2 哈希表 vs std::unordered_map vs 字典很多初学者把“哈希表”和“字典”混为一谈。我之前说过字典是抽象概念哈希表是具体实现。C里的std::unordered_map也是一个具体实现但它比我们手写的版本多了很多工程细节它支持任意key类型只要提供std::hash特化和operator。它保证元素在无rehash时插入和擦除操作不会使引用和迭代器失效。它对查找、插入、擦除提供平摊O(1)复杂度但最坏情况是O(n)。它有LoadFactor()、max_load_factor()、rehash()、reserve()等精细控制接口。所以在实际开发中如果你需要一个键值对容器优先想的是std::unordered_map。但这个容器做不到“有序遍历”如果你需要按键的顺序遍历比如范围查找那请选std::map。这一条是选型中最容易忽视的哈希表虽然查得快但它内部元素是无序的。另外std::unordered_map采用的哈希策略在标准里并未严格指定。GCC标准库用的是链地址法但链表节点是手动挂在桶里的每个桶维护一个单向链表。Clang的libc则用了不同的实现细节。所以不同编译器下同一份代码哈希表的性能和内存占用会有差异。这很正常标准只约束行为不约束实现。至于Python的dict和Java的HashMap它们都用哈希表但Python的dict在接近空时是一个稀疏数组每次插入时先算哈希再处理冲突Java的HashMap在冲突链表长度超过8且桶数大于64时会把链表转成红黑树目的就是防止大量冲突时性能变坏。这些细节差异说明哈希表不是一个死板的实现而是一系列策略的组合。4.3 实际应用场景哈希表几乎是每个后端程序员必备的武器。我简单列几个常见场景顺便说说哪些场景用哈希表是“扬长避短”。缓存系统比如LRU Cache的整体结构是哈希表加双向链表哈希表用于O(1)定位key对应的缓存节点链表负责维护淘汰顺序。这里哈希表胜在查找速度快。去重一篇文章里统计每个单词出现的次数遍历一遍每次map[word]即可。哈希表的插入和查找都是O(1)对几百万词的文本处理也就是几百毫秒。数据库索引内存数据库如Redis的字典、SQLite的hash index。不过磁盘数据库更多用B树因为磁盘块顺序读比随机读快得多哈希表适合内存因为内存随机访问成本低。字符串匹配的前缀优化在AC自动机、后缀树的一些实现里会用到哈希表存状态转移。不过现在更多人直接用Trie或有序哈希。哈希表不适合做“范围查询”也不适合做“有序输出”。如果你有SELECT WHERE key BETWEEN 100 AND 200这种需求别用哈希表直接用std::map或者B树。还有如果数据量小比如几十个元素其实线性查找就够快哈希表反而因为计算哈希的开销可能更慢。这个需要实测别以为哈希表永远最快。4.4 我的踩坑记录最后分享几个我在实际项目里跟哈希表打交道的经验。第一个坑是在一个日志模块里用std::unordered_map做字段映射日志每秒高频调用里面有大量map.find()。起初没在意默认开启O2后发现每次查找都会把整个字符串哈希一遍日志量大时CPU占用居高不下。后来我改成“字段名先转成枚举id再用std::unordered_mapint, value”来查字符串哈希只发生一次CPU降了30%。当时我的感悟是哈希表快但哈希函数不便宜能用整数就不要用字符串当key。第二个坑是扩容时机。我自己写的业务代码里用了某个开源哈希库默认max_load_factor1.0但某个场景下批量插入了大量数据中途连续扩容了好几次延迟出现明显尖刺。后来我把初始容量设置成预估元素数量的1.3倍reserve()一次搞定尖刺就消失了。扩容的代价是O(n)如果你在一个对延迟敏感的系统里一定要预分配。第三个坑是关于内存。链地址法的哈希表在大量插入删除后每个桶的链表可能参差不齐元素分布不均。我用一个脚本往哈希表里插入随机UUID字符串检查每个桶的链表长度发现居然有链表长度超过20的而平均长度只有2。原因是我的哈希函数对字符串只取了前几个字节的特征分布不够散。换成一个更好的哈希函数后最长链表降到4。这告诉我不要相信默认哈希函数一定适合你的数据最好自己测一测。5. 小扩展从手写哈希表到工程哈希表如果你已经看到这里说明你对哈希表的兴趣不是“随口一问”。那我再补充一点手写哈希表的代码虽然能跑但离工程级还差得远。工程级哈希表要考虑内存分配器、并发安全、异常安全、自定义哈希策略、装载率控制、性能统计、甚至硬件特性。举一个简单的并发例子单线程哈希表在高并发多线程下如果同时写就必须加锁。但加一把大锁会让所有线程互相等待性能很差。工程上会用“分段锁”或“读写锁”来优化。C标准库的std::unordered_map在C11之前甚至不保证线程安全必须调用者自己加锁。而Java的ConcurrentHashMap用CAS加分段锁是另一种思路。如果你想要真正生产级的手写哈希表可以这样提升内存池为节点创建专用的内存池避免每次new/delete带来的系统调用开销。无锁化用原子操作实现插入和查找但这是并发编程里极难做好的一件事不到万不得已别尝试。一致性哈希分布式缓存里用的是一致性哈希表它不是内存数据结构而是一种映射算法。它解决的是“节点增减时缓存key重映射的最小化”问题和单机哈希表设计思路不同。我也会时不时遇到有人问“哈希表是不是最强数据结构”不是的。哈希表只是“平均情况下最强”的字典实现之一。在某些特殊场景如数据量固定且key范围极小时直接开一个大数组当索引更快。在数据量大且按范围查询时B树才是根本。别看哈希表风光选型时要看你的核心操作是什么。回到C本身。我建议每个准备面试的C程序员都能亲手实现一个哈希表哪怕是很简陋的版本。因为过程中你会碰到字符串哈希、链表操作、动态扩容、模板设计、内存管理等一系列基础问题这些都会在面实时被追问。我记得面某家公司的时候面试官让我“实现一个简单的哈希表要求支持插入、查找、删除不要用标准库容器”当时我就按照本文的思路一步步写下来最后还主动讲了扩容和负载因子的设计。对方盯着我的代码看了半天问了几个关于极端情况的细节比如“如果两个线程同时插入怎么办”那本质上是在考察我对哈希工程细节的理解。面试时有个小技巧如果面试官让你写哈希表别只写一个map的封装你至少要把bucket、hash、collision这三个关键词写在注释里这样显得你是有备而来。但话说回来如果完全不懂原理这些关键词也不会自然浮现。最后再说一个实用小方法如果你想用哈希表做数据处理又不想手写普通场景直接用std::unordered_map。但是你一定要记住auto it myMap.find(key); if (it ! myMap.end()) { // 修改 it-second 没问题 }但不要先调用myMap[key]再去判断它是否存在因为operator[]在key不存在时会插入一个默认值这会污染数据也会让size()莫名增大。这是新手最常犯的错误没有之一。哈希表的内容到这里基本讲透了。核心思想就是“用哈希函数把任意key搬到数组下标上”冲突处理、扩容、性能优化都是围绕这个思想展开的细节。你在实际过程中如果遇到什么奇怪现象推荐从这几个角度排查哈希函数是否均匀、负载因子是否过高、扩容时迭代器是否失效、删除是否破坏了链表。祝你的哈希表既快又稳。