哈希冲突

为什么会有哈希冲突

哈希表能在平均 O(1) 时间内完成插入、删除、查找，前提是妥善处理哈希冲突——两个不同的 key 经哈希后落到同一位置。冲突无法避免：哈希函数要把无限（或巨大）的键空间映射到有限的表空间中，鸽笼原理决定了必然碰撞。

冲突带来两个问题：查找效率下降（需要额外的探测/链式处理）和空间利用率不均。影响冲突概率的三个因素：

• 哈希函数质量：输出越均匀，冲突越少；
• 装载因子 α（元素数/表大小）：α 超过 0.7 后冲突显著上升；
• 表大小：素数大小的表通常能更好地打散键。

开放定址法（Open Addressing）

所有元素都存在表本身里，冲突时按探测序列找下一个空位。不需要额外指针，内存紧凑、缓存友好，但装载因子高时性能急剧下降，删除需要特殊处理（惰性删除标记，避免查找链断裂）。

1. 线性探测

冲突时依次检查 h(key)+1, h(key)+2, …：

def linear_probing_insert(table, key, value):
    idx = hash(key) % len(table)
    while table[idx] is not None and table[idx][0] != key:
        idx = (idx + 1) % len(table)   # 环形查找
    table[idx] = (key, value)

优点：实现最简单、缓存最友好。缺点：一次聚集（Primary Clustering）——已占用位置连成块，后续插入要探测很长距离。

2. 平方探测

def quadratic_probing_insert(table, key, value):
    idx = hash(key) % len(table)
    i = 1
    while table[idx] is not None and table[idx][0] != key:
        idx = (idx + i * i) % len(table)
        i += 1
    table[idx] = (key, value)

探测序列为 h, h+1², h+2², …，减轻了一次聚集，但不同 key 仍可能共享同一探测序列（二次聚集），且不保证一定能找到空位——数学保证是：表大小 m 为素数且 α < 0.5 时，平方探测一定能找到空位。

3. 双重哈希

用第二个哈希函数决定探测步长，几乎消除聚集：

def double_hash_insert(table, key, value):
    h1 = hash1(key) % len(table)
    h2 = hash2(key) % (len(table) - 1) + 1   # 与 m 互质，保证覆盖全表
    i = 0
    idx = (h1 + i * h2) % len(table)
    while table[idx] is not None and table[idx][0] != key:
        i += 1
        idx = (h1 + i * h2) % len(table)
    table[idx] = (key, value)

分布最均匀、高装载因子下表现最好；代价是要算两个哈希函数，且 h₂ 必须与表大小互质（通常让表大小为素数、h₂ ∈ [1, m-1]）。

链地址法（Separate Chaining）

每个槽位放一个链表，冲突的元素挂到同一链上：

class HashMap<K, V> {
    private Node<K, V>[] table;
    static class Node<K, V> { K key; V value; Node<K,V> next; }

    public void put(K key, V value) {
        int idx = hash(key) % table.length;
        for (Node<K,V> n = table[idx]; n != null; n = n.next) {
            if (n.key.equals(key)) { n.value = value; return; }
        }
        table[idx] = new Node<>(key, value, table[idx]); // 头插
    }
}

工业级演进（以 Java HashMap 为例）：链表长度超过阈值（8）转红黑树，降到阈值以下（6）转回链表，平衡极端冲突场景的性能；装载因子超 0.75 时扩容为 2 倍。Go 的 map 是链地址法变种：每个桶内联 8 个键值对 + tophash 加速比较 + 溢出桶，装载因子超 6.5 或溢出桶过多时渐进式扩容（写入时分批迁移，分摊成本）。

链地址 vs 开放定址

进阶方法

• 布谷鸟哈希：两个表两个哈希函数，插入冲突时”踢”出旧元素重新安放，最坏查找 O(1)、空间利用率可达 95%，但插入成本可能很高（多次重定位），适合静态/查询密集型数据；
• 罗宾汉哈希：让”探测次数少”的元素让位给”探测次数多”的元素，显著降低最大探测距离，查找更稳定，但实现复杂、删除麻烦；
• 跳房子哈希：为每个位置定义固定大小邻域，冲突元素放邻域内，结合开放定址的缓存优势和链地址的容量。

如何选型

• 通用场景：链地址法（实现简单、对装载因子不敏感）——Java HashMap、Go map 都是它；
• 内存敏感/缓存敏感：开放定址法（数据连续）；
• 查找密集、要求稳定时延：布谷鸟哈希；
• 高并发：分段锁或读写锁方案（如 ConcurrentHashMap）。

最后提醒：哈希函数的质量和装载因子的控制比冲突解决策略更影响最终性能——先把哈希函数选好，再谈冲突策略。