Hash 表：拉链法与开放地址法详解
拉链法
你说的“变种链”，如果是在 Hash 表（哈希表）场景里，通常指的是 拉链法（Separate Chaining）的一些改进形式，用于解决哈希冲突。
先从普通拉链法开始理解。
1. 什么是拉链法
假设 Hash 函数：
hash(key) % 8
有数据：
1
9
17
25
计算后：
1 % 8 = 1
9 % 8 = 1
17 % 8 = 1
25 % 8 = 1
全部落到桶 1。
于是：
bucket[1]
|
v
1 -> 9 -> 17 -> 25
这就是最经典的：
数组 + 链表
结构。
2. 普通链表的问题
如果冲突很多：
bucket[1]
1 -> 9 -> 17 -> 25 -> 33 -> 41 -> ...
查找：
O(n)
性能下降严重。
3. 什么是变种链（Variant Chain）
为了优化链表性能，人们对链表做各种改造。
例如：
链表
↓
双向链表
↓
有序链表
↓
跳表
↓
红黑树
这些都可以理解为：
拉链法的变种
4. Java HashMap 的典型例子
JDK 8 以后：
冲突少
↓
链表
冲突多
↓
红黑树
结构：
bucket
|
v
Node
|
v
Node
|
v
Node
当长度超过阈值：
8
会变成：
17
/ \
9 25
/ \
1 33
即：
链表 → 红黑树
查找复杂度：
O(n)
↓
O(log n)
这就是一种典型的“变种链”。
5. Go Map 用的不是变种链
很多人以为 Go map 也用链表。
实际上不是。
Go map 采用的是：
Hash Table
+
Bucket
+
Overflow Bucket
结构类似：
bucket0
+---+---+---+---+---+---+---+---+
|kv |kv |kv |kv |kv |kv |kv |kv |
+---+---+---+---+---+---+---+---+
一个桶能放：
8 个元素
满了以后：
bucket0
|
v
overflow bucket
形成：
bucket
|
v
overflow1
|
v
overflow2
虽然看起来像链表：
bucket -> overflow -> overflow
但本质是：
桶链（Bucket Chain）
而不是：
Node -> Node -> Node
6. 数据库里的“变种链”
如果你是在看数据库源码（MySQL、Redis、LevelDB 等）时看到“变种链”，通常指：
普通链
A -> B -> C
头插链
C -> B -> A
新增更快。
双向链
A <-> B <-> C
删除更快。
有序链
1 -> 5 -> 8 -> 20
查找更高效。
树化链
链表
↓
红黑树
Java HashMap 就属于这种。
里的标准回答
如果官问：
Hash 表中的变种链是什么？
可以回答：
Hash 冲突常见解决方案是拉链法，即每个桶挂一个链表。
为了避免链表过长导致查找退化为 O(n)，实际工程中会对链结构进行优化，
例如使用双向链表、有序链表、跳表、红黑树等结构代替普通链表，
这些改进形式通常称为拉链法的变种链（Variant Chaining）。
典型例子是 Java 8 HashMap：
当桶中元素较少时使用链表，
当链表长度超过 8 时转换为红黑树，
将查找复杂度从 O(n) 降低到 O(log n)。
如果你是在看 Go map 源码 时看到“变种链”这个词，我还可以结合 Go 的 bucket + overflow bucket 结构解释为什么有些资料把它称为“变种拉链法”。
开放地址法
开放地址法（Open Addressing）其实并不少见，但它在不同语言和场景中的使用情况差异很大。
很多人会有一种错觉：
Java HashMap -> 拉链法
Go Map -> Bucket + Overflow Bucket
Redis Dict -> 拉链法
似乎大家都不用开放地址法
实际上：
Python dict ✓ 开放地址法
Python set ✓ 开放地址法
Rust HashMap ✓ 开放地址法（SwissTable）
Abseil flat_hash_map ✓ 开放地址法
Folly F14 ✓ 开放地址法
Go map ✗ 桶链式方案
Java HashMap ✗ 拉链法+红黑树
现代高性能 Hash 表反而越来越倾向开放地址法。
1. 什么是开放地址法
假设：
容量 = 8
hash(key)=3
位置 3 已经被占了：
0 1 2 3 4 5 6 7
A
插入 B：
0 1 2 3 4 5 6 7
A B
继续冲突：
0 1 2 3 4 5 6 7
A B C D
元素直接存放在数组里。
没有链表。
没有额外节点。
2. 为什么曾经很多系统不用它
因为传统开放地址法有几个明显缺陷。
缺陷1：删除麻烦
拉链法删除：
A -> B -> C
删 B：
A -> C
结束。
开放地址法：
槽位:
3:A
4:B
5:C
如果直接删 B：
3:A
4:空
5:C
查找 C 时：
hash(C)=3
3 -> A
4 -> 空
会误认为：
C不存在
因此需要：
墓碑(Tombstone)
标记删除。
结果：
查找越来越慢
缺陷2：聚集问题（Clustering）
例如线性探测：
3:A
4:B
5:C
6:D
7:E
形成：
AAAAA
大块连续区域。
以后元素越来越容易撞进去。
性能下降。
称为：
Primary Clustering
缺陷3：装载因子不能太高
拉链法：
load factor = 2
还能工作。
只是链长一点。
开放地址法：
70%
80%
90%
性能急剧下降。
例如：
容量=100
已使用=95
插入可能探测几十次。
3. 为什么现代系统又开始大量采用
因为 CPU 变了。
过去：
CPU慢
内存慢
差距不大
今天：
CPU: 几 GHz
内存: 几十~上百 ns
一次缓存未命中（Cache Miss）代价非常高。
拉链法的问题
链表：
bucket
|
v
node1
|
v
node2
|
v
node3
节点可能散落在内存：
0x1000
0x9000
0x50000
每次都要：
跳内存
跳内存
跳内存
CPU Cache 很难命中。
开放地址法的优势
元素连续存储：
[A][B][C][D][E]
CPU 一次 Cache Line：
64 Bytes
可能直接加载：
[A][B][C][D]
连续访问非常快。
4. 为什么 Python dict 特别快
原因之一就是：
开放地址法
+
连续内存
+
优秀探测算法
查找时：
数组扫描
而不是：
指针跳来跳去
5. Go 为什么不用开放地址法
Go 设计者做了折中。
Go Map 的 Bucket：
bucket
8个key
8个value
结构：
bucket
k1 k2 k3 k4 k5 k6 k7 k8
v1 v2 v3 v4 v5 v6 v7 v8
查找时：
一次读取整个 bucket
CPU Cache 友好。
但又不像开放地址法那样：
删除困难
探测链过长
所以 Go 采用：
Bucket +
Overflow Bucket
作为折中方案。
6. 现代高性能 Hash 表趋势
近几年趋势其实是：
传统拉链法
↓
桶化(Bucketization)
↓
开放地址法
↓
SIMD开放地址法
代表：
-
Python dict
-
Rust HashMap（hashbrown）
-
SwissTable
-
Abseil flat_hash_map
-
Folly F14
这些都是现代工业级实现。
一句话总结
开放地址法并不是很少使用，相反在现代高性能 Hash 表中非常流行。
它过去不够流行的原因是：
1. 删除复杂（需要墓碑）
2. 容易产生聚集
3. 负载率高时性能下降明显
但随着 CPU Cache 成为性能瓶颈，开放地址法连续内存布局的优势越来越明显，因此 Python、Rust、SwissTable 等现代实现都选择了开放地址法，而 Java 和 Go 则采用了更偏向拉链法的桶式设计来做折中。