先还原一次线上变慢。后台有个用户表,按 id 查用户信息,接口平时三毫秒,晚高峰偶尔蹦到四十毫秒。数据库监控正常,慢查询日志里没有一条慢 SQL,问题只能出在服务自己的内存索引上。同事在那个索引里加了一段统计代码,把每个桶挂了多少个节点打印出来,答案是一串很整齐的数:124、124、126、125、124、125、127、125。

一千个用户,八个桶,平均每个桶一百二十五个节点。按 id 查的时候,先算哈希找到桶,再在桶里一个一个比对键,运气不好要走到链尾,于是一次查询变成一百多次字符串比较。这个索引是手写的哈希表,构造时把「初始容量 8」当成了固定桶数,插入时根本没有扩容,装载因子早就越过 0.75 了。

同事以为哈希表的查询天然是常数时间,其实那句话有个前提:每个桶里的元素要足够少。桶少了,冲突就多;冲突多了,常数时间就变成线性时间。这篇从这条长链讲起,把哈希函数、桶、键值对、冲突、装载因子、扩容与重新哈希逐个说清楚,最后给一张按现象排查的表。

现场:一条链挂了 127 个节点

上面那组数加起来正好是一千。八个桶的「平均链长」一百二十五,最长的一条挂在第七个桶上,一百二十七个节点。接口变慢不是每次都慢,而是取决于目标用户排在链上的哪个位置:排在前面的几次比较就返回,排到链尾的要走完一百二十七步。P99 的抖动就是这么来的,平均耗时看起来还行,尾部请求却很难看。

正常的哈希表不会让这种情况持续。按 0.75 的装载因子算,八个桶最多装六个元素,插入第七个时就该扩容。这块手写代码没有这个判断,桶数组建好之后就不再变,于是一千个键全部挤在八个位置里。这不是哈希函数算错了,恰恰相反,键分布得相当均匀,问题在于桶的总数从一开始就不够。

后面会看到,把这批键放进一个会扩容的表,桶数会一路涨到 2048,最长链降到 4。同一个哈希函数、同一批键,只补上扩容这一步,查询的最坏比较次数就从一百二十七降到四。这也是理解哈希表最划算的切入点:先分清「哈希函数负责打散」和「容量负责稀释」这两件事。

一次按 key 查询走过的路
把 key 交给哈希函数,得到一个整数
用整数对桶数取模,定位到某个桶
在桶内逐个比对 key,命中就返回

哈希函数、桶与键值对

先把这个结构的零件认清楚。键(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+ 树,而不是在哈希表上硬加排序。这一点在选型时比性能数字更重要,因为它是结构性缺失,优化不出来。

键的稳定性也常被忽略。哈希值是在插入那一刻算出来并决定位置的,如果键对象的字段后来被修改,哈希值跟着变,这条记录就「漂」在错误的桶里,之后既查不到也删不掉。用可变对象做键,等于给自己埋了一个很难查的坑。规范的做法是让键不可变,或者在修改后先删除再重新插入。

最后是并发。绝大多数哈希表实现都不保证多线程安全,两个线程同时插入可能同时触发扩容,把同一条记录搬两次,甚至把链走成环。并发场景要么用专门的线程安全实现,要么在外部加锁,要么改成每个线程各持一份再合并。不要假设「只是读」就安全,扩容期间的读也可能看到半搬迁的状态。

当天能做的练习

  1. 用数组加链表实现一个固定 8 桶的哈希表,插入 1000 个 user1 到 user1000,打印每个桶的链长,确认总数是一千、分布大致均匀。
  2. 在上一个实现里补上扩容:装载因子 0.75,桶数每次翻倍。统计一共扩容几次、最终桶数多少、有多少个桶被用到、最长链多长,并和前一步的结果对比。
  3. 把链地址法换成线性探测的开放寻址,分别在装载因子 0.5 和 0.9 时插入同一批键,记录平均探测次数和最大探测次数。
  4. 用一个可变对象做键,插入后修改它的一个字段,再执行查询和删除,记录两次的结果,并解释记录为什么「消失」了。
  5. 构造 1000 个哈希值完全相同的键,分别插入链地址法和开放寻址的实现,测量单次查询耗时随元素数量增长的变化。
环境说明:文中 1000 个键落进 8 个桶的分布、扩容 8 次、最终 2048 桶、764 个桶被使用、最长链 4,均来自本机实际运行;哈希函数选择、键的命名和语言实现不同,具体数字会变化,但「桶少则链长、扩容后链短」的方向不变。

小结与下一篇

三句话收一下:哈希表用哈希函数把键换算成桶下标,用桶里的二次比对确认是哪一个键;冲突无法避免,链地址法和开放寻址是两种取舍;装载因子决定什么时候扩容,扩容要重新计算每条记录的位置,均摊便宜但单次很贵。

这一篇假设键是「正常」的,冲突是概率事件,多打散几次就均匀了。下一篇要拆掉这个假设:如果键由外部用户控制,攻击者可以刻意构造大量哈希相同的参数,让所有请求落进同一个桶,把一次查询拖成一次线性扫描。那就是哈希退化,也是碰撞攻击的起点。下一篇会从一条被构造出来的长链讲起,再看 Java 8 的红黑树和每进程随机种子各自能挡到什么程度。