开链法与开放地址法, Separate Chaining and Open Addressing, hashmap

开链法与开放地址法，Separate Chaining and Open Addressing

哈希表在插入元素时，如果两个不同的 key 计算出的哈希值落到了数组的同一个位置，就发生了哈希冲突（hash collision）。解决哈希冲突主要有两种思路：开链法（Separate Chaining）和开放地址法（Open Addressing）。Java 的 HashMap 用的是开链法；Python 的 dict 用的是开放地址法。Java 里也有用开放地址法的例子，比如 IdentityHashMap 和 ThreadLocal.ThreadLocalMap，详见后文「在 Java 中的应用」一节。

开链法，Separate Chaining

开链法是一种二维结构：第一维是一个数组，数组的每个槽位（bucket）挂着一个链表（第二维）。插入元素时，先用 hash 函数算出该 key 应该落在数组的哪个槽位，然后直接把这个 key（连同 value）作为一个节点追加到该槽位的链表上。

当多个不同的 key 计算出相同的槽位时，它们并不会互相覆盖或者被挪到别处，而是全部挂在同一个槽位的链表里，按顺序排列。查找时，先定位到槽位，然后遍历该槽位的链表，逐个比较 key 是否相等，直到找到目标或者遍历到链表末尾。

优点

• 实现简单，冲突处理直观，槽位之间互不影响。
• 删除操作非常简单，只需要从链表中把对应节点摘除即可，不会影响其它元素的查找路径。
• 负载因子（元素个数 / 数组长度）可以大于 1，只是链表会变长，查找退化为线性扫描。

负载因子，Load Factor

负载因子的英文是 load factor，公式为 load factor = 哈希表中总元素个数 / 数组长度（槽位数）。这里的"元素个数"指的是整个哈希表中的元素总数，而不是某一个槽位对应的元素个数；某个槽位挂了多少个元素（链表长度）反映的是 hash 分布是否均匀，是另一个维度的问题。例如数组长度为 16，哈希表中一共存了 12 个元素，此时 load factor 就是 0.75。

开链法下即使 load factor 大于 1（元素个数超过数组长度）也不会出错，只是链表会变长；而开放地址法由于只有一个数组，load factor 不能超过 1（数组会满）。

缺点

• 每个节点都需要额外的指针字段存储下一个节点的地址，带来额外的内存开销。
• 如果 hash 函数分布不均匀，某些槽位的链表会很长，导致查找退化为 O(n)（有些实现在链表过长时会转成红黑树，比如 Java 8 之后的 HashMap，来缓解这个问题，详见 HashMap）。
• 链表节点在内存中不连续，缓存局部性（cache locality）较差，性能上不如开放地址法这种连续数组结构。

Java 的 HashMap 就是使用开链法处理 hash 碰撞的典型例子。

开放地址法，Open Addressing

开放地址法与开链法的不同之处在于如何处理 hash 冲突。当新来一个元素哈希到数组中的位置已经被其它元素占据了该怎么办？

开放地址法只有一个数组（一维结构），会根据当前的位置计算出下一个位置，将这个冲突的元素挪进来。如果这下一个位置也被占用了，那么就再计算下一个位置，直到找到一个空的位置。可以想象，将会有一条虚拟的链条将这些相关的位置串起来。这个虚拟的链条就好比开链法里面的第二维链表，只不过链表有显式的指针字段，而虚拟链条没有，它完全是通过数学函数计算出来的。

root = hash(key) % m               // 第一个位置，m 为数组的长度
index_i = (root + p(key, i)) % m   // 链条中的第 i 个位置

index_1 = (root + p(key, 1)) % m
index_2 = (root + p(key, 2)) % m
...

这个数学函数就是上面代码中的 p —— probe sequence（探测序列）。寻找空位置的过程就是一步一步的探测的过程，不同的 key 会生成不一样的探测序列。

在查找的时候，如果第一个位置上保存的 key 不是目标 key，那就沿着探测路径继续寻找，直到找到目标或者遇到一个空位置为止。

探测函数不能随意选择

探测过程有可能出现死循环——探来探去又回到原点，或者回到路径的中间。所以探测函数不能随意选择，它必须保证探测序列不会出现循环：经过 m-1 次探测生成的探测序列必须正好是 1..m-1 的全排列。

这样的探测函数有很多，其中最常见的一种是线性探测函数。该探测序列和输入 key 无关，最终的探测路径只和初始位置相关：

// m = 2^n，c 必须是一个奇数
p(key, i) = c * i
index_i = root + c * i

这里不去仔细证明这个函数为什么满足要求，可以写个简单的代码来验证一下：

public class HashTest {
    public static void main(String[] args) {
        int m = 1 << 16;
        int c = 111111;
        Set<Integer> nums = new HashSet<>();
        for (int i = 1; i < m; i++) {
            int p = c * i % m;
            if (nums.contains(p)) {
                System.out.println("duplicated");
                return;
            }
            nums.add(p);
        }
        System.out.println("no duplicate");
    }
}

输出结果：

no duplicate

死循环的问题解决了。

删除的处理

开链法删除很简单，直接从链表中摘走就是；但开放地址法不能随意地将探测路径中的某个元素删除，这样会导致探测路径中断。为了不让探测路径中断，删除有两种实现方案：

1. 删除标记：在删除的位置置一个特殊的删除标记，查找时可以直接跳过继续沿着探测路径往后寻找。这个删除的位置在后续新元素插入时会被回收利用：插入元素时遍历探测路径，遇到第一个删除标记的位置时不能立即插入，因为这个 key 有可能存在于探测路径的后半部；需要遍历到底确认路径里确实不存在这个元素后，再回过头插入到第一个删除标记的位置。如果删除的位置过多，会影响查找和插入性能。
2. 整体重建：将探测路径的后半部元素全部删除，然后重新插入。如果路径较长，可能会影响插入性能。

聚集问题（Clustering）

在采用 p(key, i) = c * i 探测函数的前提下，如果多个不同的 key 哈希的第一个位置相同，那么它们将共享同一条探测路径——因为探测路径完全由第一个位置决定，和输入 key 无关。这些相关的 key 就会在一条探测路径上聚集，可能导致数据分布不均匀。

如果使用一个和输入 key 相关的探测函数，就可以消灭这个聚集问题：把探测函数中的常量 c 换成一个 hash 函数，只要这个函数总是返回奇数即可，这样的 hash 函数很容易编写：

p(key, i) = h2(key) * i

Python 的 dict 就是使用开放地址法处理 hash 碰撞的典型例子。

Python dict 的实现演变与伪随机探测

Python 的 dict 从很早的版本开始就是开放地址法，这一点从未变过；变化的是内存布局和探测函数的细节：

• 3.6 之前：dict 是一个纯粹的开放地址哈希表，槽位数组直接存 (hash, key, value)，不保证遍历顺序。

• 3.6 引入"紧凑字典"（compact dict）：把哈希表拆成两部分——一个稀疏的索引数组（只存整数下标，大小仍是 2 的幂），和一个按插入顺序紧密排列的 (hash, key, value) 数组。查找时先在索引数组里探测拿到下标，再去紧凑数组里取值。稀疏数组只需要存下标，不用像以前那样让每个槽位都留出 hash/key/value 三个字段的空间，这个改动省了不少内存，顺带带来了"dict 保序"这个副作用（3.7 正式写进语言规范）。但探测发生在索引数组这一层，冲突解决的思路本身没变，仍是开放地址法。

• 探测函数：CPython 没有用简单的线性探测（i = (i+1) % size），而是用一种伪随机探测：

  perturb = hash            // 初始值就是 key 的 hash
  i = hash & mask           // 第一个探测位置，mask = size - 1
  
  // 每次探测失败后：
  perturb >>= PERTURB_SHIFT   // PERTURB_SHIFT = 5
  i = (i * 5 + perturb + 1) & mask
  

  这本质是一个线性同余生成器（LCG），但每一步都会混入 hash 剩余的高位（perturb）。纯线性探测容易让哈希值低位相同的 key 聚集在一起、越滚越大；伪随机探测让探测路径同时依赖 hash 的高位，即使两个 key 的初始位置相同，只要完整 hash 不同，很快就会分道扬镳。当 perturb 减到 0 后，根据 Hull–Dobell 定理，i = (i*5+1) & mask 这个纯 LCG 能保证遍历完所有 2^n 个槽位，不会死循环。PERTURB_SHIFT = 5 是 Tim Peters 通过大量实验选出的经验值。

  • 从早期版本到目前最新的 3.14 系列，这套伪随机探测算法的核心思路一直没变。

其他解决方法

除了开链法和开放地址法这两大类，还有一些变体和混合方案：

• 双重哈希（Double Hashing）：开放地址法的一种探测函数，用第二个哈希函数计算探测步长（即前面 p(key, i) = h2(key) * i 的思路），让不同 key 的探测路径尽量不同，缓解聚集问题。
• 公共溢出区法（Overflow Area）：所有冲突的元素不再挂在原槽位的链表或往后探测，而是统一放进一个独立的"溢出表"。查找时先查主表，查不到再查溢出表。
• 合并链地址法（Coalesced Hashing）：开链法和开放地址法的混合——链表照常存在，但节点复用同一个数组里的空闲槽位，而不是另外分配内存，兼顾开链法的简单和开放地址法的内存连续性。
• 布谷鸟哈希（Cuckoo Hashing）：用两个（或多个）哈希函数和数组。插入时若目标位置已被占用，就把原来的元素"踢出去"，让它去自己的另一个哈希位置，可能引发连锁踢出。优点是查找最坏情况下只需检查固定几个位置，是 O(1)。
• Robin Hood 哈希：开放地址法的变体。插入时如果新元素离自己理想位置的距离比当前占位元素离它理想位置的距离更远，就把旧元素换出来插到别处，从而让各元素的探测距离趋于均匀，减少方差和聚集。
• 跳房子哈希（Hopscotch Hashing）：开放地址法的变体，限制每个元素离理想位置的最大偏移量在一个邻域内，兼顾缓存局部性和删除效率。

在 Java 中的应用

• HashMap、Hashtable、ConcurrentHashMap、LinkedHashMap 用的都是开链法（前文已提到）。
• IdentityHashMap 反而是开放地址法（线性探测），和 HashMap 正好相反，官方文档里明确写了它是 linear-probe hash table，细节见 IdentityHashMap：基于引用相等的 Map 实现。
• ThreadLocal 内部的 ThreadLocal.ThreadLocalMap（每个 Thread 持有一份）同样用开放地址法（线性探测）实现。
• 第三方高性能集合库，比如 fastutil 的 Object2IntOpenHashMap、Int2ObjectOpenHashMap 等 Open*Map 系列，用的也是开放地址法线性探测，为了避免装箱开销和获得更好的缓存局部性。
• Robin Hood 哈希、布谷鸟哈希这些方案在 JDK 和主流 Java 库里没有看到生产级应用，目前多见于学术论文和对比研究中的教学实现。

在 Go 语言中的应用

• Go 1.24 之前：内置 map 更接近开链法的变体——底层是 2^B 个桶（bucket），每个桶固定装 8 个 key-value，桶内还存了每个 key hash 的高 8 位（tophash）用于快速跳过明显不匹配的槽位；桶装满后会挂一个"溢出桶"（overflow bucket），形成一条短链，跟开链法思路很像，只是链表的最小单位是"8 个元素的桶"而不是单个节点。注意这里的"溢出桶"是每个桶各自私有的一条链（哪个桶满了就单独给它挂一个），并不是所有桶共享同一个"公共溢出区"——后者是前文提到的公共溢出区法（Overflow Area）那种不同槽位的冲突元素统一放进一张共享溢出表的做法，Go 的实现严格来说不是这一种，仍然是开链法变体。
• Go 1.24 起：换成了基于 Swiss Table 的实现，思路更接近开放地址法，细节见 Swiss Table 哈希表——8 个 slot 分为一组（group），组内用一个 64 位控制字保存每个 slot hash 的低 7 位，可以并行比较整组 8 个 slot，命中候选后再核对完整 key；一组探测不到就探测下一组，不再需要单独分配溢出桶。这次改动让 map 操作最多快 60%，内存占用最多降低 70%。
• 所以 Go 的 map 前后两代实现分别对应开链法和开放地址法的工程变体：都不是教科书式的单节点链表或单 slot 探测，而是引入"批量分组 + tophash/控制字快速比较"来提升缓存局部性和 SIMD 利用率。

参考

作者：老錢 链接：https://juejin.cn/post/6844903860792721415 来源：稀土掘金 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

维护记录