先看一次很难解释的 CPU 告警。一个查询接口平时五毫秒,某天下午 CPU 从两成涨到九成,数据库一切正常,QPS 也没明显上涨。加日志之后发现,处理请求的代码反复停在同一行:在本地缓存的哈希表里按参数名查一条记录。更奇怪的是,日志里打印的桶号永远是同一个,那个桶挂了 1024 条记录。

把请求参数抓出来才看清:参数值是 20 个字符,由 Aa 和 BB 两个片段拼成。它们看起来每一个都不一样,但按 Java 的字符串哈希规则算出来,1024 个字符串的哈希值完全相同。每个请求都要在那条 1024 节点的链上从头走到尾,做 1024 次字符串比较;并发一上来,CPU 就全花在了比较上。

这就是哈希退化(hash degradation):哈希表原本靠「键分布均匀」换来常数查找,一旦大量键落进同一个桶,单次查找就退化成线性扫描。如果这些键还能由外部输入控制,事情就从「概率上的不巧」变成了「可以故意构造的攻击」。这篇先还原这条链是怎么造出来的,再讲碰撞攻击、红黑树和随机种子各自能挡到哪一层。

现场:1024 个不同的键,一个哈希值

先把现象复现出来。Java 的字符串哈希规则很简单:从左到右,每个字符的编码乘 31 再加上前一步的结果,溢出按 32 位有符号整数处理。Node.js 里用 Math.imul 可以精确模拟这套 32 位乘法。

function javaHash(s) {
  let h = 0;
  for (let i = 0; i < s.length; i++) {
    h = (Math.imul(h, 31) + s.charCodeAt(i)) | 0;
  }
  return h;
}

console.log(javaHash("Aa"), javaHash("BB"));

本机输出是 2112 2112。原因可以手算:A 的编码是 65,a 是 97,65 乘 31 加 97 正好 2112;B 是 66,66 乘 31 加 66 也等于 2112。两个不同的两字符组合,撞在同一个值上。

单靠这一对还不够。把 Aa 和 BB 当成积木,每一层从两块里任选一块,拼十层,就得到 2 的 10 次方,也就是 1024 个长度为 20 的字符串。哈希是逐段累加的:每加一个两字符块,前面的结果先乘 31 的平方,再加上这个块的哈希值。因为每个块的哈希值都是 2112,所以无论怎么排列,最终结果都一样。

const list = [];
for (let mask = 0; mask < 1024; mask++) {
  let s = "";
  for (let i = 0; i < 10; i++) s += (mask >> i) & 1 ? "BB" : "Aa";
  list.push(s);
}
console.log(list.length, list[0].length, new Set(list.map(javaHash)).size);

本机输出是 1024 20 1:1024 个互不相等的字符串,长度都是 20,不同的哈希值只有 1 个。把这批键插进一个 16 桶的链表式哈希表,1024 条记录会全部挂在 0 号桶里;此时装载因子的总量看起来很正常,扩容也救不了它们,因为桶数翻倍之后,同一个哈希值对新的桶数取模仍然在同一个位置。

一次碰撞攻击请求的落点
外部参数进入服务,被当作缓存键
哈希函数算出同一个值,全部落进同一个桶
桶内链表变长,查询逐节点比较
并发叠加,CPU 被字符串比较吃满

哈希退化到底是什么

哈希表的期望成本有一个前提:键经过哈希函数之后,落在各个桶里的数量大致相等。满足这个前提时,桶里平均只有常数条记录,查找是常数时间。哈希退化就是这个前提被破坏的状态:大量键集中到少数桶,单桶内的记录数 k 远大于一,查找要从 O(1) 变成 O(k),最坏时 k 等于元素总数 n。

退化不等于「哈希表实现有 bug」。哈希函数、扩容、冲突处理都可能在按设计工作,只是输入不配合。常见的触发方式有三种:哈希函数本身太弱,只用了键的一部分信息;键的分布有规律,比如都是同一个前缀加递增数字;键的数量和桶数比例失衡,装载因子长期偏高。三种情况都会让桶内的链变长,只是原因不同。

还有一种更隐蔽的情况:哈希值分布看起来均匀,但键的集合被精心挑选过。攻击者不需要让所有键都同哈希,只要让足够多的键落进同一个桶,就能把平均链长拉到几十甚至上百。对单次请求来说,几十次比较不算什么;对每秒上万次请求来说,这些比较就是实打实的 CPU。

碰撞攻击:把概率问题变成确定问题

碰撞攻击(collision attack)在这里指一种拒绝服务手法:攻击者构造大量哈希值相同的键,让服务端的哈希表退化,从而用很小的请求量消耗大量 CPU。它不需要破解密码,也不需要高流量,只需要知道服务端用的哈希算法,并且能控制进入哈希表的键。

能控制的入口比想象中多。查询参数会被框架解析成一个映射;表单字段名、JSON 对象的键、HTTP 请求头、Cookie 名,都会在某一层被放进哈希表。缓存系统用请求参数拼缓存键,路由用路径片段做匹配,模板引擎把变量名放进上下文,日志组件把字段名放进字典。任何一处把「外部可控的字符串」当作哈希表的键,都可能成为攻击面。

放大效应来自嵌套。一次请求带 n 个互相碰撞的键,每插入一个都要沿链走一遍,总成本接近 n 的平方除以二。n 是 1000 时约五十万次比较,n 是 5000 时约一千两百五十万次。请求体只大了几十 KB,CPU 却涨了几个数量级。所以「限制单个参数长度」不一定有用:攻击者可以用很多个短参数。

更麻烦的是,这类攻击在监控上很像业务量上涨:QPS、数据库、网络都没变,只有 CPU 高,排查时容易先怀疑死循环或某次发布。真正有用的线索是同一个桶号反复出现,以及单次耗时随参数个数线性增长。这两个现象指向哈希退化,而不是普通性能问题。

链地址法怎样退化成长链

以链地址法为例,退化过程很直观。插入一个键时,先算哈希、取模定位到桶;如果桶里已经有记录,就把新记录接在链尾。所有键同哈希时,它们永远进同一个桶,链表从一条变成一千条。查找时先定位到桶,再沿着链逐个比较键,目标在链尾就要走完整条链。

定位哈希值相同,取模结果相同,所有键都指向同一个桶,这一步仍然是常数。
插入每条新记录都接到同一条链上,链长随元素数量线性增长。
查找从链头逐节点比对键,命中越晚,比较次数越多,最坏等于链长。

注意扩容在这里帮不上忙。扩容改变的是桶的数量,键的位置是「哈希值对桶数取模」,同哈希的键在任何桶数下都算出同一个下标。桶数从 16 涨到 2048,这一千条记录还是挤在同一个桶里,只是这个桶的下标换了。扩容还会搬一遍数据,短时间内让 CPU 更忙。

开放寻址的退化形态不同,结果类似。所有键同哈希,第一个键占了初始位置,后面的键按探测规则依次往后找空位,于是它们在数组里连成一片。查找时要从初始位置一路探测过去,探测次数和元素数量成正比;删除留下的墓碑会让探测链更长。开放寻址对装载因子更敏感,退化往往来得更早。

两种实现都说明同一件事:冲突处理只能解决「少量碰撞」,解决不了「系统性同哈希」。当碰撞是被人为构造的,桶内结构再怎么优化,也只是把线性扫描换成对数扫描,成本仍然随规模增长。

Java 8 的红黑树挡在哪一层

红黑树(red-black tree)是一种自平衡的二叉查找树,插入和删除会通过旋转维持大致平衡,查找、插入、删除都是对数时间。Java 8 的 HashMap 在链表过长时会把桶内的链转成红黑树,目的就是给最坏情况加一道上限:链长 1024 时,链表查找最坏一千多次比较,红黑树大约十次。

这套转换有条件,不是链一到 8 就立刻变树。桶内节点数达到 8 时会尝试树化,但还要看整个表的容量:容量小于 64 时,HashMap 选择先扩容而不是树化,因为小表扩容后冲突大概率会被打散,建树反而更贵。容量够了才真正转换。反向也有阈值,节点数降到 6 时转回链表,避免在 7、8 附近反复转换。

树化也有代价:树节点多存孩子和颜色,内存更大;插入要维护平衡,常数更高;键不可比较时还要走兜底规则。阈值 8 是权衡的结果:链短时链表更省,链长时树更稳。

红黑树能做的

把单桶最坏查找从线性降到对数。即使攻击者构造出上千个同哈希的键,单次查找也不再走完整条链。它保护的是「已经落进同一个桶」之后的那一段成本。

红黑树做不到的

它不能阻止键继续往同一个桶里堆。插入仍然要定位、比较、调整平衡,元素总数增长时总成本仍会上升。它也不适用于所有语言和所有实现,阈值和容量条件各版本还不一样。

还有一点:树化只改变桶内结构,不改变哈希值,攻击者仍能让所有键进同一棵树。1024 个键约十次比较,比一千次好得多,但一千万个键就是二十多次,高并发下仍能吃掉可观的 CPU。所以红黑树是减速带,不是防火墙。

随机种子:让攻击者算不出来

换一个思路:如果哈希函数里掺入一个每个进程都不一样的随机数,攻击者就无法在本地预先算出「哪些字符串会碰撞」。同一个键在两次进程启动后可能落到不同桶里,攻击者构造的那批字符串,到了新进程里就散开了。这个随机数叫种子(seed),这种做法叫每进程随机化。

具体实现通常是把原始哈希再和一个随机种子混合,或者直接换成一个带密钥的哈希函数。Python 从 3.3 开始对字符串哈希默认加随机种子,可以用环境变量固定它来复现实验;Rust 标准库的 HashMap 默认用带随机密钥的哈希;一些 Web 框架和语言运行时也采用类似策略。它们的目标一致:让「同哈希的键集合」无法被外部提前构造。

Java 8 的 HashMap 默认没给字符串哈希加每进程随机种子,String 的哈希规则固定,所以 Aa 和 BB 的碰撞在不同进程里都能复现。它能依靠的是红黑树,把长链查找压到对数级。同一段攻击在 Python 服务上可能失效,在 Java 8 上仍能制造长链,只是被树化削弱。

种子也带来约束。哈希值不再跨进程稳定,依赖顺序的逻辑会变得不可复现:测试断言的遍历顺序、按哈希分片的缓存都可能对不上。分布式场景需要的不是随机,而是共享密钥的稳定哈希:节点用同一个密钥,外部不知道它,节点之间仍能算出相同结果。

种子的强度同样重要。种子太短可以被暴力枚举,种子写进代码仓库或日志等于公开密钥,种子在进程启动时从可预测的时间戳生成也容易被猜中。随机化的价值在于「攻击者算不出来」,一旦种子泄露,它就退化成固定哈希,之前的所有防护都回到原点。

现象、真实原因与第一步排查

哈希退化在现场的表现经常被误判成「代码有死循环」或「机器性能下降」。下面这些症状可以帮你把方向拉回来。

现象真实原因第一步查什么
QPS 没涨,CPU 突然飙高,数据库正常大量键同哈希,单桶长链被反复线性扫描抓请求参数,统计键的哈希与桶分布
日志里同一个桶号反复出现输入被构造成同一哈希值,集中落在一个桶取几条键在本地算哈希,确认是否相同
单请求耗时随参数个数线性增长每个参数插入或查找都要走长链,总量接近平方级对比参数个数与耗时的关系曲线
重启后攻击效果消失,过一阵又出现进程级随机种子改变了桶位置,攻击者需要重新试探确认运行时是否启用哈希随机化
链长明明超过 8,却没有转成树表容量还没到树化门槛,实现选择先扩容看容量、桶内节点数与实现的阈值条件
树化后单次查找仍然偏慢键不可比较,比较退化成兜底规则;或元素总量太大统计比较次数与树的实际高度
同样的攻击在另一种语言里无效不同运行时的哈希算法、种子策略、冲突结构不同确认语言版本与哈希随机化配置
防护规则没拦住,服务仍然变慢攻击参数在请求体、请求头或 Cookie 里,不在 URL盘点所有进入哈希表的外部输入

第一行和第二行要结合看:只看 CPU 高容易去查数据库,只看桶号又容易以为日志打错。把两者对上,再拿几条真实键本地算一遍哈希,基本能确认。第五行提醒:不同实现的阈值不同,不能直接照搬 8 和 64。

边界与代价:防护不是免费的

红黑树的代价在内存和常数上。每个树节点要存额外的指针和颜色,节点数量大时内存上升明显;插入删除要旋转,单次操作比链表慢;键不可比较时还要走兜底比较。它适合「链已经很长」的极端情况,不适合日常的小桶,所以阈值定在 8 而不是 2。

随机种子的代价在可复现性上。哈希顺序变了,依赖顺序的测试会飘,按哈希分片的数据会错位,缓存和索引的跨进程一致性会被打破。它挡的是「预先构造」的攻击,挡不住偶然碰撞,也挡不住攻击者通过大量试探反推种子。种子一旦固定或泄露,防护效果立刻归零。

更根本的限制是:只要外部能控制键,就没有一劳永逸的结构。树化压低最坏成本,随机化让构造变难,限流和校验减少攻击面,这三层都只是提高成本。真正的边界是别让不可信的大量键直接进同一张表:限制单请求参数个数、给缓存键设长度上限、把解析和业务分开。

还要留意测量方式。碰撞攻击往往表现为「平均耗时正常、尾部很糟」,只看平均值会漏掉,应看 P99、单请求最大耗时和桶长最大值。压测时用「同哈希参数」单独跑一组,否则测不出这条退化路径。

当天能做的练习

  1. 实现本文的 javaHash,打印 Aa 与 BB 的哈希值,确认都是 2112,并手算验证 65 乘 31 加 97 与 66 乘 31 加 66。
  2. 用 10 层 Aa 与 BB 的组合生成 1024 个长度为 20 的字符串,统计不同哈希值的数量,再插进 16 桶链表式哈希表,打印每个桶的链长。
  3. 给哈希函数加一个进程启动时生成的随机种子,重复第二步,记录两次运行的分桶结果,说明为什么两次不一样。
  4. 实现一个简单的红黑树或直接用有序结构模拟树化,对比 1024 个同哈希键在链表和树上的平均比较次数。
  5. 本地起一个最小 HTTP 服务,用普通参数和一批同哈希参数各压测一次,记录 P99 与 CPU,确认退化只出现在构造参数那一组。
环境说明:文中 Aa 与 BB 的哈希 2112、1024 个长度 20 的字符串只有 1 个不同哈希值、16 桶时全部落进 0 号桶,均为本机 Node.js 24 实际运行结果。Java 的阈值与行为来自其公开实现约定,不同版本可能有差异,落地前请以所用版本为准。

小结与下一篇

三句话收一下:哈希退化是「键分布均匀」这个前提被破坏,单桶成本从常数变线性;碰撞攻击利用可控输入构造同哈希键,用很小的流量放大 CPU;红黑树把桶内查找压到对数,随机种子让攻击者无法提前算出碰撞,两者都只是提高攻击成本。

下一篇换一个场景:不再是单个服务里的哈希表,而是一组缓存节点怎样决定「哪个 key 放哪台机器」。用取模法时,集群从三台扩到四台,绝大多数 key 的归属都会变,缓存命中率瞬间塌掉。下一篇讲一致性哈希的哈希环、顺时针找节点和虚拟节点,解释为什么扩缩容时只需要搬一小部分数据。