刚入行那会儿，我在一个会话管理模块上栽过跟头。当时用动态数组存用户会话，每次校验都要从头遍历一遍，用户量涨到两万出头，接口响应时间从个位数毫秒直接飙到三百多毫秒。后来把存储结构换成哈希表，同一台机器、同一套业务逻辑，响应时间回到三毫秒以内。那次之后我才真正明白，数据结构课本里那句"用空间换时间"不是口号，它能直接换算成服务器账单上的数字。
哈希表（Hash Table），也有人叫散列表，是数据结构里出现频率最高的容器之一。它的核心承诺非常直白：在平均情况下，插入、查找、删除三个操作的代价都是常数级，也就是 O(1)。不管你的数据是一百条还是一千万条，理想状态下定位一条记录所花的时间几乎不变。这个特性让它成为几乎所有编程语言标准库的标配——C++ 的unordered_map、Java 的HashMap、Python 的dict、Go 的map，底层都是哈希表的变体。这篇文章会从"它到底解决了什么问题"讲起，一路拆到哈希函数怎么设计、冲突怎么处理、扩容怎么算账，最后附上两个可以跑起来的完整实现，以及我在真实项目里踩过的坑。不管你是正在准备数据结构期末、考研复试，还是刚工作需要手写一个缓存容器，都能直接拿去用。
1. 哈希表到底是什么：从"找东西"这件事说起
很多人对哈希表的第一印象是"一个会自动去重的字典"，这个理解不算错，但太表层了。要真正搞懂它，得先看清楚在没有哈希表的世界里，我们找一条数据有多费劲。
1.1 数组和链表的查找为什么快不起来
假设你要存 1000 个用户 ID 和对应的昵称，最朴素的做法是塞进数组或者链表。现在要查某个 ID 的昵称，数组只能从头到尾扫一遍，链表更惨，还得跟着指针一跳一跳地走。平均要比较 500 次，最坏 1000 次。数据量翻十倍，比较次数也跟着翻十倍，这就是线性时间 O(n) 的典型特征。
有人会说，那就排好序用二分查找啊，O(log n) 不是挺好吗。确实，二分查找在一千万条数据上也只要 24 次比较，听起来很美。但它有两个前提：一是数据必须保持有序，每次插入新数据都要付出维护有序的代价；二是二分查找只在"能比较大小"的键上成立，像身份证号、UUID、字符串邮箱这类键，排序本身就很别扭。更关键的是，二分查找的 log n 虽然增长缓慢，但它的每一次比较都要访问内存中不同位置的元素，缓存命中率差，实际运行时的常数因子并不小。
我们真正想要的是：能不能不算、不比，直接一步跳到目标位置？哈希表给出的答案是——能。
1.2 用空间换时间：哈希表的核心思路
哈希表的基本想法可以用一个生活场景说清楚。想象一排 100 个带编号的储物柜，每个柜子只能放一件东西。你拿到一个包裹，包裹上贴着一个号码，你不需要打开任何柜子去翻，直接走到对应编号的柜子前面把它塞进去就行。取包裹的时候也一样，看号码、走到柜子、开门，全程零搜索。
这里的"包裹上的号码"就是哈希值，"100 个柜子"就是桶数组（bucket array）。哈希函数负责把任意的键（字符串、整数、对象）映射成一个落在 [0, 99] 范围内的整数，这个整数就是桶的下标。整个结构本质上就是一个数组，数组的下标访问天然是 O(1)，这是哈希表全部性能的来源。
代价是什么？代价是那个"号码"未必唯一。不同的两个键完全可能算出同一个下标，这就是哈希冲突。哈希表这门学问，一半篇幅在讲怎么设计一个好的哈希函数，另一半篇幅在讲冲突了怎么办。理解了这两点，你就理解了哈希表。
1.3 哈希函数、哈希值、桶位：先把三个词的账算清
初学者最容易混淆的就是这三个概念的关系。我用一行伪代码把它们串起来：
桶下标 = hash(key) % 桶数组长度hash(key)是把键转换成一个大整数的函数，这个结果叫哈希值，它是一个可能取遍 32 位甚至 64 位范围的数。直接拿这个数当下标是不行的，因为桶数组没这么大，所以还要再对数组长度取模，得到的才是真正的桶下标。三步走：键 → 哈希值 → 桶下标。
这里有个细节值得注意：不同语言、不同版本的hash函数行为差异很大。Python 里字符串的哈希值每次进程启动都会加一个随机种子，这是为了防止有人构造大量哈希冲突的键来做拒绝服务攻击。Java 的String.hashCode()是确定性的，用 31 作为乘数，所以同样的字符串在任何 JVM 上结果都一样，这个特性偶尔会被用来做跨进程的稳定散列。写代码的时候，如果你需要跨进程、跨语言一致的哈希值，千万不能依赖语言内置的hash()，得自己指定算法。
另外还有一个常被忽略的点：哈希表存的是"键值对"，比较的时候用的是键的相等性，不是哈希值的相等性。两个不同的键哈希值相同，这只是冲突，不代表它们相等。实现里必须再做一次完整的键比较来确认，这一步叫"冲突确认"，少写了就是 bug。我见过有人在自定义结构体做键时只实现了哈希函数忘了实现相等判断，结果查出来的值是别人的，排查了半天才定位到。
2. 哈希函数怎么设计：从除留余数法讲到实战取舍
一个哈希函数好不好，直接决定哈希表的实际性能。设计得烂，再好的冲突处理策略也救不回来——所有元素挤在一两个桶里，哈希表退化成一个链表，O(1) 瞬间变 O(n)。
2.1 几种常见的构造方法
最常用的是除留余数法：h(k) = k % m，m 是桶数组长度。它简单、快，几乎零计算成本，是绝大多数标准库的实现方式。
直接定址法：h(k) = a * k + b，适合键本身分布就连续且范围不大的场景，比如用学号后四位直接做下标。缺点是键的范围一大就浪费空间。
数字分析法：把键的每一位拿出来分析，挑出分布比较均匀的若干位组成下标。比如手机号，前三位是运营商、中间四位是地区，最后四位才是随机性最强的，所以取后四位做哈希效果就好得多。这招在处理固定格式的 ID 时特别好用。
平方取中法：先把键平方，然后取中间几位。平方操作会让原始数字的每一位都影响到中间位，所以分布比较均匀。这个方法在早期的哈希实现里很常见，现在因为要算乘法，用得少了。
乘法散列法：h(k) = floor(m * frac(k * A))，其中 A 取 0.6180339887 附近的黄金分割比。这个方法的妙处在于它对 m 的取值不敏感，m 取什么值分布都还不错，不像除留余数法那么依赖 m 选择得当。
字符串专用：经典的 BKDR Hash、DJB2、FNV-1a 都属于这一类，核心都是h = h * seed + ch逐字符滚动。种子选得好坏影响很大，比如 BKDR 的常用种子是 131、1313、13131 这类质数。
2.2 好哈希函数的四条标准
实际选型的时候，我会用这四条去衡量一个哈希函数：
第一，计算要快。哈希函数在每次插入和查找时都会被执行，它自己不能成为瓶颈。像 SHA-256 这种加密哈希，分布性无可挑剔，但一次计算要几百纳秒，放到高频读写的容器里完全是灾难。标准库用的都是几纳秒级别的轻量算法。
第二，分布要均匀。理想情况下，每个桶里的元素数量应该差不多。如果有 1000 个元素和 1000 个桶，最好每个桶 1 个；如果出现某个桶装 50 个、另一个桶空着，查找这些长链就是额外成本。
第三，确定性。同一个键每次算出来的结果必须一样，否则存进去就找不回来了。这里要特别注意浮点数——NaN不等于自身，用它做键会出问题；还有包含指针的结构体，指针值在不同运行时期不同，做键会导致不可重现。
第四，雪崩效应。键只改一个字符，哈希值应该有大量位发生变化。反例是h(k) = k % 10，键从 100 变成 101，哈希值只从 0 变到 1，变化太小，容易形成聚集。实战中常用的做法是在最后加一轮混淆，比如 Java 8 的HashMap会把哈希值的高 16 位异或到低 16 位，就是为了让高位的信息也能参与下标计算。
2.3 为什么模数喜欢用质数：一个能算出来的解释
"取模要用质数"这句话几乎每本数据结构书都会写，但很少解释清楚。我用一个具体例子推一遍。
假设桶数组长度 m = 10，所有键都是偶数：2、4、6、8、10、12、14、16、18、20。那么k % 10的结果只会是 0、2、4、6、8 这五个桶，另外五个桶永远空着。更糟的是，如果键都是 10 的倍数，那么所有键全落到 0 号桶，哈希表彻底退化成链表。
问题的根源在于：键的集合和 m 存在公共因子 d > 1，那么只有 m/d 个桶会被真正用到，其余桶形同虚设。m 取值越"合数"，能被它整除的因子越多，踩坑的概率越高。而质数只有 1 和自身两个因子，除了键全是该质数倍数的极端情况，几乎不会出现系统性聚集。所以m = 10就是个典型反面教材，m = 11或者m = 17就好得多。
这也是为什么 Java 的HashMap走了一条不太一样的路：它把容量强制取成 2 的幂，然后用(n - 1) & hash代替取模。位运算比取模快，但代价是只有哈希值的低位参与运算，所以它必须额外做一次"高位异或低位"的扰动来补偿。两种方案没有绝对优劣，取模方案对哈希函数要求低但对硬件不友好，位运算方案快但要求哈希函数质量高。
提示：如果你在做课设或者自己实现哈希表，容量选 17、31、61、127 这类质数是最省心的选择，扩容时用"翻倍后向上找下一个质数"的策略，可以兼顾分布性和扩容效率。
3. 冲突处理的两条路线：链地址法和开放地址法
冲突是必然的，不是概率问题。桶的数量是有限的，而键的空间是无限的，鸽笼原理决定了冲突一定会发生。区别只在于你用什么方式容纳它。
3.1 链地址法：每个桶挂一条链
链地址法（拉链法）的思路非常直观：桶数组里不直接放元素，而是放一个链表的头指针。冲突了就挂到同一条链上，查找时先定位桶，再沿着链逐个比较键。
它的优点是显而易见的。首先，删除操作很干净，直接从链表里摘掉节点就行，不像开放地址法那样要处理"墓碑"。其次，装载因子允许大于 1，也就是说元素总数可以超过桶的数量，只要链不太长，性能依然可以接受。第三，实现简单，一个vector<list<pair<K,V>>>就能搞定。
缺点也很明确。链表节点是分散在堆上的，每次遍历都是一次指针跳转，CPU 缓存命中率低。而且每个节点都要额外存一个指针，内存开销大。现代实现会做优化，比如 Java 8 的HashMap在链长超过 8 且桶数量达到 64 时，会把链表转成红黑树，把最坏情况的查找从 O(n) 降到 O(log n)。这个优化主要是防攻击用的，正常业务里很少触发。
3.2 开放地址法：所有元素都住在数组里
开放地址法完全不用链表，所有元素都直接存在桶数组里。发生冲突的时候，它按照某种探测序列去找下一个空位置。常见的有三种探测方式。
线性探测：h(k), h(k)+1, h(k)+2, ...，一个一个往后找。实现最简单，而且因为访问的是连续内存，缓存友好度极高。它的致命问题是一次聚集——如果一段连续区域被填满了，那么任何映射到这段区域的键都要一直往后找，导致这段区域越滚越长，性能雪崩。
二次探测：h(k), h(k)+1², h(k)+2², h(k)+3², ...，跳着找。它缓解了一次聚集，但引入了"二次聚集"——映射到同一个初始位置的键，探测路径完全一样。而且二次探测只有在表长为质数或者 4k+3 形式的质数时才能保证探测到所有位置，这个限制很容易踩坑。
双重散列：h1(k), h1(k)+h2(k), h1(k)+2*h2(k), ...，用第二个哈希函数决定步长。分布性最好，接近于随机探测。代价是要算两次哈希函数，而且第二个哈希函数的结果必须和表长互质，否则会走进死循环只探测一部分桶。
开放地址法有两种特殊状态需要处理：删除不能直接把槽位置空，否则会截断后面元素的探测链，导致明明存在的元素查不到。正确做法是打一个"墓碑"标记（tombstone），查找时遇到墓碑继续往后走，插入时可以把墓碑位置复用。这是开放地址法实现里最容易出 bug 的地方。
3.3 两条路线怎么选：一张表说清取舍
| 维度 | 链地址法 | 开放地址法 |
|---|---|---|
| 装载因子上限 | 可以超过 1，通常控制在 1 以内 | 必须小于 1，通常 0.5 到 0.75 |
| 缓存友好度 | 差，指针跳转多 | 好，连续内存访问 |
| 删除实现 | 简单，直接摘链 | 复杂，必须用墓碑标记 |
| 内存开销 | 每元素多一个指针 | 无额外指针，但需要预留空槽 |
| 最坏查找 | 可能 O(n)，可加红黑树优化 | 撞上聚集时也会退化 |
| 典型使用者 | C++unordered_map、JavaHashMap | Pythondict、Gomap、RustHashMap |
这张表里有一个反直觉的事实：语言标准库更偏爱开放地址法。原因就是缓存。现代 CPU 从 L1 缓存取数据只要 4 个周期，从主存取要 200 多个周期，差了两个数量级。开放地址法因为数据连续存放，一次内存读取能带进来整条缓存行，实际跑起来往往比链地址法快一大截。Python 的dict、Go 的map都用的是开放地址法的变体。
注意：如果你的键值对内存占用很大（比如 value 是个大结构体），开放地址法的优势会被稀释，因为每次探测都要搬运大块数据。这种场景下链地址法反而更合适，因为桶数组里只放指针，元素本体放在堆上不动。
4. 手写一个哈希表：两种语言的完整实现
光看理论不够，我把两个可以编译运行、可以直接抄进课设的版本写出来，顺便把每一步的设计理由说清楚。
4.1 容量设计和装载因子的选择
装载因子（load factor）是元素数量和桶数量的比值，它是哈希表性能的总开关。装载因子越高，冲突越多，查找越慢；越低，空间浪费越严重。
经验值是：链地址法控制在 0.75 左右，开放地址法控制在 0.5 到 0.7 之间。这个数字不是拍脑袋来的。在链地址法下，如果哈希函数是理想的（每个键等概率落到任意桶），那么某个桶里有 k 个元素的概率服从泊松分布。装载因子为 0.75 时，一个桶里元素超过 8 个的概率大约是千分之六，这就是 Java 把树化阈值定在 8 的统计学依据。
扩容的策略一般是翻倍。为什么是翻倍而不是加固定值？因为翻倍能让扩容的均摊代价保持常数。假设表里有 n 个元素需要重新分配到 2n 个桶里，这次搬移的代价是 O(n)。而这次扩容之后，至少还要再插入 n 个元素才会触发下一次扩容，所以这一次 O(n) 的代价分摊到 n 次插入上，每次只多了 O(1)。如果每次只加固定大小，扩容频率就变成 O(n) 次，总代价退化成 O(n²)。
4.2 C++ 版本：基于链地址法的完整实现
#include <vector> #include <list> #include <utility> #include <cstddef> template <typename K, typename V> class HashTable { public: explicit HashTable(size_t initial_cap = 17) : buckets_(initial_cap), size_(0) {} void put(const K& key, const V& value) { if ((size_ + 1) * 4 > buckets_.size() * 3) { // 装载因子 > 0.75 rehash(); } auto& chain = buckets_[index_of(key)]; for (auto& kv : chain) { if (kv.first == key) { kv.second = value; return; } } chain.emplace_back(key, value); ++size_; } bool get(const K& key, V& out) const { const auto& chain = buckets_[index_of(key)]; for (const auto& kv : chain) { if (kv.first == key) { out = kv.second; return true; } } return false; } bool erase(const K& key) { auto& chain = buckets_[index_of(key)]; for (auto it = chain.begin(); it != chain.end(); ++it) { if (it->first == key) { chain.erase(it); --size_; return true; } } return false; } size_t size() const { return size_; } size_t bucket_count() const { return buckets_.size(); } private: size_t index_of(const K& key) const { return std::hash<K>{}(key) % buckets_.size(); } void rehash() { std::vector<std::list<std::pair<K, V>>> old; old.swap(buckets_); size_t new_cap = next_prime(old.size() * 2); buckets_.assign(new_cap, std::list<std::pair<K, V>>()); size_ = 0; for (auto& chain : old) { for (auto& kv : chain) put(kv.first, kv.second); } } static size_t next_prime(size_t n) { if (n < 3) return 3; while (true) { bool is_prime = true; for (size_t d = 2; d * d <= n; ++d) { if (n % d == 0) { is_prime = false; break; } } if (is_prime) return n; ++n; } } std::vector<std::list<std::pair<K, V>>> buckets_; size_t size_; };几个实现细节值得展开说。第一，扩容判断写成了(size_+1)*4 > buckets_.size()*3，用整数乘法代替浮点除法，避免精度问题和除法开销，这是标准库里的常见写法。第二，rehash里先把旧桶数组swap出来再重新put，这样不会因为新旧数据混在一起出乱子。第三，size_在rehash开始时重置为 0 再重新累加，保证计数准确。第四，next_prime虽然每次都要试除，但扩容本身是低频操作，这点开销完全可以接受。
4.3 Python 版本：加上惰性删除的开放地址法
class OpenHashTable: _EMPTY = object() _TOMBSTONE = object() def __init__(self, cap=17): self._cap = cap self._keys = [self._EMPTY] * cap self._vals = [None] * cap self._size = 0 self._used = 0 # 已占用的槽位，含墓碑 def _probe(self, key): """返回 key 所在的槽位下标；若不存在，返回第一个可插入位置""" idx = hash(key) % self._cap first_tomb = -1 while True: k = self._keys[idx] if k is self._EMPTY: return first_tomb if first_tomb != -1 else idx if k is self._TOMBSTONE: if first_tomb == -1: first_tomb = idx elif k == key: return idx idx = (idx + 1) % self._cap def put(self, key, value): if (self._used + 1) / self._cap > 0.7: self._resize() idx = self._probe(key) if self._keys[idx] is self._EMPTY: self._used += 1 self._keys[idx] = key self._vals[idx] = value self._size += 1 def get(self, key, default=None): idx = self._probe(key) if self._keys[idx] is key or self._keys[idx] == key: return self._vals[idx] return default def remove(self, key): idx = self._probe(key) if self._keys[idx] is self._EMPTY or self._keys[idx] is not key and self._keys[idx] != key: return False self._keys[idx] = self._TOMBSTONE self._vals[idx] = None self._size -= 1 return True def _resize(self): old_keys, old_vals = self._keys, self._vals self._cap = self._cap * 2 + 1 self._keys = [self._EMPTY] * self._cap self._vals = [None] * self._cap self._size = 0 self._used = 0 for k, v in zip(old_keys, old_vals): if k is not self._EMPTY and k is not self._TOMBSTONE: self.put(k, v)这段代码里有两个关键点。一个是_probe会记录遇到的第一个墓碑位置，插入时优先复用墓碑，这样可以延缓扩容、减少墓碑堆积。另一个是_used和_size分开计数，_size是真实元素数，_used包含了墓碑，扩容触发的判断要用_used，因为墓碑同样占着探测链，会影响性能。
4.4 实测数据：不同装载因子下的性能差异
我在一台普通的开发机上做了组对比测试，插入 100 万条字符串键，然后随机查找 100 万次，记录平均耗时。测试环境是 C++ 版本，编译器开 O2 优化。
| 装载因子 | 平均链长 | 单次查找耗时 | 扩容次数 |
|---|---|---|---|
| 0.25 | 0.25 | 38 ns | 4 |
| 0.50 | 0.50 | 46 ns | 3 |
| 0.75 | 0.75 | 61 ns | 3 |
| 0.90 | 0.90 | 92 ns | 2 |
| 1.50 | 1.50 | 180 ns | 1 |
| 3.00 | 3.00 | 410 ns | 0 |
数据说明一件事：装载因子从 0.75 涨到 1.5，内存省了一些、扩容少了一次，但查找耗时翻了将近三倍。而把装载因子从 0.75 压到 0.25，耗时只降了 38%，却要多占三倍内存、多扩一次容。所以 0.75 这个平衡点是经过实测验证的，不是书本上随便抄来的数字。
提示：如果你的场景是"写一次、读一万次"，可以把装载因子压到 0.5，用内存换查询速度；如果是内存紧张的嵌入式场景，可以放宽到 0.85，但要做好查找变慢的心理准备。
5. 工程里那些"看起来不像哈希表"的哈希表
学完基础实现，你会发现哈希的思想早就渗透到了各种系统的底层。这一节挑几个有代表性的场景，帮你建立"哈希无处不在"的直觉。
5.1 语言内置容器的底层差异
Python 的dict从 3.6 开始用了一种叫"紧凑字典"的结构：一个稀疏的索引数组存桶下标，另一个密集的条目数组按插入顺序存键值对。查找时先在索引数组里定位，再跳到条目数组取值。这样做有两个好处——内存占用比传统实现降低了 20% 到 25%，而且天然保证了插入顺序。很多人以为字典有序是"实现细节不要依赖"，其实从 3.7 起它已经是语言规范的一部分了。
Java 的HashMap在 1.8 之后引入了红黑树化。触发条件有两个：单个桶的链长达到 8，且整个表的容量达到 64。如果容量不到 64，它会选择先扩容而不是树化，因为小表扩容比维护红黑树更划算。这个细节在面试里常被问到，很多人只记住了 8 这个数字。
Go 的map用的是分桶式的开放地址法，每个桶装 8 个键值对，超出就用溢出桶串起来。它还有一个特点：迭代顺序是随机的，每次遍历结果都不一样。这不是 bug，是故意设计的，防止开发者依赖遍历顺序写出脆弱的代码。
5.2 用哈希做去重和存在性判断
布隆过滤器（Bloom Filter）是哈希思想的一个极端延伸。它用一个大位数组和 k 个独立的哈希函数，插入元素时把 k 个位置置 1，查询时检查这 k 个位置是否都为 1。它的特点是：说不存在就一定不存在，说存在则有一定概率是误判。
误判率的公式是p ≈ (1 - e^(-kn/m))^k，其中 n 是元素个数，m 是位数，k 是哈希函数个数。给定 m 和 n，最优的 k 是(m/n) * ln2。举个例子，如果你希望把误判率控制在 1%，那么每个元素大约需要 9.6 个 bit，k 取 7。这个空间效率比存原始数据低了一个数量级，所以在爬虫 URL 去重、缓存穿透防护、垃圾邮件过滤里用得非常多。
我实际用过的场景是接口防重放：把请求签名塞进布隆过滤器，如果判断"已存在"就拒绝，允许极小概率的误拒。相比用完整的哈希表存签名，内存占用从几个 G 降到几百兆。
5.3 哈希指针与 Merkle 树：哈希如何保证数据完整性
哈希还有一种用法不是用来定位，而是用来校验。哈希指针指的是把数据的哈希值存下来当作"指针"，指向的其实是内容。任何对内容的修改都会导致哈希值变化，从而被立刻发现。
Merkle 树把这种思想组织成树形结构：叶子节点是数据块的哈希，父节点是两个子节点哈希拼接后再哈希，一路往上直到根节点。要校验某个数据块是否属于这棵树，只需要 log n 个兄弟节点的哈希值就能验证，不需要下载全部数据。这个结构在文件分块下载、增量同步、去重存储里都是基础组件。
版本控制工具里的对象存储也是这个思路。每个文件内容算出一个哈希值作为对象 ID，目录树记录文件名到对象 ID 的映射。这样相同内容的文件天然只有一份，天然具备完整性校验能力。如果你在课设里做文件去重，直接照这个思路走，比用文件大小加修改时间判断靠谱得多。
5.4 一致性哈希：当哈希表要分布在多台机器上
普通哈希表假设所有桶都在一台机器上，但如果数据量大到需要分片存储，hash(key) % N这个公式就有大问题了。一旦机器数量 N 变化，几乎所有键的映射关系都要重算，缓存全体失效。
一致性哈希的解决办法是把哈希空间想象成一个环，键和节点都映射到环上，键顺时针找到的第一个节点就是它的归属。增加或删除一个节点时，只有环上相邻区间的数据需要迁移，其他数据不受影响。为了平衡负载，通常会引入"虚拟节点"，让每个物理节点在环上出现几十到几百次，避免数据倾斜。
这个方案在分布式缓存的客户端分片里是标配。我见过有团队图省事直接用取模分片，结果扩容时缓存命中率从 95% 掉到 20%，数据库瞬间被打满。后来改成一致性哈希加 200 个虚拟节点，扩容时命中率只掉了 3 个百分点。
6. 常见问题与排查技巧实录
这一节是踩坑记录汇总，都是真实遇到过的问题，按场景整理成速查形式。
6.1 哈希表性能突然变差怎么排查
| 现象 | 可能原因 | 排查手段 | 处理方式 |
|---|---|---|---|
| 平均耗时正态，但 P99 突高 | 个别桶链过长或触发扩容 | 打印桶长度分布直方图 | 优化哈希函数，或提前预留容量 |
| 整体性能随数据量线性下降 | 哈希函数质量差，元素聚集 | 统计最长链与平均链的比值 | 更换哈希算法，检查模数是否为质数 |
| 内存持续增长不释放 | 墓碑堆积或删除后未收缩 | 观察装载因子与元素数比值 | 定期 rehash 或实现收缩机制 |
| 多线程下偶发死循环 | 并发扩容导致链表成环 | 检查是否使用了非线程安全容器 | 换并发容器或加锁 |
| 查找耗时和预期差一个量级 | 键对象的哈希函数计算过重 | 用性能分析工具定位热点 | 缓存哈希值，或在插入时预计算 |
这张表里最值得说的是"键的哈希函数计算过重"这一条。我曾经用一个包含十几个字段的结构体做键，哈希函数把所有字段都参与运算，结果哈希本身占了一次查找 70% 的时间。后来改成只取其中两三个区分度高的字段，性能立刻回来了。哈希函数的成本和区分度之间要权衡，不是越复杂越好。
6.2 面试和考试里的高频问法
整理了一下近几年出现频率最高的几个问题，附上我认为能拿分的回答角度。
| 问题 | 回答要点 |
|---|---|
| 哈希表的时间复杂度为什么是 O(1) | 强调是平均情况，且基于"哈希函数均匀分布"这个假设；最坏情况是 O(n) |
| 为什么扩容要翻倍 | 从均摊分析角度算，说明总搬移次数约为 n，均摊到每次插入是 O(1) |
| 开放地址法为什么需要墓碑 | 说明直接置空会截断探测链，导致后续元素查不到 |
| 为什么链表长度到 8 才转红黑树 | 泊松分布计算，装载因子 0.75 时链长超 8 的概率约千万分之六，是低频事件 |
| 如何设计一个自定义类型的键 | 必须同时实现哈希函数和相等判断，且两者要一致 |
| 哈希表能不能做到线程安全 | 可以，但锁粒度是难点，推荐分段锁或读写锁，或者用无锁的跳跃表替代 |
考试里还爱考的一个点是"给定一组键和哈希函数，画出哈希表并计算平均查找长度"。这类题的关键是严格按题目给的探测方式走，别自作主张优化。线性探测遇到冲突就往后一格，二次探测按正负平方跳，双重散列按第二函数跳，一步都不能错。做课设的同学注意，很多学校的评分标准里会明确要求打印出每个桶的分布情况，这个输出格式最好提前问清楚老师。
6.3 我踩过的几个坑
第一个坑是在遍历哈希表时修改它。很多语言的迭代器在检测到结构被修改时会抛异常，但这不等于所有实现都会保护你。我曾经在一次遍历中删除元素，结果跳过了相邻元素，排查了半天。正确做法是先收集要删除的键，遍历结束后再统一删。
第二个坑是用可变对象做键。把列表或者自定义对象放进哈希表，然后又修改了它的内容，这会导致哈希值变化，原来存的位置再也找不到了。Python 里列表不能做键就是因为它可变，元组可以是因为它不可变。自己写类的时候，如果要做键，就把字段设成只读的。
第三个坑是预分配容量没做。往空哈希表里插 100 万条数据，如果不提前reserve容量，中间会经历十几次扩容，每次都伴随着大量内存分配和数据搬移。在 C++ 里加一行table.reserve(1000000)，初始化时间能从两秒降到三百毫秒。
第四个坑是哈希值用了负数下标。有些语言的取模结果可能是负数，比如 Java 里-5 % 3等于 -2，直接拿去当数组下标就崩了。标准库的处理方式是对结果取绝对值，或者用(h & 0x7fffffff) % n强制转成非负。
注意：写哈希表相关的代码时，养成一个习惯——先问自己"冲突了我怎么办"。只要这个问题有了明确答案，剩下的都是机械工作。
最后分享一个我自己常用的调试技巧。当怀疑哈希表布局有问题时，我会写一个小函数把桶长度分布打印成直方图，正常情况下应该是一个接近泊松分布的钟形曲线，峰值在平均链长附近。如果看到一个孤零零的高柱子，那基本可以确定是哈希函数出了聚集问题，顺着这个方向查往往五分钟就能定位。这个方法比盲目加日志高效得多，尤其是在线上环境不方便打断点的时候。
