哈希表这玩意，刷题、做工程、看开源代码，基本绕不开它。很多人一开始觉得它神神秘秘，好像是个黑盒，知道能用它做O(1)查找就完事了。但一旦面试问你“冲突怎么解决”，或者让你手写一个支持增删查的哈希表，不少人就卡住了。这篇文章，我就拿最经典的拉链法（链地址法）来拆解，从原理到C++实现，再到我实际调试中踩过的坑，一次性讲透。
先说清楚它能解决什么问题：给定一个key，在O(1)平均时间复杂度内完成插入、查找、删除。适合什么场景呢？去重、词频统计、缓存、建立索引，以及一切需要快速判断“这个东西见没见过”的地方。这篇文章适合刚学数据结构的同学，也适合准备面试、想搞懂底层原理的选手。
1. 哈希表到底在解决什么问题
1.1 从数组查找说起：为什么需要哈希表
要理解哈希表，得先从数组说起。数组最大的优势是按下标访问，时间复杂度是O(1)，原因是内存连续，通过起始地址加上偏移量就能直接算出目标位置。但问题来了——我们实际处理的数据，key通常不是从0开始的连续整数。比如你要存储一批学生信息，用学号做key，学号可能是“20240101”这种，直接拿学号当下标，得开一个上亿长度的数组，显然不现实。
哈希表的思路就是：通过一个哈希函数，把任意类型的key（整数、字符串、对象）映射成一个整数下标，然后存到数组里。这样既保留了数组O(1)随机访问的优势，又不用把数组开到key的取值范围内。一句话总结：哈希表是数组的一种推广，核心武器是哈希函数。
要注意的是，这个映射不能保证一一对应。因为key的空间通常远大于数组容量，根据鸽巢原理，必然存在两个不同的key映射到同一个下标，这就是哈希冲突。所以设计哈希表，本质上是在做两件事：一是设计一个好的哈希函数让数据分布均匀，二是设计一套冲突解决策略。
1.2 两种主流冲突解决思路：开放寻址与拉链法
冲突解决有两大流派。开放寻址法的思路是：既然这个位置被占了，我就按照某种探测序列往后找空位，比如线性探测（依次往后找）、二次探测（按平方步长找）、双重哈希（再用另一个哈希函数计算步长）。它的好处是不需要用额外的指针，空间利用率高，对缓存友好。缺点是删除操作很麻烦，不能真删，只能打标记；而且当装载因子变高时，探测序列会迅速变长，性能断崖式下跌。
拉链法（也就是本文主题）的思路完全不同：每个桶不直接存元素，而是挂一条链表。冲突的元素全部链到同一个桶的链表上。查找的时候，先通过哈希函数找到桶，再沿着链表一个个比较key。它的优点是对装载因子不敏感、实现简单、删除方便，而且特别适合key数量不确定、波动大的场景——哈希表可以动态扩容，链表本身也能吸收一定程度的冲突。
我在实际工程中，绝大多数情况都选拉链法。Java的HashMap、C++的unordered_map底层用的都是“桶数组 + 链表/红黑树”的变体。拉链法的链表退化成O(n)是极端情况，但只要哈希函数均匀，链表长度基本就是个位数，性能完全顶得住。
2. 拉链法的核心设计与数据结构
2.1 整体结构：桶数组与链表的组合
拉链法哈希表的结构可以拆成两层。
第一层是一个数组，通常叫 bucket array（桶数组）或者 table。数组的每个元素是一个链表的头指针（或者说是一个链表节点指针）。
第二层是链表。所有哈希到同一个桶的(key, value)对就挂在对应链表的后面。插入时，算出桶下标后，直接在链表头部插入（时间复杂度O(1)）；查找时，算出桶下标后，遍历链表找key。
你可能会问：为什么插入选头部不选尾部？因为头部插入不需要遍历链表找尾节点，省掉了O(n)的遍历成本。如果你需要保留某种顺序（比如按插入顺序迭代），那才考虑尾插，但常规哈希表不关心这个。
节点结构大体长这样：每个节点包含key、value，以及一个指向下一个节点的next指针。这是最朴素的单向链表版本。如果你要在哈希表上做LRU淘汰、维护访问顺序，就得改用双向链表甚至“哈希表+双向链表”的组合结构。
2.2 哈希函数选型：均匀性是第一原则
哈希函数的好坏直接决定拉链法会不会退化。理想情况下，哈希函数应该满足三点：
- 确定性：同一个key，任何时候计算出的哈希值都必须相同。
- 均匀性：不同key的哈希值尽可能均匀分布在整个取值范围内。
- 高效性：计算不能太慢，否则哈希表反而成了性能瓶颈。
C++里，标准库std::hash为内置类型提供了不错的默认实现。整数类型通常直接返回原值（或者做一点混淆操作），字符串类型则用类似BKDR的算法，逐字节迭代算出一个64位哈希值。工程上，如果默认实现够用，就别自己造轮子——我见过不少人自创哈希函数，结果分布极差，性能比默认实现差一个数量级。
不过有一个细节必须注意：哈希函数的输出通常是一个无符号整数（比如size_t），但桶数组的下标范围是有限的，比如1024个桶。所以拿到哈希值后，需要做一个映射，最常见的做法是对桶数量取模，也就是hash(key) % bucket_count。
取模操作有个坑：如果桶数量是偶数（比如1000、1024），并且哈希值的低位有规律，那么取模结果也会呈现规律性，导致部分桶永远空着，部分桶挤满。解决办法是把桶数量设为质数，比如53、97、193这种。质数能打散公因数带来的规律性，让取模结果更均匀。
2.3 装载因子与触发扩容的时机
装载因子（load factor） = 元素个数 / 桶数量。它衡量的是哈希表的“拥挤程度”。装载因子越大，链表平均越长，查找性能越差；装载因子越小，空间浪费越多。
拉链法的经验阈值是0.75。超过这个值就扩容——申请一个更大的桶数组（通常是原容量的2倍，且取下一个质数），然后重新计算所有元素的哈希值，把它们搬到新数组里。这个过程叫rehash（重哈希）。
为什么扩容后要把每个元素重新哈希一遍？因为桶下标 = hash(key) % bucket_count，而bucket_count变了，算出来的下标也就变了。如果直接复制原数组，所有元素的位置都是错的。也没办法“聪明地”只搬一部分，因为取模运算不是线性映射，每个元素的新位置都得重新算。
我实测过，扩容次数如果控制得好（每次扩容翻倍），每个元素平均只会被搬运约2次，整体均摊复杂度仍然是O(1)。这就是为什么哈希表的插入虽然偶尔会触发O(n)的rehash，但均摊下来依然是O(1)的原因。
3. C++手写一个拉链法哈希表
3.1 节点定义与类骨架
下面我直接给一份精简但完整的C++实现。这个实现覆盖了插入、查找、删除、扩容四个核心操作，同时支持模板key和value，方便你在不同场景下复用。
#include <vector> #include <list> #include <functional> #include <utility> #include <cstddef> template <typename Key, typename Value, typename Hash = std::hash<Key>> class HashMap { private: // 每个桶是一个list，直接用std::list代替手写链表 using Bucket = std::list<std::pair<Key, Value>>; std::vector<Bucket> buckets_; Hash hash_fn_; size_t elem_count_ = 0; static constexpr double kMaxLoadFactor = 0.75; static constexpr size_t kInitBucketCount = 16; public: HashMap() : buckets_(kInitBucketCount) {} size_t size() const { return elem_count_; } bool empty() const { return elem_count_ == 0; } void insert(const Key& key, const Value& value); bool find(const Key& key, Value* out = nullptr) const; bool erase(const Key& key); void clear(); private: size_t bucketIndex(const Key& key) const { return hash_fn_(key) % buckets_.size(); } void rehashIfNeeded(); void rehash(size_t new_bucket_count); };这里你可能会问：为什么不用手写单向链表，而是用std::list？其实都行。手写链表的优点是你能完全控制内存分配和节点结构，面试时也常考；用std::list的优点是少写很多边界判断，不容易出指针错误，工程上代码更安全。面向面试的写法，我会在后面的避坑章节单独讲手写链表版本的关键点。
用std::list还有一个额外的好处：删除节点时不会像vector那样导致元素移动，迭代器也不会失效（erase只让被删元素的迭代器失效）。这点在写LRU Cache这类复合结构时很重要——但那是另一个话题了，先按下不表。
3.2 插入与查找的具体实现
插入逻辑分为两步：先判断是否需要扩容，然后找桶、遍历链表，如果key已存在就更新value，否则在链表头插入新节点。
template <typename Key, typename Value, typename Hash> void HashMap<Key, Value, Hash>::insert(const Key& key, const Value& value) { rehashIfNeeded(); size_t idx = bucketIndex(key); auto& bucket = buckets_[idx]; // 遍历桶链表，检查key是否已存在 for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == key) { it->second = value; // key已存在，更新value return; } } // key不存在，头部插入 bucket.emplace_front(key, value); ++elem_count_; }查找逻辑类似：算桶下标，遍历链表，比较key。
template <typename Key, typename Value, typename Hash> bool HashMap<Key, Value, Hash>::find(const Key& key, Value* out) const { size_t idx = bucketIndex(key); const auto& bucket = buckets_[idx]; for (const auto& kv : bucket) { if (kv.first == key) { if (out) *out = kv.second; return true; } } return false; }这两个函数理解透一个，另一个就通了。核心步骤永远是三件事：哈希取模（定位桶）、链表遍历（定位元素）、key比较（确认目标）。注意，永远不要用value比较来代替key比较，因为不同key可以映射到同一个桶，你必须在链表里找到key完全匹配的节点才算命中。
3.3 删除操作的实现与细节
删除稍微有一点讲究。思路是：找到桶，遍历链表，找到目标节点后erase掉，同时把elem_count_减1。用std::list的erase，传入迭代器即可，不需要手动释放内存。
template <typename Key, typename Value, typename Hash> bool HashMap<Key, Value, Hash>::erase(const Key& key) { size_t idx = bucketIndex(key); auto& bucket = buckets_[idx]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == key) { bucket.erase(it); --elem_count_; return true; } } return false; }这里有个细节：删除后要不要缩容（shrink）？我的建议是常规情况下不做。因为缩容同样需要rehash，代价很高。缩容触发得不好，会导致“频繁扩容、频繁缩容”的抖动现象，反而影响性能。如果你明确知道某段时间后数据量会大幅下降、并且内存紧张，那可以显式调用一个reserve或shrink_to_fit接口手动触发，而不是在erase里自动缩容。
删除还有个边界情况要留意：如果erase发生在rehash之前（同一轮操作里先大量删除再插入），要重新统计元素个数。我的做法是删除不触发缩容，插入前照常用elem_count_判断是否扩容，逻辑就简单多了。
3.4 扩容rehash的正确打开方式
扩容是拉链法哈希表里最容易写错的部分。先看实现：
template <typename Key, typename Value, typename Hash> void HashMap<Key, Value, Hash>::rehashIfNeeded() { double load_factor = static_cast<double>(elem_count_) / buckets_.size(); if (load_factor > kMaxLoadFactor) { size_t new_size = buckets_.size() * 2 + 1; // 保证桶数量是质数（简化版：至少是奇数） while (!isPrime(new_size)) ++new_size; rehash(new_size); } } template <typename Key, typename Value, typename Hash> void HashMap<Key, Value, Hash>::rehash(size_t new_bucket_count) { std::vector<Bucket> new_buckets(new_bucket_count); for (auto& bucket : buckets_) { for (auto& kv : bucket) { size_t new_idx = hash_fn_(kv.first) % new_bucket_count; new_buckets[new_idx].emplace_front(kv.first, kv.second); } } buckets_.swap(new_buckets); }rehash的核心逻辑我再说一遍：新建更大的桶数组，遍历旧数组的每个桶，再遍历桶里的每个节点，用新容量重新计算哈希下标，把节点插入新桶。这里可以用std::list::splice把节点“移动”过去，避免拷贝节点，但我上面用值拷贝是为了让代码更直白，性能和可读性的取舍看你的场景。
扩容后，旧数组会被析构，所有链表的节点也会随之释放。如果你在外部保存了指向某个节点的裸指针或迭代器，扩容后全部失效——这点和std::vector扩容时迭代器失效的逻辑类似，但注意哈希表的扩容是重排所有位置，不是简单搬一段连续内存，所以失效范围是全量，不是end()之后的半段。实际工程里，如果对迭代器稳定性有要求，得选择std::unordered_map这类自带单元素引用稳定性的容器，或者改用基于节点的容器。
4. 实操中的优化技巧与避坑经验
4.1 哈希函数设计：从std::hash到自定义类型
我见过很多人在自定义类型上栽跟头。比如你有一个结构体：
struct Student { std::string name; int id; bool operator==(const Student& other) const { return name == other.name && id == other.id; } };如果你想让Student作为哈希表的key，直接写HashMap<Student, int>会编译失败，因为std::hash没有为Student提供特化。你必须自己提供一个哈希对象，或者给std::hash做特化：
struct StudentHash { size_t operator()(const Student& s) const { std::hash<std::string> h1; std::hash<int> h2; return h1(s.name) ^ (h2(s.id) << 1); } };这里有个常见的弱实现：直接把哈希值异或到一起。如果两个字符串相同但id不同，h1(s.name) ^ (h2(s.id) << 1)大概率还是能区分的；但如果两个字段的哈希值高度相关，异或的结果可能集中在某个范围，导致分布不均。更好的做法是采用类似boost::hash_combine的方式，把上一个哈希值乘以一个质数常量再加新哈希值：
size_t seed = h1(s.name); seed ^= h2(s.id) + 0x9e3779b9 + (seed << 6) + (seed >> 2);这个魔数0x9e3779b9来自黄金分割比率，作用是让哈希值在混合时均匀“打散”。我自己用下来，这种混合方式分布效果比纯异或好很多，尤其是在桶数量不多的情况下。
4.2 桶数量用质数还是2的幂？我的实际测试
业界有一个争论：桶数量到底用质数好，还是用2的幂好？
用2的幂（比如1024、2048）的好处是取模可以用位运算代替，速度极快：hash(key) & (bucket_count - 1)。代价是低位的规律性会直接影响桶分布。如果哈希函数本身足够随机（比如std::hash对所有整数做了一次混淆），低位基本也够随机，那用2的幂问题不大。很多现代哈希表的实现（包括某些版本的libstdc++）就是对内置类型做了高质量的混淆，然后直接用位运算做映射。
但如果你用的是朴素哈希函数（比如整数直接返回原值），用质数容量更安全。举个例子，key全是偶数，容量是1024，那么所有元素都只会落在偶数下标上，奇数下标全部浪费，链表却越长越长。如果容量是1013（质数），奇偶的分布就被打散了。
我个人的经验是：在竞赛刷题场景，直接使用std::unordered_map，默认的hash和容量策略已经足够好；但如果你手写哈希表，在拿不准哈希函数质量的情况下，选质数容量更稳妥。维护一个质数表（从小到大预先生成）也是常见做法。
4.3 手写链表版与std::list版的取舍
如果面试官让你“手写一个HashMap，不允许用标准库容器”，你就得自己写链表节点。
template <typename K, typename V> struct Node { K key; V value; Node* next; }; template <typename K, typename V> class HashMap { Node<K, V>** buckets_; size_t bucket_count_; size_t elem_count_; // ... };手写版本要注意三个坑：
第一个坑是析构。每个桶的链表节点都要逐个delete，不能只delete桶数组。我在刚开始写的时候就在析构上踩过坑——只释放了桶数组，结果一堆节点泄漏。写析构函数的时候，要遍历每个桶，再while(node != nullptr)逐节点释放。
第二个坑是内存分配。每次插入都new一个节点，频繁扩容时会有大量内存分配开销。你可以引入内存池或节点复用，但在教学场景不推荐，先把正确性搞定再说。
第三个坑是拷贝控制。如果你写了析构函数，就必须同时考虑拷贝构造函数和拷贝赋值操作符，否则默认的浅拷贝会导致两个对象共享同一堆节点，析构时双重释放。最简单的做法是把它们delete掉，或者实现深拷贝。工程上我优先推荐delete掉拷贝、只保留移动语义，能规避大量问题。
4.4 实战排查：如何定位哈希表性能劣化
哈希表最烦人的问题不是“运行出错”，而是“运行变慢”。这时候你不能只看接口，要检查内部状态。
第一个排查点：统计装载因子。如果元素很多但桶数量没变，装载因子可能已经膨胀到2甚至3，链表全都老长老长，查找退化。解决办法是强制扩一次容，或者把扩容阈值调低。
第二个排查点：统计桶内链表长度分布。我常用一个小工具函数，遍历所有桶，算出最大链表长度、平均链表长度、空桶比例。如果最大链表长度是几百，而平均只有个位数，说明哈希函数严重不均匀，有“热点”key挤在同一个桶里。常见的热点原因是key的高位规律性强，而哈希函数没有做充分混淆。
第三个排查点：换一个哈希函数试试。C++的std::hash对内置类型有保证，但如果你用了自定义哈希对象，可以从简单的BKDR、FNV-1a、djb2这几个经典字符串哈希函数里换着测。字符串哈希的选择对分布影响极大，比如简单的“把字符ASCII值相加”的哈希，就对变位词极其不友好——所有变位词都会落到同一个桶。
5. 从刷题到工程：拉链法哈希表的应用与边界
5.1 高频面试题的哈希表解法
刷题时哈希表的出场率极高。最经典的“两数之和”（LeetCode 1），朴素解法是两层循环O(n^2)，用哈希表可以把查找从O(n)降到O(1)，整体变成O(n)：遍历数组时，把每个数存入哈希表，同时查“target - 当前数”是否已经在哈希表里。
另一个高频题是“字母异位词分组”（LeetCode 49）。关键点是把每个字符串排序后当作哈希表的key，然后value是一个vector ，把相同key的字符串放进同一组。这里哈希表的key是string，直接用上面的HashMap即可。
高频题“LRU缓存”（LeetCode 146）的教科书解法也是“哈希表+双向链表”：哈希表负责O(1)定位节点，双向链表负责维护访问顺序。哈希表节点的value里存储链表节点的迭代器/指针，这样可以在O(1)时间内把节点移动到链表头部。这个组合思路，如果你只用做过上面的拉链法实现，理解起来会快很多。
5.2 和std::unordered_map的比较与选型建议
很多读者会问：既然标准库已经有unordered_map，我手写这个还有什么意义？
答案在于理解和控制。标准库的unordered_map确实好用，但你无法控制它的桶数量、哈希函数细节、rehash时机。而手写哈希表可以做到以下几点：
- 针对特定数据分布定制哈希函数，显著提升性能。
- 对内存使用做精确控制，比如预分配足够的桶、复用节点。
- 在面试或比赛中，标准库可能不允许用（某些竞赛环境限制STL），或者其实现与你的平台绑定，你无法预知行为。
- 学习和面试价值：讲清楚手写哈希表，能体现你对哈希表底层机制的理解深度，而不是“会用API”。
当然，日常开发里我强烈建议直接用std::unordered_map。它的实现经过长期优化，引入了哈希策略、异常安全、迭代器失效规则等大量细节，自己造轮子很难在短时间内超越它。但如果你要在性能敏感的地方做定制，标准库也提供了扩展能力，比如传入自定义哈希对象、调用reserve预分配桶数、rehash手动调整桶数。
5.3 拉链法的局限性与场景边界
拉链法不是万能的。有几个场景我会主动避开它：
第一个场景是极端追求缓存命中率的场景。链表节点在内存中不连续，每访问一个节点就产生一次cache miss。对这种场景，开放寻址法配合连续存储更友好。比如某些高性能hash map库（google的swiss table）用的就是开放寻址思想。
第二个场景是键值极小但数量极大的场景。比如存几百万个int到bool的映射，如果用拉链法，每个链表节点的指针开销甚至比数据本身还大，内存浪费严重。这种时候可以考虑bitset或开放寻址。
第三个场景是删除频率极高且对延迟敏感的场景。虽然拉链法删除本身是O(1)，但rehash如果触发缩容，会造成周期性的卡顿。如果业务要求极低的p99延迟，建议在非高峰期手动缩容，或者干脆放弃缩容，接受内存占用。
选型永远是权衡，没有银弹。理解拉链法的实现细节，不是为了任何时候都手写它，而是为了在遇到性能问题时，能准确判断瓶颈在哪里，知道该从哪里下手优化。
最后分享一个我在实际项目里用哈希表踩过的教训：别忽略初始化容量。default构造的unordered_map默认桶数很小，当你快速插入大量元素时，rehash会触发很多次，每次都要重新搬运所有元素，耗时可能比插入动作本身还高。实测数据：一次性插入100万条数据，从默认容量开始（触发十几次rehash）比直接reserve(200万)再插入，时间能差出2~3倍。所以，如果预知数据规模，一定先调reserve；这个习惯能帮你省掉大量的隐式rehash开销，比纠结哈希函数选哪个更立竿见影。
