计算机是怎么长出来的
总目录/ 第 1 部/ 1.5 数据怎么组织/ 1.5.2

1.5.2 哈希表:为什么它能一秒查到一百万人里的你

约 0.9 万字 · 6 张图 · 读完你能说清哈希函数在做什么、冲突为什么躲不掉、 两种冲突处理法各吃什么亏,以及扩容时那些位置为什么必须重算

上一节结尾留了个坑:数组、链表、栈、队列,全都只能「按位置取」。 要在一百万条记录里找一个名字,它们能做的只有从头扫到尾。 而现实里最常见的需求恰恰是「按内容找」——通讯录按名字查号码, 浏览器按网址找缓存,数据库按主键取一行。

哈希表就是为这件事发明的。它的想法简单到有点赖皮: 不要让数据决定它在哪,让数据自己算出它在哪。 名字是「张三」,那就用一个函数把「张三」算成一个编号, 编号是 73104,那这条记录就放在第 73104 号格子里。 下次再找「张三」,重算一遍,还是 73104,直接走过去就行。

整个过程没有比较、没有扫描、没有「看看下一个是不是」。 走的步数与表里存了多少条记录完全无关——这就是「一秒查到一百万人里的你」的全部秘密。 代价也有,而且不小:两个不同的名字有可能算出同一个编号, 而怎么处理这种撞车,构成了哈希表后面所有的工程内容。

本节的小部分

  1. 1 按内容找,前面四种全都不行
  2. 2 哈希函数:把任何东西压成一个数
  3. 3 好哈希函数的三条标准
  4. 4 冲突躲不掉:生日悖论
  5. 5 一次插入的完整动作
  6. 6 链地址法:每个桶挂一条链
  7. 7 开放寻址:冲突了就换个槽
  8. 8 聚集与墓碑
  9. 9 扩容:位置必须重算
  10. 10 哈希表的坑
  11. 11 各语言的 map 差在哪
  12. 12 哈希表撑不起什么

1.5.2-1按内容找,前面四种全都不行

先把问题摆清楚。有一个存了一百万条「姓名 → 电话」的表,要查「李雷」的电话。 上一节的四种结构各能做到什么:

结构按名字找为什么
数组O(n)不知道李雷在第几号,只能一个一个比
链表O(n)同上,而且每跳一步还要等一次取址
栈 / 队列O(n),还得破坏结构它们压根没打算让你在中间找东西
排好序的数组O(log n)二分查找,20 次比较就能定位——但每次插入都要挪

最后一行是唯一像样的答案:把数据按名字排好序,二分。 100 万条记录只需要 20 次比较,微秒级。听起来够用了, 但代价在「插」和「删」上:往排好序的数组中间插一条,后面几十万条都要往后挪, 那是 1.5.1 里说的 O(n) 搬家。一个通讯录如果只读不写,二分完全够; 可真实的表一直在增删,排序维护不住。

还有一个更根本的问题:二分要求「能比大小」。 名字可以按字典序比,可要是键是身份证号、URL、图片的 MD5、 或者一个包含十几个字段的对象呢?「比大小」这件事本身就得先定义, 定义出来了也不一定有意义——「https://a.com/x」和「https://b.com/y」 谁大谁小,除了排序本身,没有任何用处。

所以需要的不是「更好的查找算法」,而是一个完全不同的思路: 能不能不比较,直接算出位置?

能。只要你愿意接受一件事:位置由内容决定。 名字是「李雷」,那「李雷」这三个字本身就带着一个编号, 只要你有一个函数能从名字算出这个编号,取的时候再算一遍就行。 这个函数就是哈希函数,算出来的编号叫哈希值。

注意这个思路跟前面所有结构的根本区别:数组、链表、树,位置都是外部安排的 ——你决定放第几个,或者按大小排到某处。 哈希表里位置是内容自己长出来的。 正因如此,取的时候不需要任何线索,把内容再喂进函数一次就够。

1.5.2-2哈希函数:把任何东西压成一个数

哈希函数的定义一句话:输入任意长度的东西,输出一个固定范围内的整数。

h("李雷")        = 40971263
h("韩梅梅")      = 21851042
h(13800138000)   = 93045108
h(0x7ffd4a2b)    = 77102944

输入是字符串、整数、指针、结构体都行,输出统一是一个 32 位或 64 位的整数。 这个整数还不能直接用——表只有 m 个槽,得把它折进范围里。最常用的折法是取模:

槽位 = h(key) % m          // m 是槽的个数

比如 m = 8,h("李雷") = 40971263,40971263 % 8 = 7,那「李雷」就放 7 号槽。 下次查「李雷」,重算一遍还是 7,直接去 7 号槽拿。

三个不同的 key 经哈希函数算出整数,再对槽数取模得到槽位,直接落到对应的槽里
图 1.5.2-1 哈希函数把任意内容压成一个槽位。全流程只有一次函数调用和一次取模,没有比较。注意槽位与别的 key 存不存在无关,与 key 自身多大也无关——"李雷"这个名字多长、有多少条记录,都不影响它落在 7 号槽这件事。

这里有三个必须说清的点。

第一,同一个 key 每次算出的值必须一样。 这是哈希表能用的前提。如果 h("李雷") 今天返回 7、明天返回 3, 存进去以后就再也找不到了。所以哈希函数必须是纯函数:不看全局状态、不看时间、不看随机数。 Python 里有个著名的例外——字符串哈希带了一个进程级随机种子, 但那个种子在进程启动时就固定下来了,进程内每次算都一样, 只是换个进程会变。这不妨碍它当哈希表用,只意味着「哈希值不能存到磁盘上跨进程使用」。

第二,输出范围要有限。 真正的哈希表不会拿 64 位哈希值直接当地址——那是 16 EB 的空间。 折进 m 个槽是必须的,这一步也埋下了冲突的根: 有限的槽装无限的 key,撞车是数学必然,不是实现缺陷。

第三,取模这一步有讲究。 % m 是一次除法,除法在 CPU 上要十几到几十个周期,比加减慢得多。 所以容量取 2 的幂时,实现会改用位与:

m = 16 时
  h % 16        →  一次 div,约 20 到 40 周期
  h & (16 - 1)  →  一次 and,1 周期

  前提:m 必须是 2 的幂,否则 & 得到的不是取模

Java 的 HashMap、Go 的 map、Rust 的 hashbrown 都走这条路。 取模换位与省下的这点时间,在每次插入每次查询都要算一遍的情况下,很值。

代价是「只取低几位」会放大哈希函数的质量问题: 如果 h 的低 4 位经常重复(比如都是 0),那么 m = 16 时所有 key 都会挤进同一个槽。 Java 的对策是在取位与之前先做一次扰动,把高位的信息混进低位:

static int hash(Object key) {
    int h = key.hashCode();
    return h ^ (h >>> 16);      // 高 16 位异或到低 16 位
}
// 之后再用 (n - 1) & hash 定位,n 是容量

这一行的意思是:如果哈希值的高位有区分度、低位没有(很常见,因为整数 key 往往高位变化、低位固定), 那么把高位折下来,让低位也带上信息。一行代码,解决了一整类「哈希函数不坏但被截断搞坏」的问题。

1.5.2-3好哈希函数的三条标准

既然位置是算出来的,那函数的脾气就决定了整张表的脾气。好的哈希函数要满足三条。

一是快。 每次插入、每次查询都要算一遍,函数慢,表就慢。 一个要做 200 次乘法的「密码学级」哈希,用在表上就是自杀: SHA-256 算一次要几百纳秒,比直接线性扫十个小元素还慢。 哈希表要的是廉价混合,不是密码学强度——这两件事经常被搞混。

二是均匀。 输出要尽量摊满整个范围,不要偏爱某些值。 均匀性差的典型症状是「一堆 key 挤在少数几个槽」, 于是查找退化成遍历那一条长链。

三是雪崩。 输入差一个 bit,输出要面目全非。 这条标准专门对付「相似的 key」:如果 h 只取决于前几个字节, 那么 user_00001 到 user_99999 会算出大量相同的值; 如果 h 是「各字节求和」,那么 ab 和 ba 完全一样, 而且范围被压在很小的区间里。

看两个真实在用的字符串哈希,都很短,都能用:

// djb2(Daniel Bernstein,1991)
unsigned long h = 5381;
while (*s) h = h * 33 + *s++;        // 33 = 32 + 1,编译器会做成移位加法

// FNV-1a(1991)
unsigned long h = 2166136261u;
while (*s) { h ^= *s++; h *= 16777619u; }

两个都是「乘一个大常数 + 加(或异或)下一个字节」,靠自然溢出把高位丢掉。 为什么这样就够了?因为乘一个大奇数会把输入的每一位往高位推, 溢出的部分丢掉,剩下的位就被之前的输入反复混过。 一次乘法的扩散效果有限,但循环几十次以后,一个字节的差别已经传到整个字长的各处了。

整数 key 更省事。有一种叫乘法散列的做法,是 Knuth 提的:

// 64 位无符号数,取高位而不是低位
uint64_t h = key * 11400714819323198485ull;   // 2^64 / φ
槽位 = h >> (64 - log2(m));

那个常数是黄金比例的倒数乘以 2 的 64 次方。它的性质是「把连续的整数打散得最开」, 所以 1, 2, 3, 4… 这种连续 key 也不会挤在一起,而是均匀散到整个区间。 取高位而不是低位,是因为乘法之后低位的变化最小,高位才带信息。

「哈希」这个词有两个意思,别混。 一个是哈希表里的哈希函数——求快、允许碰撞、碰撞了有办法补救; 另一个是哈希摘要(MD5、SHA-1、SHA-256)——求慢、抗碰撞、被改了就会变。 后者用在文件校验、密码存储、数字签名上,故意设计成算一次要几百毫秒, 让暴力破解变得不划算。两者共用「把任意输入压成定长输出」这个想法, 但设计目标几乎相反。把 SHA-256 拿去当哈希函数,表会慢到没法用; 把 djb2 拿去做文件校验,随便就能构造出碰撞。

1.5.2-4冲突躲不掉:生日悖论

现在说那个绕不过去的问题。m 个槽,要放 n 个 key,只要 n 比 m 大, 就必然有两个 key 落进同一个槽——这叫冲突(collision)。 但真正反直觉的是:n 远小于 m 的时候,冲突也几乎一定会发生。

先看一个中学就讲过的现象。一个班 50 个人,有两个人同一天生日的概率是多少? 很多人算成 50/365 ≈ 14%。正确答案是 97%。原因是要比较的不是「50 个人各自和某一个特定的人同生日」, 而是所有可能的两两组合:50 个人有 1225 对,每一对撞上的概率是 1/365, 1225 对里一对都没撞上的概率是 (364/365)^1225 ≈ 3%。

n 个 key 两两组合的对数:n(n-1)/2
一对都没撞上的概率 ≈ exp(-n(n-1) / (2m))
撞上的概率      ≈ 1 - exp(-n(n-1) / (2m))

令概率 = 50%,解出 n ≈ 1.18 × √m

最后这行是本节最该记住的一个数:撞车概率过半的点,在 √m 附近。 把它代进实际规模:

槽数 m50% 概率发生冲突时相当于装了
365(一年天数)23 个 key6% 满
1 万118 个 key1.2% 满
100 万1177 个 key0.12% 满
10 亿3.7 万个 key0.0037% 满
两条曲线:生日问题 m=365 时 23 人就有五成概率撞上;100 万个槽时 1177 个 key 就有五成概率冲突
图 1.5.2-2 冲突概率随 key 数增长得比直觉快得多。100 万个槽,塞到 1177 个 key 就已经有五成概率撞一次。所以「表还很空,不会撞」是错的——表确实很空,但已经在撞了。这就是为什么任何正经实现都必须处理冲突,而不是「尽量设计一个好的哈希函数避免它」。

这张图的实用含义是:冲突处理不是异常分支,是主流程。 一个哈希表的性能,主要不是由哈希函数决定的,而是由「撞了以后怎么办」决定的。 后面三节全在讲这件事。

1.5.2-5一次插入的完整动作

在讲两种冲突处理法之前,先把一次插入的骨架立起来。它在两种实现里是一样的:

insert(key, value):
    i = h(key) % m              // 1. 算槽位
    while 槽 i 被占用:            // 2. 槽被占了呢?
        if 槽 i 的 key 等于 key:
            覆盖 value; return   // 3a. 是同一个 key,更新
        i = 下一个候选槽位         // 3b. 是别人的 key,换一个位置继续找
    把 (key, value) 写进槽 i      // 4. 找到空位,落座

查询是同一段代码,只是最后一步换成「读出来」而不是「写进去」。 这里有两个容易忽略的点。

第一,最后一定要比较 key 本身。 哈希值只是「筛出候选」,不能证明相等。两个不同的 key 完全可能算出同一个槽位, 甚至(理论上)算出完全相同的哈希值。所以 哈希值相同只是「可能相等」,key 相等才是「确实相等」。 这就是为什么自定义类型做键时,必须同时正确实现「哈希」和「相等」两个操作, 而且两者要一致:相等 ⇒ 哈希值相等(反过来不要求)。

Java 里这两个方法是 hashCode() 和 equals(), Python 里是 __hash__ 和 __eq__,C++ 里是 std::hash 特化和 operator==。只写一个是最常见的 bug 来源: 只写 equals 不写 hashCode,两个「相等」的对象会落到不同槽,查不到; 只写 hashCode 不写 equals,两个哈希相同但内容不同的对象会被当成一个,覆盖掉。

第二,第 3b 步「换一个候选槽位」就是两种流派的分水岭。 换到哪儿去?这个问题有两种主流答案,它们对应两种完全不同的数据结构。

1.5.2-6链地址法:每个桶挂一条链

第一种答案最直白:槽里不放数据,放一个链表的头指针。 撞了就往那条链上再挂一个节点。

struct entry {
    char *key;
    void *value;
    struct entry *next;      // 同一个槽里的下一个
};

struct entry *table[1024];   // 每个槽是一个链表头

插入时算出槽位,走到那个槽,顺着链比较每个节点的 key,都没有就新建一个节点挂在链尾(或链头)。 查询同理。这一招叫链地址法(separate chaining),也叫拉链法。

八个槽的数组,槽 2、3、5 各自挂着一条链表,新插入的 key 追加在槽 3 的链尾
图 1.5.2-3 链地址法:撞车的 key 串在同一个槽下面。槽位数组本身一个字节都不用动,冲突只是让某条链变长。查询的代价是「1 次定位 + 链长次比较」,所以链长就是性能本身——这也是为什么负载因子(平均链长)是这个结构最重要的参数。

它的好处很实在:

实现简单。不需要考虑「表满了怎么办」,链可以无限长; 删除就是摘链,一步到位,不用留标记。

负载因子可以大于 1。1000 个槽放 3000 个 key 不会崩, 只是平均每条链 3 个节点。开放寻址做不到这一点——它的元素必须都待在槽里, 槽满了就真装不下了。

扩容可以拖。因为槽满了也能继续挂链,所以不用急着扩容, 可以等到链真的长了再动。

代价也有两条,而且在现代 CPU 上都不轻:

一是每跳一个节点就是一次 cache miss。 链表节点是插入时逐个 malloc 出来的,散落在堆的各处。 1.5.1 讲过的「地址依赖链」在这里完整复现: 要读下一个节点,得先拿到当前节点里的指针,那就必须等这次内存访问完成。 链长 8 的桶,最坏要串行等 8 次,每次几十纳秒。

二是每个节点都带指针开销。 一个 key-value 对多 8 字节指针;Java 里更狠,节点是个对象, 16 字节对象头起跳,一个 HashMap.Node 实打实 32 字节 (哈希值 4、key 引用 4、value 引用 4、next 引用 4,加对象头对齐)。 100 万条记录,光节点就是 32 MB。

Java 8 之后给这个结构打了个补丁:单条链长度达到 8 时,把链转成红黑树。 链长 8 在随机哈希下概率极低(约千万分之六),所以平时不付出树的代价; 一旦有人恶意构造大量同槽 key,树能把最坏情况的 O(n) 压到 O(log n)。 这就是「树化」,而树是下一节的主角。

1.5.2-7开放寻址:冲突了就换个槽

第二种答案更省:不加链表,冲突了就按某个规则找下一个空槽,把数据放进去。 所有元素都待在槽位数组里,一个指针都不用。

最简单也最常用的是线性探测:槽 i 被占了就看 i+1,还占就看 i+2,直到找到空的。 查询时走同一条路:算出 i,如果那里的 key 不是要找的,就继续看 i+1、i+2…… 直到找到,或者遇到一个空槽(空槽意味着这条路上后面不可能有它)。

i = h(key) % m;
while (table[i].used) {           // 一直走到空槽
    if (equal(table[i].key, key)) return table[i].value;
    i = (i + 1) % m;              // 线性探测:下一个
}
return NOT_FOUND;                 // 遇到空槽 = 这条路走完了
十六个槽的数组,5 到 8 号被占用,新 key 从哈希位置一路探测到后面的空槽
图 1.5.2-4 线性探测:从哈希位置一路往后找空槽。探测路径是连续内存,缓存全命中,这是它最大的优势;代价是「连续占用的段」会越来越长,后面的 key 全得排队走到队尾。

这条路的优点正好补上链地址法的短板:

没有指针,没有额外分配。所有数据在一个数组里, 探测时读的是相邻的几个槽,通常在同一个缓存行里,一次 miss 就够。 实测在中等负载下,开放寻址比链地址快一倍以上,原因就在这里。

内存紧凑。100 万条记录,链地址要额外 32 MB 的节点开销, 开放寻址只有那个数组本身。

但它的短板也同样明显,而且更致命:

第一,负载因子不能高。元素不能超过槽数,否则真的没地方放。 实际实现会把它压在 0.5~0.75 之间,超过就扩容—— 也就是说,一个 100 万条记录的表,得准备 150 万到 200 万个槽。

第二,探测次数随负载因子急剧上升。这一条下面单独说。

第三,删除很麻烦。把槽清空会让探测链断掉,后面那些「绕过来的」key 就找不到了。 解决办法是留一个「墓碑」标记,这也是单独一节。

探测规则不一定是「下一个」。常见的还有两种:

探测方式第 k 步看哪优点问题
线性探测 (i + k) % m 连续内存,缓存最友好,实现最简单 原始聚集严重(见下一节)
二次探测 (i + k²) % m 不会紧挨着排成一片,聚集弱一些 跳得远,每次都是一次新 miss;且同一起点仍走同一序列
双重散列 (i + k·h₂) % m 分布最均匀,接近理想哈希 每次探测都要多算一次哈希(h₂ 是第二个哈希),且要求 m 与步长互质

Python 的 dict 用的是「扰动探测」:先用 i = h & mask 定位, 冲突了就用哈希值的高 5 位做一次扰动,再算下一个位置。 这样既保持了线性扫描的局部性(下一个位置就在附近),又打散了聚集。 Redis 用的也是类似的做法。

1.5.2-8聚集与墓碑

线性探测最要命的问题叫聚集(clustering): 一段连续被占用的槽会自我加强。

假设 5 到 8 号槽已经被占。现在来了一个 key,哈希到 5 号—— 它得一路走到 9 号。再来一个哈希到 6 号的,也得走到 9 号(如果 9 号已占,就走到 10 号)。 于是这段「连续占用」从 5~8 长成了 5~10,接着又会吞掉更多落进来的 key。

更要命的是:只要 key 的哈希值落在段里的任意一个位置,它就要走到段尾。 一个长度 L 的段,对「落进这一段」的所有 key 都额外征收 L 步的成本。 而段越长,落进来的概率越大——正反馈。

数学上,线性探测在负载因子 α 下的平均探测次数是:

命中查找:  ≈ ½ (1 + 1/(1-α))
不命中查找:≈ ½ (1 + 1/(1-α)²)

α = 0.5  →  命中 1.5 次,不命中 2.5 次
α = 0.75 →  命中 2.5 次,不命中 8.5 次
α = 0.9  →  命中 5.5 次,不命中 50 次

注意最后一行。负载因子从 0.75 到 0.9 只多了 0.15, 不命中查找的平均探测次数从 8.5 涨到 50——五倍多。 这就是为什么开放寻址的实现几乎都把扩容阈值压在 0.75 以下: 不是怕表满,是怕手感在接近满的时候断崖式变差。

第二个坑是删除。开放寻址里,一个不存在的 key 的「查找结束条件」是「遇到空槽」。 那么如果把某个槽真的清空,会怎样?

槽:   5     6     7     8
     [a]   [b]   [ ]   [c]
             ↑
        b 和 c 都想放 5 号,b 占了 6 号,c 被挤到 8 号

删掉 b 之后:
槽:   5     6     7     8
     [a]   [ ]   [ ]   [c]
             ↑
查 c:算到 5 → 6 是空的 → 「这条路断了,c 不存在」
但 c 明明在 8 号。查找失败。

解决办法是墓碑(tombstone):删除时不置空,而是打一个「这里死过人」的标记。 查找时把墓碑当作「已占用」继续往下走,插入时把墓碑当作「空位」可以复用。 代价是墓碑会一直占着位置,直到下一次扩容才被真正清掉—— 所以一个频繁增删的表,即使元素不多,探测也会越来越慢。

为什么很多语言干脆不用开放寻址处理删除? 因为墓碑的记账成本不低。Python 会在墓碑比例过高时触发一次重建, Redis 会把删除做成「标记 + 下次 rehash 时清掉」。 工程上常见的偷懒办法是「删除改成逻辑删除」——但那是把问题推给了业务, 表里全是死数据,最终还是要重建。

1.5.2-9扩容:位置必须重算

表总会满,或者负载因子总会顶到阈值。这时候要扩容。 直觉上,扩容就是把老数组拷到新数组里——但哈希表不行。

因为位置是 h % m 算出来的,m 变了,每个 key 的位置都变了。 老表里在 5 号槽的 key,新表里可能在 13 号。所以扩容必须逐个 key 重新算哈希、重新取模、重新落位。这一步叫 rehash。

旧表容量 8,三个 key 分别落在 1、2、5 号槽;扩容到 16 后,同样的三个 key 落到 9、10、13 号槽
图 1.5.2-5 扩容时每个 key 的位置都要重算。三个 key 三个新位置,没有一个能照搬。这也是为什么哈希表扩容比数组扩容贵:数组扩容是「搬内存」,哈希表扩容是「重算 + 重放」,每个 key 都要再算一次哈希。

代价是一次的:搬 100 万条记录,要对每个 key 重算哈希再落位, 在现代机器上大约几十到几百毫秒。这个停顿在服务端是能被感知的—— 一个请求正好撞上扩容,就会突然慢几十倍。

但摊还下来还是便宜。理由与 1.5.1 里动态数组的扩容完全同构: 容量按倍数增长(通常翻倍),搬的总次数是 1 + 2 + 4 + … + n,不到 2n, 摊到每次插入就是常数。 「摊还 O(1)」这个词在这里第二次出现,两次的算术是同一套。

那什么时候扩?看负载因子 α = 元素数 ÷ 槽数。 不同实现选不同的点,本质是在「空间」和「速度」之间选:

实现冲突处理扩容阈值扩容倍数
Java HashMap链 + 树化0.752 倍
C++ unordered_map链1.0(可调)约 2 倍(质数序列)
Python dict开放寻址2/3约 4 倍(小表翻倍)
Go map桶 + 溢出桶6.5 / 桶2 倍
Redis dict链1.0(无持久化时)/ 5.02 倍
两条曲线:链地址的平均比较次数随负载因子平缓上升,线性探测在接近 1 时急剧上升
图 1.5.2-6 负载因子对两种结构的影响完全不同。链地址只是「链变长」,开放寻址是「手感断崖」。所以链地址敢把阈值放到 1.0 甚至更高,开放寻址必须压在 0.75 以下——它不是在省空间,是在买探测次数。

Java 的 0.75 是个折中:再高,链变长的速度快于空间节省的收益; 再低,浪费的内存太多(100 万条记录要预留 200 万个槽)。 这个数字是实测出来的经验值,不是推导出来的。

Redis 的 5.0 则是有意的偷懒:它在做后台持久化(fork 出子进程写盘)时, 尽量不扩容,因为扩容会触发写时复制,把内存翻倍。 用性能换内存,这个取舍只有它自己知道。

最后提一个工程上很漂亮的手法:渐进式 rehash。 既然一次性搬 100 万个 key 会卡住,那就别一次搬完。 Redis 保留新旧两张表,每次读写操作顺手搬一个桶;查找时两张表都查一遍。 等到搬完,旧表释放。

这样每次操作只多一点点工作,把「几十毫秒的停顿」摊成了「几百万次的一点点」。 代价是这段时间内内存占用翻倍,且每次操作都要判断「现在是不是在 rehash」。 Go 的 map 扩容也是类似的思路(evacuate,逐步搬迁)。

1.5.2-10哈希表的坑

哈希表用起来简单,坑却很集中。下面这几条都是真会踩到的。

一、最坏情况是 O(n),而且是可被利用的。 如果所有 key 都落进同一个槽,哈希表就退化成一个链表。 攻击者可以故意构造这样的 key——2011 年就有研究报告指出, 多数语言(Java、PHP、Ruby、Python、ASP.NET)的哈希表都能被这种方式打瘫: 发一个包含几万个精心构造参数的 POST 请求,服务端解析参数时要建哈希表, 每次插入都退化成遍历一条长链,一个请求就能吃掉几分钟 CPU。

现在的对策是给哈希加随机种子:进程启动时随机选一个数, 混进哈希计算。这样攻击者离线构造的 key 到了线上就打不准了。 Python 从 3.3 起默认开启(PYTHONHASHSEED), Rust、Ruby、Perl 用的是 SipHash——一种专门为「抗哈希洪水」设计的、 带密钥的哈希函数。它的速度比 djb2 慢,但足以让构造碰撞变得不可行。

二、键必须是不可变的。 哈希值在插入时算一次,位置就定死了。如果之后修改了键的内容, 哈希值变了,但记录还在老位置——下次查就查不到了,而且它会永远占着那个槽, 变成一块垃圾。

// 错误:用可变对象做键
Map<List<Integer>, String> m = new HashMap<>();
List<Integer> k = new ArrayList<>(List.of(1, 2));
m.put(k, "值");
k.add(3);                 // 键被改了
m.get(k);                 // null —— 哈希值变了,去的是另一个槽
m.get(List.of(1, 2));     // 也拿不到 —— 那个槽里躺着的 key 已经不是原来那个了

所以 Java 里做键的通常是 String、Integer 这些不可变类型; 自定义类做键,必须保证参与哈希的字段不可变。 (Java 的 String 还顺手把哈希值缓存在对象里, 第一次算完就不再重算——因为字符串哈希要遍历全部字符, 而 HashMap 每次操作都要算一遍。)

三、遍历顺序是没有意义的。 哈希表的顺序由槽位决定,而槽位由哈希值和容量决定。 插入一个新元素可能触发扩容,扩容后所有元素位置全变—— 所以「上次遍历是这个顺序,这次应该也差不多」这个假设是错的。

需要顺序的场景,要么用有序结构(树、跳表),要么额外维护一个链表记住插入顺序 (Java 的 LinkedHashMap 就是这么做的)。 Python 3.7 起 dict 保证插入顺序,但那是 dict 的额外承诺, 靠的是一层紧凑的 entries 数组——不是哈希表的通用性质。

四、浮点数做键要小心。 0.1 + 0.2 不等于 0.3,它们的哈希值自然也不同; -0.0 == 0.0 但哈希值在某些语言里不一样; NaN != NaN,所以拿 NaN 做键存进去就再也取不出来。 这些不是哈希表的问题,是浮点数的问题,但哈希表会把它放大成「数据凭空消失」。

五、内存开销比想的大。 一条「字符串 → 整数」的记录,业务数据可能只有 20 字节, 但在 Java 的 HashMap 里要占 32(Node)+ 40(String 对象)+ 8(数组槽位) ≈ 80 字节,四倍。100 万条记录就是 80 MB。 这也是为什么「缓存几百万条数据」经常比预期更早 OOM。

1.5.2-11各语言的 map 差在哪

哈希表的原理就这么点,但各家实现的差异不小,而且差异都集中在「怎么处理冲突」和「怎么扩容」上。

Java 的 HashMap:链 + 树化。 数组里存链表头(或树根),单链长度达到 8 且总容量至少 64 时转成红黑树。 扩容时有个巧妙的优化:容量翻倍后,每个 key 的新位置只有两种可能—— 原地不动,或者移动到「原位置 + 旧容量」。 因为 h & (2m-1) 比 h & (m-1) 多用了最高一位, 这一位是 0 就不动,是 1 就往后跳 m。所以扩容时不用重算哈希, 只要看那一位,把链拆成两条即可。

Python 的 dict:开放寻址 + 紧凑布局。 3.6 之后它分两层:一层是稀疏的索引数组(存的是「第几条记录」的下标), 一层是紧凑的 entries 数组(按插入顺序连续存放 key-value)。 查找时先查索引,再跳进 entries。好处有三个:遍历时是连续内存(快)、 天然保持插入顺序、内存比纯稀疏表省很多(索引只存 4 字节下标,不存完整的 key)。

Go 的 map:桶数组 + 溢出桶。 一个桶固定装 8 个 key-value,外加 8 个哈希值的高字节(用来快速筛掉不可能相等的项), 装不下就挂一个溢出桶。查找时先算到桶,再在桶里线性扫 8 个—— 因为 8 个 key 挤在同一个缓存行里,这个线性扫比「再算一次哈希」还快。 扩容阈值是「平均每个桶 6.5 个」,比 8 低,就是给溢出留余量。

Redis 的 dict:链 + 渐进式 rehash。 它要服务几十万个 key,且不能接受停顿,所以扩容是分批做的。 另外它同时维护两张表,查找时两边都查——这段代码因此多了一个分支, 但换来了「永不卡顿」。

实现冲突处理一个亮点一个代价
Java HashMap 链,长链转红黑树 扩容时靠一位判断,不用重算哈希 每条约 80 字节,内存重
Python dict 开放寻址 + 扰动 紧凑布局,遍历快且保插入顺序 负载因子只能到 2/3,空槽多
Go map 8 槽桶 + 溢出桶 桶内线性扫,缓存命中率高 实现复杂,且不保证遍历顺序(每次随机)
Redis dict 链 + 渐进 rehash 扩容不停顿 rehash 期间内存翻倍,代码分支多

看这张表会发现一件事:没有一个实现是「教科书哈希表」。 每个都在某处加了补丁,补的都是同一类问题——冲突处理太慢、扩容太贵、内存太多。 这也说明哈希表的核心难点从来不是「怎么算哈希」, 而是「撞了以后怎么收场」。

1.5.2-12哈希表撑不起什么

哈希表把「按内容找」做到了 O(1),代价是它把顺序彻底打乱了。 而顺序本身是一种信息,很多查询要的正是这个信息。

范围查询。「取 2026 年 1 月到 3 月的所有订单」—— 哈希表只能一条条判断「这条在不在区间里」,等于全表扫描。 因为它对「大小关系」一无所知:相邻的两个 key 在表里可能隔着十万八千里。

最接近的那个。「找小于 100 的最大值」,哈希表做不到。 它只会回答「100 在不在」,不会回答「谁挨着 100」。

排序遍历。要把所有 key 按顺序列出来,哈希表得先全部取出再排序, O(n log n)。而一棵平衡树只要中序遍历,O(n)。

前缀匹配。「所有以 138 开头的号码」—— 哈希把前缀信息彻底搅碎了,同一前缀的 key 散落在各处。 这类需求要靠 trie(字典树)或者有序索引。

所以真实的系统里,哈希表和树是搭档而不是替代关系。 数据库的主键索引用 B+ 树,因为它要支持范围扫描和排序; 但内存里的连接缓冲、去重集合、缓存映射,用的都是哈希表。 一个 MySQL 查询可能同时用到两者: WHERE id = 42 走哈希(如果建了哈希索引), WHERE id BETWEEN 10 AND 20 走 B+ 树。

下一节讲树。它要解决的就是哈希表放弃的那件事: 在保持顺序的前提下,把查找压到 O(log n)。 而且因为磁盘的一次读写要几毫秒(比内存慢十万倍), 磁盘上的树必须长得又矮又胖——那是 B 树和 B+ 树的全部设计的来源。

自测:能答上 6 题,这一节就算过了

  1. 哈希表查找是 O(1),这里的「1」具体指什么?
  2. 为什么哈希函数必须是纯函数(同样的输入永远同样的输出)?
  3. 容量是 2 的幂时,为什么可以用 & 代替 %?这种做法的副作用是什么?
  4. 100 万个槽,塞多少个 key 时撞车概率就过半了?这个数怎么来的?
  5. 哈希值相同,两个 key 一定相等吗?为什么最后必须比较 key 本身?
  6. 链地址法和开放寻址,各自最大的优势和最大的问题是什么?
  7. 线性探测的「聚集」为什么会自我加强?
  8. 开放寻址删除元素时,为什么不能直接把槽清空?墓碑有什么副作用?
  9. 扩容时为什么不能把老数组的元素直接搬到新数组的相同位置?
  10. 哈希表最怕什么样的输入?现在的语言怎么防?
点开看答案(先自己想,别急着点)
  1. 指「步骤数与元素个数无关」:一次哈希计算、一次取模、一次内存访问。不是「很快」——步骤固定,但如果那一步是 cache miss,照样要几十纳秒。
  2. 因为位置是靠重算哈希找回来的。如果同一个 key 两次算出的值不同,存进去的位置就再也算不出来了。所以哈希函数不能依赖时间、随机数、全局可变状态。(Python 的字符串哈希有进程级随机种子,但进程内固定。)
  3. 因为 m = 2^k 时,h % m 等价于取 h 的低 k 位,而 h & (m-1) 就是取低 k 位,一次 and 指令代替一次 div。副作用是只用了低位,如果哈希函数低位区分度差(比如整数 key 低位固定),就会大量冲突——所以 Java 在取位之前先做一次 h ^ (h >>> 16) 扰动。
  4. 约 1177 个。由 n ≈ 1.18√m 得出。原因是冲突概率取决于「两两组合的对数」n(n-1)/2,它随 n 平方增长,所以 n 只需要到 √m 的量级,对数就接近 m 了。
  5. 不一定。不同 key 完全可能算出同一个哈希值(这本身就是冲突)。哈希只负责「筛出候选槽」,最后必须用 key 本身比较一次才能确认。这也是为什么 hashCode 和 equals 必须一起正确实现。
  6. 链地址:优势是负载因子可以大于 1、删除简单、扩容可以拖;问题是每跳一个节点一次 cache miss,且每个节点有指针开销。开放寻址:优势是没有指针、数据连续、缓存命中率高;问题是负载因子必须压低(否则探测次数爆炸),删除要留墓碑。
  7. 因为「落进段里任意位置」的 key 都必须走到段尾。段越长,落进来的 key 越多,段就更长——正反馈。
  8. 因为查找的结束条件是「遇到空槽」。清空会让探测链断开,后面的 key 就找不到了。墓碑的副作用是它仍占着位置,频繁增删的表会越来越慢,直到重建。
  9. 因为位置是 h % m 算的,m 变了结果就变了。老表的 5 号槽对应的 key,在新表里可能在 13 号。所以必须逐个重算重放(rehash)。(Java 有个例外优化:容量翻倍时新位置只可能是「原位」或「原位 + 旧容量」,但那也只是省了重算哈希,位置仍然要重新判断。)
  10. 最怕「大量 key 落在同一个槽」——退化成链表,最坏 O(n)。攻击者可以离线构造这样的 key 打瘫服务(哈希洪水)。对策是加随机种子(Python 的 PYTHONHASHSEED)或用带密钥的哈希(SipHash)。
← 1.5.1 数组、链表、栈、队列:四种最基础的装东西的方式