C++哈希表从原理到手写实现：彻底看懂unordered_map的O(1)

哈希表（Hash Table）在C++里的存在感很不均衡：刚学的时候觉得它就是个std::unordered_map，会用就行；等真正遇到性能问题，或者被面试官问一句“为什么unordered_map查找是O(1)”，很多人一下子就卡住了。我前段时间在写一个按用户ID定位会话对象的小组件，数据量从几万涨到上百万之后，用vector线性查找开始肉眼可见地卡顿，换成unordered_map快了一大截，也顺手把哈希表的原理彻底搞明白了一遍。

这篇文章把哈希表从头到尾拆开讲：先弄懂它解决了什么问题、冲突是怎么处理的，然后从零写一个能跑的C++哈希表，插入、查找、删除、扩容一个不落，再拿它跟std::unordered_map做一次实测对比，最后把实战里教材一般不写的坑和调优思路一起梳理出来。适合正在学C++数据结构的人、准备面试的朋友，以及那些用了很久unordered_map却一直想深入一层的开发者。

1. 哈希表登场前：从“按下标找”到“按键找”

1.1 数组为什么能做到O(1)

要理解哈希表，得先理解数组。数组之所以访问快，是因为它的物理存储就是一段连续内存。假设数组首地址是base，每个元素占sizeof(T)字节，那么a[i]的地址就是base + i * sizeof(T)，一次乘法和一次加法就拿到了目标位置，整个过程跟数组里有多少元素完全无关，这就是O(1)的来历。

但数组有个前提：下标必须是整数，而且最好是连续且规律的。现实问题里要查找的键往往不是整数，或者说是整数但跨度很大。比如用户ID从100000001到999999999，中间大量空缺；再比如按用户名查找，用户名是字符串。这时候强行用数组，只能开一个上亿的数组然后大部分空着，或者老老实实遍历。遍历到十万级数据就开始难看了，百万级基本就是灾难。

1.2 哈希函数：给任意键算出一个“虚拟下标”

哈希函数的任务，就是把“键”变成一个整数，再把整数压缩到桶数组范围内。用公式表达就是：

index = hash(key) % bucket_count

其中hash(key)返回一个无符号整数，取模把范围压缩到0到bucket_count - 1之间。C++标准库里std::hash就是这个入口：std::hash<int>对整数直接返回原值，std::hash<std::string>会把字符串按某种加权方式聚合成一个数。只要这个函数是确定性的，同一个键永远得到同一个下标，查找就能复现定位。

从使用者的角度看，哈希表就像一个“升级版数组”：你不用关心键到底是什么类型，哈希函数帮你把任意键翻译成数组能用的下标。这正是哈希表的核心思想。

1.3 冲突为什么躲不掉：鸽笼原理和退化风险

这里有个关键问题：键的种类远比桶的数量多。把任意多的键塞进有限个桶里，必然有至少一个桶要装多个键，这就是鸽笼原理。所以哈希表从设计上就要允许桶里挂多个元素，而不是追求“一个键一个位置”。

理想情况是每个桶的元素尽量少，最坏情况是全部挤进一个桶，此时哈希表就退化成了链表，查找O(n)。这也是哈希表被称为“平均O(1)、最坏O(n)”的原因。面试时被问到这个问题，能答出鸽笼原理和冲突处理，基本就能过关。

2. 哈希函数与冲突处理：决定哈希表性能的两根支柱

2.1 一个“好”的哈希函数，标准其实不高但很难定

判定哈希函数好不好，我习惯看三件事：计算够不够快、分布够不够均匀、同一个键的结果稳不稳定。“快”不要理解成绝对时间短，而是相对于你要查询的数据量来说不能喧宾夺主。“均匀”是说不能让某几个桶特别长。举个例子：如果键都是整数且都是偶数，你直接用key % 4，结果只有0和2，一半桶空一半桶特别长，这就是典型的劣质分布。“稳定”是硬要求，同一个键两次调用结果必须一样，否则查找就没法复现。

常见的字符串哈希做法是：从第一个字符开始，每次h = h * 31 + ch。乘31是个经典选择，因为31是素数且编译器能优化成移位减法的形式，速度快。这个思路放到任何类型上都成立：组合各个部件的哈希值，再让它们互相影响。

2.2 两种主流冲突处理方案：拉链 vs 开放寻址

冲突处理有两个大流派。

拉链法（Separate Chaining）是每个桶后面挂一个链表，冲突的元素都进这个桶的链表。STL的std::unordered_map用的就是拉链法。优点：实现简单，删除就是链表常规删除，扩容也好处理。缺点：节点分散在内存各处，Cache不友好，多一个next指针的内存开销。

开放寻址法（Open Addressing）是不额外挂链表，冲突了就在桶数组内部往后探测，直到找到空位。线性探测就是看下一个位置，不行再看下一个。Python的dict、早期Java的HashMap底层本质上都跟开放寻址沾边。优点：元素存在连续数组里，Cache友好。缺点：删除非常麻烦，直接清除某个位置会把后面探测链条上的元素“打断”，导致明明存在的元素却查不到，所以必须用墓碑（tombstone）标记逻辑删除。

这两个方案我用一个表格对比一下：

对新手来说，我强烈推荐先写拉链法，我自己手写哈希表也选择拉链法。原因很直接：开放寻址的删除逻辑处处是陷阱，调试起来非常痛苦；拉链法至少能让你把注意力放在核心原理上。

2.3 负载因子与扩容：0.75是怎么来的

负载因子就是size / bucket_count，即每个桶平均装了多少个元素。0.75这个数字不是拍脑袋，是空间和时间的长期折中。负载因子越高，链越长的概率越大，查找越慢；越低，空桶越多，内存浪费越严重。0.75意味着平均每个桶0.75个元素，大部分桶长度为0或1，冲突概率比较低，同时内存占用也没到离谱的程度。

扩容的时机通常是插入前检查：如果当前负载因子超过阈值，先把桶数翻倍，把所有旧节点重新哈希挂进新桶，再执行插入。这个动作叫rehash。单次rehash确实是O(n)，但因为桶数翻倍后要过很久才会再次触发，平摊下来每个元素只付出常数级成本，所以哈希表插入的均摊复杂度依然可以认为是O(1)。这也是面试里常问“为什么扩容后的均摊复杂度还是O(1)”的标准答案。

2.4 桶数选2的幂还是素数：一个容易被忽略的细节

取模运算符其实挺贵的。桶数选2的幂时，index = hash & (bucket_count - 1)，一次位运算就搞定，比取模快。代价是哈希结果只有低位参与映射，如果键的低位有规律，容易聚集。举个极端例子：键全是4的倍数，桶数是8，所有键都落在0号桶，直接退化成链表。

STL的unordered_map在libstdc++里默认用一组素数作为桶数，目的就是用“不整除”来分散那些与素数没有公共因子的键，代价是rehash时求模比位运算贵一点。我的自研实现为了演示方便用2的幂，但会在hash()里加一个位混合步骤，先把哈希值的低质量低位搅匀，再用位运算取下标。

3. 从零手写一个哈希表：完整实现与代码拆解

3.1 结构设计：为什么选vector<Node*> + 手写链表

我选择vector<Node*>作为桶数组，Node是链表节点。用vector的原因很简单：扩容时移动的是指针，不会移动节点，所以rehash之后，指向元素节点的指针和引用依然有效。手写链表而不是std::list，是为了把next指针暴露出来，删除时可以直接改指针，也方便讲清楚rehash时节点是怎么“搬家”的。

类的核心成员就三样：

struct Node { Key key; Value value; Node* next; }; std::vector<Node*> buckets_; // 桶数组，每个元素是链表的头指针 size_t size_ = 0; // 当前存放的元素个数 double maxLoadFactor_ = 0.75; // 扩容阈值

3.2 插入、查找、删除的关键细节

插入的逻辑是：先检查负载因子，需要就rehash；再算出下标；然后在对应桶的链表里查重，如果key已经存在就返回false；不存在就头插一个新节点。头插法是O(1)操作，比尾插快，代码也简洁。但注意：插入前必须扫描整条链确认key不存在，允许重复key的话，find会返回第一个遇到的节点，行为就不可控了。

查找返回Value*而不是Value。这样找不到时可以返回nullptr，省去额外状态判断，调用方拿到指针先判空再用，这是C++容器常用的做法。

删除有一个很实用的小技巧：单向链表删除需要记前驱节点，头节点又要单独处理，很啰嗦。干脆用二级指针：

Node** pp = &buckets_[index]; while (*pp) { if ((*pp)->key == key) { Node* victim = *pp; *pp = victim->next; delete victim; --size_; return true; } pp = &(*pp)->next; }

pp先指向头指针的地址，如果删的是头节点，*pp赋值就相当于修改buckets_[index]本身；如果删的是链中节点，*pp赋值相当于修改前驱节点的next。两种情况统一处理，不用特判，代码非常干净。

3.3 rehash的实现与所有权转移

扩容的核心不是重新new节点，而是把旧节点挨个摘下，重新计算下标，头插进新桶。整个过程中节点对象一直存在，只是next指针变了。关键代码是一个两层循环：

void rehash(size_t newBucketCount) { std::vector<Node*> newBuckets(newBucketCount, nullptr); for (Node* head : buckets_) { while (head) { Node* next = head->next; size_t index = hash(head->key) % newBucketCount; head->next = newBuckets[index]; newBuckets[index] = head; head = next; } } buckets_.swap(newBuckets); }

很多人第一次看会疑惑：swap之后，newBuckets不是拿着旧桶数组吗？它析构时会不会把节点也误删？不会。vector<Node*>析构只释放指针数组本身，不会去delete指针指向的Node。此时所有节点都已经挂到新桶上了，旧桶只是一个空壳指针数组，随它销毁就行。这个“指针容器和堆对象的所有权分离”思路，写底层数据结构的同学值得反复体会。

3.4 完整代码：一个可直接运行的HashTable类

下面给出完整实现。为了控制篇幅，我把类模板和测试程序分开写，你可以直接复制到一个main.cpp里编译运行。

#include <iostream> #include <vector> #include <functional> template <typename Key, typename Value> class HashTable { public: explicit HashTable(size_t bucketCount = 16) : buckets_(bucketCount, nullptr), size_(0) {} ~HashTable() { clear(); } HashTable(const HashTable&) = delete; HashTable& operator=(const HashTable&) = delete; bool insert(const Key& key, const Value& value) { if (loadFactor() >= maxLoadFactor_) { rehash(buckets_.size() * 2); } size_t index = hash(key) % buckets_.size(); for (Node* cur = buckets_[index]; cur; cur = cur->next) { if (cur->key == key) { return false; } } buckets_[index] = new Node(key, value, buckets_[index]); ++size_; return true; } Value* find(const Key& key) { size_t index = hash(key) % buckets_.size(); for (Node* cur = buckets_[index]; cur; cur = cur->next) { if (cur->key == key) { return &cur->value; } } return nullptr; } bool remove(const Key& key) { size_t index = hash(key) % buckets_.size(); Node** pp = &buckets_[index]; while (*pp) { if ((*pp)->key == key) { Node* victim = *pp; *pp = victim->next; delete victim; --size_; return true; } pp = &(*pp)->next; } return false; } size_t size() const { return size_; } size_t bucketCount() const { return buckets_.size(); } double loadFactor() const { return static_cast<double>(size_) / buckets_.size(); } void clear() { for (Node* head : buckets_) { while (head) { Node* next = head->next; delete head; head = next; } } std::fill(buckets_.begin(), buckets_.end(), nullptr); size_ = 0; } private: struct Node { Key key; Value value; Node* next; Node(const Key& k, const Value& v, Node* n) : key(k), value(v), next(n) {} }; std::vector<Node*> buckets_; size_t size_ = 0; double maxLoadFactor_ = 0.75; size_t hash(const Key& key) const { std::size_t h = std::hash<Key>{}(key); // 位混合：把低位信息打散，配合2的幂桶数使用 h ^= h >> 16; h *= 0x45d9f3b; h ^= h >> 16; return h; } void rehash(size_t newBucketCount) { std::vector<Node*> newBuckets(newBucketCount, nullptr); for (Node* head : buckets_) { while (head) { Node* next = head->next; size_t index = hash(head->key) % newBucketCount; head->next = newBuckets[index]; newBuckets[index] = head; head = next; } } buckets_.swap(newBuckets); } };

测试程序：

#include <string> struct Student { std::string name; int score; }; int main() { HashTable<std::string, Student> table; table.insert("Alice", Student{"Alice", 92}); table.insert("Bob", Student{"Bob", 85}); table.insert("Charlie", Student{"Charlie", 78}); Student* s = table.find("Bob"); if (s) { std::cout << "Found: " << s->name << " " << s->score << "\n"; } if (!table.insert("Bob", Student{"Bob", 99})) { std::cout << "Bob already exists, insert rejected\n"; } table.remove("Alice"); std::cout << "size=" << table.size() << " buckets=" << table.bucketCount() << " loadFactor=" << table.loadFactor() << "\n"; for (int i = 0; i < 30; ++i) { table.insert("K" + std::to_string(i), Student{"", i}); } std::cout << "after more inserts: size=" << table.size() << " buckets=" << table.bucketCount() << "\n"; return 0; }

这个类模板支持任意能用std::hash算哈希、能用==比较的键类型。如果键是自定义结构体，需要自己提供哈希和相等判断，后面第5章会专门讲。

3.5 一个容易踩的细节：插入前先扩容

我故意把扩容检查放在插入最前面，而不是插入之后再检查。原因是：插入完成后负载因子通常会略微超限，如果把insert写成“先插入、后检查并扩容”，那么新节点还要经历一次搬家，浪费一次重哈希。先检查再插入，保证插入动作发生时桶容量已经足够，逻辑上更干净。

4. 和std::unordered_map正面刚一次：性能差距究竟在哪

4.1 测试条件与代码

手写实现毕竟是个教学版本，我很想知道它跟std::unordered_map到底差多少，于是做了一组简单测试。环境是Linux + g++，开了-O2优化，数据用伪随机生成的int键，value也是int，分别测10万和100万规模的插入与查找。

测试的核心结构是这样：

const int N = 1000000; std::vector<int> keys(N); uint64_t seed = 12345; for (int& k : keys) { seed = seed * 6364136223846793005ULL + 1442695040888963407ULL; k = static_cast<int>(seed >> 32); } // 分别对自研HashTable和std::unordered_map跑同样的循环 // 插入：for (int k : keys) table.insert(k, k); // 查找：for (int k : keys) table.find(k);

4.2 结果：能打，但差距还是看得见

我这里给一个在我机器上比较典型的量级，换编译器、换机器会有明显浮动，重点看相对趋势：

看到这个结果，我第一反应是“教学版居然还能跟上”。但仔细想，差距其实藏得很深：第一，自研版每次insert都要new一个节点，走通用内存分配器；第二，STL对节点分配、桶数选择、rehash时机有大量细节优化；第三，libstdc++的unordered_map用素数桶列表，对随机整数键的分布更稳健。

4.3 换种玩法：字符串键差距会更明显

如果键改成std::string，差距会进一步拉大。原因很简单：字符串哈希本身要遍历每个字符，这个过程在两次实现里是一样的，但节点分配、桶查找这些开销的比例会放大。实操中如果遇到字符串键特别多的场景，优化方向通常是提前把哈希值缓存下来，或者用更紧凑的存储，而不是一味依赖容器默认配置。

4.4 哈希表和“字典”、std::map到底什么关系

很多从Python转过来的人会把哈希表叫做“字典”，这是命名习惯的问题。Python的dict、Java的HashMap、C++的std::unordered_map，底层核心都是哈希表。C++里还有一个std::map，但它底层通常是一棵红黑树，元素按键的大小有序排列，操作是O(log n)。

一句话总结选择标准：需要按键排序遍历，或者要求稳定的最坏时间复杂度，用std::map；只需要快速按键查找，不在乎顺序，用std::unordered_map或自研哈希表。面试被问“哈希表和字典的区别”，其实就是在问“哈希表和map的区别”：哈希表是一种数据结构，字典/映射是对这种数据结构的抽象命名，两者不是一个层面的概念。

5. 实战里那些教材不会写的坑与调优方向

5.1 自定义类型当键：三个必须提供的部件

把自定义结构体直接塞进unordered_map，编译器会报一长串错误，本质上是缺两样东西：一个哈希函数，一个operator==。std::hash不知道你的结构体怎么算哈希，==也不知道两个结构体怎么算相等。正确做法是给结构体提供operator==，再写一个仿函数或特化std::hash。下面是一个常见示例：

struct Book { std::string title; int year; bool operator==(const Book& other) const { return title == other.title && year == other.year; } }; struct BookHash { std::size_t operator()(const Book& book) const { std::size_t h1 = std::hash<std::string>{}(book.title); std::size_t h2 = std::hash<int>{}(book.year); return h1 ^ (h2 << 1); } }; std::unordered_map<Book, double, BookHash> prices;

注意组合哈希时直接用h1 ^ h2容易出问题，因为同样的两个数交换位置后哈希值不变，Book{"A", 1}和Book{"", 1}？这里影响不大，但更稳妥的做法是让第二个哈希先移位或乘一个大奇数再异或。我这行h1 ^ (h2 << 1)就是一个低成本改进。

5.2 哈希崩塌：当所有键都掉进同一个桶

性能杀手不一定是扩容，而是哈希函数质量崩塌。举个例子：键是连续整数，哈希函数只做key & 7，桶数是8，那么键8、16、24会全部落到0号桶，查找直接退化成链表遍历。哪怕键是随机分布的数，如果哈希结果的高位信息完全被丢弃，照样会聚集。

我在自研版里加了位混合步骤，代价极小但对低位规律性强的键有奇效：

h ^= h >> 16; h *= 0x45d9f3b; h ^= h >> 16;

这段操作在开源项目里非常常见，本质上就是把哈希值的各个区域的信息混合到一起。如果你在公网环境提供接口，还要注意另外一个问题：恶意输入可以故意构造大量相互碰撞的键，把O(1)的哈希表打成O(n)，造成服务卡顿。这也是为什么有些标准库实现会加载随机种子参与哈希计算，目的就是让攻击者无法预测你的桶分布。

5.3 迭代器失效与遍历安全

std::unordered_map的迭代器失效规则很多人记不住，我帮你记住两条。第一，插入操作如果触发了rehash，所有迭代器都会失效，但是指向元素的指针和引用不会失效，因为节点对象本身没有移动。第二，删除元素只会让指向被删元素的迭代器失效。所以遍历中安全插入的做法是：先把要插入的数据收集起来，遍历完成后再统一插入；或者遍历时提前保存下一个迭代器。

这个东西在自研版里也一样：find返回的是Value*，只要不发生clear或删除操作，这个指针一直有效。一旦rehash，指针仍然有效这个特性，其实是链式哈希表相对于开放寻址法的一大优势。

5.4 一份按优先级排序的调优清单

如果项目的哈希表性能已经成了瓶颈，按这个顺序排查通常比较高效：

1. 能预估规模就先reserve。一次预留足够的桶数，避免多次rehash带来的分配和搬移开销。
2. 键是连续小整数，直接用数组模拟哈希表。比如键是用户ID且范围已知，vector直接按下标访问，性能吊打所有哈希表。这是最简单的“哈希表”但也是最快的数据结构。
3. 节点分配多次触发内存申请，考虑内存池。手写版里每次new Node开销不小，如果插入上百万节点，内存分配器会成为明显瓶颈。给节点分配加一个简单的对象池，性能立刻会向std::unordered_map靠拢。
4. 追求极致性能可以换开放寻址的工业级实现。比如absl::flat_hash_map、google::dense_hash_map，它们用连续内存存储元素，Cache友好度远高于链式实现。
5. 字符串键特别多时，在外部缓存哈希值。哈希表每次查找都要重算字符串哈希，如果字符串是长文本，这个开销相当可观。换个思路，先给字符串分配一个稳定ID，哈希表只存整型ID，性能往往有明显提升。

5.5 最后说一点个人体会

写这份自研哈希表的过程，比我预期的要有价值得多。以前用std::unordered_map，我只知道“插入、查找、删除都是O(1)”，但完全没想过负载因子、rehash、哈希质量这些藏在背后的东西。直到数据规模上来、性能出现问题，才意识到容器不是魔法，理解原理才能做出正确的选择。比如遇到字符串键太多的问题，如果你不懂哈希原理，可能就会想着去换一个更高性能的map库，但懂原理之后会先想到缓存哈希值，或者把字符串映射成ID，这些改动往往比换库更有效、更可控。

如果你也在学C++或准备面试，我建议别只停留在“会用unordered_map”这一步，找个周末把手写哈希表这个练习做一遍。代码量不大，但把插入、删除、扩容、位混合这些细节亲手敲一遍，你对哈希表的理解会彻底不一样。