先还原一次线上变慢。后台有个用户表,按 id 查用户信息,接口平时三毫秒,晚高峰偶尔蹦到四十毫秒。数据库监控正常,慢查询日志里没有一条慢 SQL,问题只能出在服务自己的内存索引上。同事在那个索引里加了一段统计代码,把每个桶挂了多少个节点打印出来,答案是一串很整齐的数:124、124、126、125、124、125、127、125。
一千个用户,八个桶,平均每个桶一百二十五个节点。按 id 查的时候,先算哈希找到桶,再在桶里一个一个比对键,运气不好要走到链尾,于是一次查询变成一百多次字符串比较。这个索引是手写的哈希表,构造时把「初始容量 8」当成了固定桶数,插入时根本没有扩容,装载因子早就越过 0.75 了。
同事以为哈希表的查询天然是常数时间,其实那句话有个前提:每个桶里的元素要足够少。桶少了,冲突就多;冲突多了,常数时间就变成线性时间。这篇从这条长链讲起,把哈希函数、桶、键值对、冲突、装载因子、扩容与重新哈希逐个说清楚,最后给一张按现象排查的表。
现场:一条链挂了 127 个节点
上面那组数加起来正好是一千。八个桶的「平均链长」一百二十五,最长的一条挂在第七个桶上,一百二十七个节点。接口变慢不是每次都慢,而是取决于目标用户排在链上的哪个位置:排在前面的几次比较就返回,排到链尾的要走完一百二十七步。P99 的抖动就是这么来的,平均耗时看起来还行,尾部请求却很难看。
正常的哈希表不会让这种情况持续。按 0.75 的装载因子算,八个桶最多装六个元素,插入第七个时就该扩容。这块手写代码没有这个判断,桶数组建好之后就不再变,于是一千个键全部挤在八个位置里。这不是哈希函数算错了,恰恰相反,键分布得相当均匀,问题在于桶的总数从一开始就不够。
后面会看到,把这批键放进一个会扩容的表,桶数会一路涨到 2048,最长链降到 4。同一个哈希函数、同一批键,只补上扩容这一步,查询的最坏比较次数就从一百二十七降到四。这也是理解哈希表最划算的切入点:先分清「哈希函数负责打散」和「容量负责稀释」这两件事。
哈希函数、桶与键值对
先把这个结构的零件认清楚。键(key)是查找时用的东西,比如用户 id;值(value)是键对应的数据,比如用户对象;键值对(entry)就是把两者绑在一起的一条记录。桶(bucket)是底层数组的每一格,一格可以只放一条记录,也可以挂一串记录。哈希表就是「数组加一套把键换算成数组下标的方法」。
哈希函数(hash function)负责这个换算:它接收任意长度的键,输出一个固定范围内的整数。这个整数不需要唯一,也不需要可逆,它只要满足三件事:同一个键每次算出来一样;不同的键尽量落到不同的值;算得快。很多实现还会把结果再截断到桶数范围内,比如对桶数取模,或者当桶数是二的幂时直接取低位。
function hash(key) {
let h = 0;
for (let i = 0; i < key.length; i++) {
h = (h * 31 + key.charCodeAt(i)) >>> 0;
}
return h;
}
function bucketIndex(key, bucketCount) {
return hash(key) % bucketCount;
}
这段代码是最常见的多项式哈希:把每个字符的编码乘上一个常数再累加,最后截成 32 位无符号整数。常数 31 不是随便挑的,它能让相邻字符的顺序对结果有足够影响,乘法和位移的开销也小。真实的库会更讲究,比如加入随机种子、做高低位混合,目的都是让输出的每一位都尽量随机。
这里要强调一个容易被忽略的点:哈希函数算出来的整数通常很大,真正决定去哪个桶的是「对桶数取模」这一步。哈希函数再好,桶数只有八个,一千个键也只能挤在八个位置。反过来,桶数够了但哈希函数只用了键的最后一位,那所有尾号相同的键还是会撞在一起。打散和稀释是两件事,缺一件都不行。
冲突:为什么必然发生
冲突(collision)指两个不同的键算出了同一个桶下标。它不是实现缺陷,而是数学上躲不开的结果:键的取值可以是无限多的,桶的数量是有限的,把无限压进有限,必然有多个键落到同一格。一千个键、八个桶,平均每个桶一百二十五个,这就是冲突最直白的形态。
处理冲突有两类主流做法。第一类是链地址法(separate chaining):每个桶不存单条记录,而是存一条链,冲突的新记录直接挂在链上,查找时沿着链逐个比对键。第二类是开放寻址(open addressing):所有记录都放在桶数组里,位置被占了就按固定规则往后找下一个空位,找位置的规则叫探测,常见的有线性探测、二次探测和双哈希。
链地址法
每个桶挂一条链,冲突就往后接。实现直白,删除只要改指针,装载因子可以超过一。代价是每条记录多一个指针,节点分散在堆上,遍历时缓存命中率差,链长了只能一个个走。
开放寻址
所有记录都待在数组里,冲突了就按规则找下一个空位。内存连续、缓存友好,没有额外指针。代价是装载因子必须留有余量,删除要留墓碑,冲突密集时探测会连着跳很多格。
两种做法没有绝对优劣,选哪种取决于键的类型、内存预算和删除频率。Java 的 HashMap 用链地址法,冲突严重时会把长链转成红黑树;Python 的 dict 用开放寻址,靠紧凑的数组布局省内存。无论哪一种,「桶内还要再比一次键」这件事都不会省掉,因为哈希只负责定位候选位置,最终确认相等仍然要靠键本身。
这也是为什么自定义对象做键时,必须同时正确实现哈希和相等判断。哈希决定去哪个桶,相等判断决定桶里哪一条才是目标。只改其中一个,表现就是「明明放进去了却查不到」,或者「两个逻辑上相同的键各存了一份」。
装载因子、扩容与重新哈希
装载因子(load factor)是元素数量和桶数量的比值。它衡量桶有多满:一千个元素、两千个桶,装载因子是 0.5;一千个元素、一千个桶,装载因子是 1。装载因子越高,冲突越多,链越长或者探测越远。多数实现把阈值定在 0.75 左右,这是在空间和时间之间取的折中:再低就浪费桶,再高就明显变慢。
当插入让装载因子越过阈值,表就要扩容(resize)。扩容不是简单地多加几格,而是申请一个更大的桶数组,然后把每一条记录重新放到新数组里。因为桶数变了,同一个哈希值对新的桶数取模会得到不同的下标,所以每条记录都要重新计算位置,这个过程叫重新哈希(rehash)。
本机把同样一千个键交给一个带扩容的表:每次插入前检查元素数加一是否超过桶数乘 0.75,超过就把桶数翻倍并重算所有键的位置。容量从 8 开始,依次翻到 16、32、64、128、256、512、1024、2048,一共扩容 8 次。最终 2048 个桶里有 764 个被用到,最长的一条链是 4 个节点。和前面那条一百二十七节点的链相比,差别只来自容量。
扩容的成本要分两个角度看。单次扩容是 O(n),要把所有记录搬一遍;但桶数按倍数增长,扩容一次能撑很多次插入,把成本摊到每次插入上仍然是常数,这叫均摊。真正要小心的是「单次」的那一下:数据量大时,一次搬迁可能造成明显的停顿,如果发生在请求路径上,就会表现为偶发的接口抖动。能预估规模时,创建表就给定足够的初始容量,可以省掉大部分扩容。
现象、真实原因与第一步排查
下面这些症状在哈希表相关的代码里出现频率很高。看到类似情况,先按表里的「第一步」定位,不要急着重写哈希函数。
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 按 id 查询偶发变慢,数据库正常 | 桶数太少或装载因子过高,桶内链太长 | 打印元素总数、桶数、每个桶的链长 |
| 写入时偶发长时间卡顿 | 一次扩容要搬全部记录,停顿集中在那一刻 | 卡顿时间点是否与容量翻倍吻合 |
| 对象明明放进去了却查不到 | 只重写了相等判断,没重写哈希,或哈希用了可变字段 | 键类型的哈希与相等是否成对、字段是否可变 |
| 两个逻辑相同的键各存了一份 | 哈希一致但相等判断没实现,桶内比对失败 | 桶内比对用的是什么相等规则 |
| 遍历顺序每次运行都不一样 | 哈希表不保证顺序,扩容和种子都会改变顺序 | 业务是否依赖顺序,是否需要换成有序实现 |
| 大量键集中在一两个桶 | 哈希函数低位分布差,或键本身规律太强 | 抽样算哈希值,看低位是否集中 |
| 删除很多次后查询明显变慢 | 开放寻址留下了大量墓碑,探测链被拖长 | 统计墓碑数量,是否需要定期重建 |
| 并发场景下 CPU 飙高或数据错乱 | 哈希表不是线程安全的,扩容时并发写会破坏结构 | 是否用了线程安全实现或统一加锁 |
这张表里最容易误判的是第三行和第五行。第三行看起来像「数据没写进去」,实际是键的哈希和相等判断不一致,记录还在某个桶里,只是查找时走不到;第五行看起来像「实现有 bug」,实际是哈希表本来就不承诺顺序,扩容一发生,链上的记录就会被拆到不同桶里。判断哈希表问题,先问「这个键应该去哪个桶」,再问「桶里比对时凭什么认为它是同一个键」。
边界与代价:哈希表不是免费的
哈希表最常被夸大的一点是「查询 O(1)」。准确的说法是「在哈希函数分布均匀、装载因子受控的前提下,查询的期望成本是常数」。一旦这两个前提被打破,最坏情况会退化成 O(n):所有键挤进同一个桶,每次查找都要走完整条链。这不是理论上的极端,键的规律性、糟糕的哈希实现、甚至故意构造的参数都能把它变成现实。
空间是另一项代价。桶数组本身要占位置,每条记录通常还要额外存键的引用、值的引用和链指针。装载因子压低会让查询更快,但空桶变多;装载因子拉高会省内存,但冲突变多。没有一组参数适合所有场景,只能按「读多写少还是写多读少」「内存紧不紧」来定。
哈希表还放弃了顺序。它能把「这个键在不在」回答得很快,却不能回答「比这个键大的下一个是谁」,也不能做范围扫描、前缀匹配、按序遍历。需要这些能力时,应该换平衡树、跳表或 B+ 树,而不是在哈希表上硬加排序。这一点在选型时比性能数字更重要,因为它是结构性缺失,优化不出来。
键的稳定性也常被忽略。哈希值是在插入那一刻算出来并决定位置的,如果键对象的字段后来被修改,哈希值跟着变,这条记录就「漂」在错误的桶里,之后既查不到也删不掉。用可变对象做键,等于给自己埋了一个很难查的坑。规范的做法是让键不可变,或者在修改后先删除再重新插入。
最后是并发。绝大多数哈希表实现都不保证多线程安全,两个线程同时插入可能同时触发扩容,把同一条记录搬两次,甚至把链走成环。并发场景要么用专门的线程安全实现,要么在外部加锁,要么改成每个线程各持一份再合并。不要假设「只是读」就安全,扩容期间的读也可能看到半搬迁的状态。
当天能做的练习
- 用数组加链表实现一个固定 8 桶的哈希表,插入 1000 个
user1到user1000,打印每个桶的链长,确认总数是一千、分布大致均匀。 - 在上一个实现里补上扩容:装载因子 0.75,桶数每次翻倍。统计一共扩容几次、最终桶数多少、有多少个桶被用到、最长链多长,并和前一步的结果对比。
- 把链地址法换成线性探测的开放寻址,分别在装载因子 0.5 和 0.9 时插入同一批键,记录平均探测次数和最大探测次数。
- 用一个可变对象做键,插入后修改它的一个字段,再执行查询和删除,记录两次的结果,并解释记录为什么「消失」了。
- 构造 1000 个哈希值完全相同的键,分别插入链地址法和开放寻址的实现,测量单次查询耗时随元素数量增长的变化。
小结与下一篇
三句话收一下:哈希表用哈希函数把键换算成桶下标,用桶里的二次比对确认是哪一个键;冲突无法避免,链地址法和开放寻址是两种取舍;装载因子决定什么时候扩容,扩容要重新计算每条记录的位置,均摊便宜但单次很贵。
这一篇假设键是「正常」的,冲突是概率事件,多打散几次就均匀了。下一篇要拆掉这个假设:如果键由外部用户控制,攻击者可以刻意构造大量哈希相同的参数,让所有请求落进同一个桶,把一次查询拖成一次线性扫描。那就是哈希退化,也是碰撞攻击的起点。下一篇会从一条被构造出来的长链讲起,再看 Java 8 的红黑树和每进程随机种子各自能挡到什么程度。