哈希表：散列、哈希冲突与扩容

学“哈希表：散列、哈希冲突与扩容”时，我走过的弯路可以概括成一句话：HashMap 是我日常用得最多、也误以为最熟的结构，直到被问到冲突、扩容和负载因子，才发现会用和理解差得很远。问题不在于知识点有多难，而在于我一开始只盯着结果，没有看到它在维护什么关系。下面是我重新补这块基础时留下的笔记。

哈希表希望根据键直接定位槽位，而不是从头遍历。理想情况下，插入、查询和删除的平均复杂度都接近 O(1)。这个“快”建立在三个条件上：哈希值分布合理、负载率受控、碰撞处理正确。

它从哪里来

散列思想在二十世纪五十年代用于快速检索记录。Hans Peter Luhn 在 1953 年的 IBM 备忘录中描述了相关方法。它把“从头比较每条记录”改成“先根据键计算候选位置”，而冲突处理、负载因子与扩容正是这种速度提升必须支付的代价。

从键到槽位

哈希映射、桶碰撞和扩容重散列图

图：key 经哈希映射到桶，碰撞处理与扩容共同维持查询效率

槽位数量有限，键空间却几乎无限，所以不同键映射到同一槽位是必然现象，不能靠一个“完美公式”彻底消除。好的哈希函数追求的是稳定、快速且分布均匀。

当容量是 2 的幂时，常见索引计算是：

int spread(int hash) {
    return hash ^ (hash >>> 16);
}

int index = spread(key.hashCode()) & (capacity - 1);

高位扰动让高位信息参与低位索引；位与运算比取模更直接，但要求容量设计与扩容策略保持一致。

两类碰撞处理

拉链法

每个槽位保存一组条目，碰撞元素连接在同一个桶中。结构直观，删除方便；桶过长时查询会退化。Java HashMap 在冲突达到阈值且容量足够时，会把长链转换为红黑树，控制最坏查询成本。

开放寻址

开放寻址线性探测与墓碑删除图

图：发生碰撞后继续探测，删除时用墓碑保持查找链

所有元素都放在数组中。发生碰撞时按照线性探测、二次探测或双重哈希寻找下一个可用槽位。它缓存友好、对象少，但删除需要墓碑标记或重排，负载率过高时探测长度会快速增加。

一个教学版拉链哈希表

public final class SimpleHashMap<K, V> {
    private static final class Node<K, V> {
        final K key;
        V value;
        Node<K, V> next;
        Node(K key, V value, Node<K, V> next) {
            this.key = key; this.value = value; this.next = next;
        }
    }

    @SuppressWarnings("unchecked")
    private Node<K, V>[] table = (Node<K, V>[]) new Node[16];

    public V get(K key) {
        int index = index(key, table.length);
        for (Node<K, V> n = table[index]; n != null; n = n.next) {
            if (java.util.Objects.equals(n.key, key)) return n.value;
        }
        return null;
    }

    private int index(K key, int length) {
        int h = java.util.Objects.hashCode(key);
        return (h ^ (h >>> 16)) & (length - 1);
    }
}

完整实现还需要 put、覆盖已有键、remove、尺寸统计、扩容和重新分桶。教学代码故意不伪装成生产级 HashMap。

一个正确的 put 至少要区分“更新已有键”和“新增节点”：

public V put(K key, V value) {
    int index = index(key, table.length);
    for (Node<K, V> node = table[index]; node != null; node = node.next) {
        if (java.util.Objects.equals(node.key, key)) {
            V old = node.value;
            node.value = value;
            return old;
        }
    }
    table[index] = new Node<>(key, value, table[index]);
    size++;
    if (size > table.length * loadFactor) resize();
    return null;
}

新增节点前插简单，但会改变桶内顺序；若对迭代顺序有要求，就需要额外结构，而不是依赖桶顺序。

扩容时到底发生了什么

假设容量从 16 扩到 32，旧索引使用低 4 位，新索引使用低 5 位。对容量为 2 的幂的实现，元素的新位置通常只有两种：保持旧位置，或移动到 oldIndex + oldCapacity。成熟实现可以利用这个性质拆分桶，避免对每个键做完整取模。

扩容步骤应是：

检查新容量上限和整数溢出。
分配新桶数组。
遍历旧桶，把每个节点迁移到新槽位。
替换 table 引用并更新阈值。
保证异常或并发情况下不会暴露半迁移状态。

教学实现如果直接复用节点并改写 next，要先保存旧 next，否则会丢失桶中剩余元素。

负载因子与扩容

负载因子约等于 size / capacity。容量太小会让碰撞增多，容量过大又浪费内存。达到阈值后扩容，可以缩短平均桶长度，但扩容需要申请新数组并迁移元素，单次成本为 O(n)。

扩容不是简单复制：槽位索引依赖容量，容量变化后元素通常需要重新分布。并发环境下，如果没有恰当同步，读写与扩容交错会造成丢数据或结构不一致，因此应直接使用经过验证的并发容器。

Java HashMap 的结构边界

现代 Java HashMap 主要使用数组桶、链表和红黑树。长链是否树化，不只看桶中节点数量，也看整个数组容量；容量太小时优先扩容，因为扩大桶数往往比立即树化更有效。

这些阈值是实现细节，不应该写进业务判断。真正需要记住的是设计动机：平均情况下保持短桶，在恶意或极端碰撞时限制最坏查找成本。

HashMap 允许一个 null 键，靠专门的哈希处理进入固定槽位；ConcurrentHashMap 不允许 null 键和值，因为并发读取时 get == null 需要明确表示“没有映射”，否则难以区分键存在但值为 null。

equals 与 hashCode 契约

在 Java 中，相等对象必须有相同的 hashCode。如果键对象参与哈希的字段在放入 Map 后发生变化，之后可能再也找不到它。因此键最好不可变，或至少保证影响 equals/hashCode 的字段在键的生命周期中不变。

工程判断

需要有序遍历时考虑 LinkedHashMap 或 TreeMap，而不是假设 HashMap 顺序稳定。
面向不可信输入时要考虑哈希洪泛攻击和碰撞最坏情况。
预估规模较大时设置合理初始容量，减少扩容峰值。
O(1) 是平均判断，不是延迟承诺；实时系统仍需关注尾延迟。

哈希安全与并发

外部输入可以故意构造大量碰撞，让平均 O(1) 退化。公开服务中的哈希表要使用成熟实现、限制单请求元素数，并结合超时与资源配额。密码等安全校验使用的是专门的密码哈希/KDF，与集合寻址哈希不是同一类问题。

多线程读写使用 ConcurrentHashMap，而不是“读取时不加锁、写入时偶尔加锁”。复合操作也应使用 computeIfAbsent、merge 等原子 API；containsKey 后再 put 仍可能发生竞态。

测试清单

不同键、相同 hashCode 的碰撞键。
put 同一键是否覆盖且 size 不增加。
null 策略与 equals 对称性。
刚好跨越扩容阈值时所有键仍可读取。
删除桶头、桶中间、桶尾和不存在键。
随机操作与 java.util.HashMap 对照。
极端碰撞下的性能和桶长度监控。

自测

为什么哈希碰撞必然存在？
拉链法与开放寻址分别适合什么情况？
扩容后为什么要重新确定元素槽位？
可变对象作为 HashMap 的键可能出现什么问题？