哈希表把任意类型的键映射到数组下标，用空间换时间，把查询、插入、删除的平均成本压到常数级。它的全部设计难点集中在三件事上：哈希函数怎么设计、冲突来了怎么安放、表快满了怎么扩。

它解决什么问题

「按 key 快速找到 value」是编程中最高频的需求之一：缓存索引、频率统计、去重、分片路由，背后都是它。顺序表查找要 O(n)，有序数组二分是 O(log n)，而哈希表借助「键 → 整数 → 下标」的映射，理想情况下一次定位。代价有两条：一是键空间远大于数组，不同键挤进同一个桶的冲突在数学上不可避免；二是它只回答「在不在、值是多少」，不维护任何顺序关系。

可以把哈希表拆成三层理解：数组负责存放数据，每个槽位叫桶；哈希函数负责把键变成整数；冲突策略决定多个键落到同一桶时如何安置。三层中任何一层设计失衡，性能都会从常数掉到线性。

核心原理

好的哈希函数要同时满足三条要求。第一是确定性：同一个键在任何时刻算出的哈希值必须一致，否则放进去就再也找不到。第二是计算快：通常是移位、乘法、异或的组合，如果哈希计算本身很重，就抵消了哈希表的速度优势。第三是分布均匀：输出要尽可能铺满值域，理想状态是雪崩效应——输入只翻转一个比特，输出约一半比特跟着变化，FNV、MurmurHash 这类非加密哈希都是为此设计的。

拿到哈希值后还要映射到下标。当数组长度 n 是 2 的幂时，hash & (n - 1) 在数学上等价于取模，但省掉了除法指令；副作用是下标只由哈希值的低位决定，高位信息被丢弃。工程实现通常先做一步扰动，把高位异或进低位，让高位差异也参与定位。

还要分清两个概念：哈希表追求的是速度与分布，和密码学哈希追求的抗碰撞、不可逆是两回事。但在对外暴露的服务里，恶意用户可能精心构造碰撞键发起拒绝服务攻击，这类场景会改用带随机种子的哈希函数，让攻击者无法预测碰撞对。

深入机制

拉链法：桶外挂链

拉链法让每个桶挂一条链表，冲突的键依次链在后面；查询时先定位桶，再在桶内逐一比较。桶内结构不必局限于链表：Java HashMap 在链表长度达到阈值 8 且数组长度不小于 64 时会把桶转成红黑树，让极端冲突下的桶内查询从线性降到对数级。拉链法的装载因子 α（元素数 / 桶数）可以超过 1，分布均匀时成功查找的期望比较次数约为 1 + α/2，所以表「装满」也不会立刻崩溃，只是平均链长随 α 线性增长。

开放寻址：表内探测

开放寻址不用任何外挂结构，所有元素都在数组里，冲突后按探测序列继续找空位。线性探测每次看下一个槽，实现最简、缓存局部性最好，但连续占用段会越滚越大，形成聚集；二次探测按平方步长跳跃，缓解了主聚集；双重哈希用第二个哈希函数决定步长，分布最散。开放寻址的装载因子必须小于 1，且越接近 1 探测次数越陡峭——线性探测下成功查找的期望探测数约为 (1 + 1/(1-α))/2，α 取 0.9 时已经要探测约 5.5 次。删除也更麻烦：直接清空槽位会截断其他元素的探测链，因此要放置「墓碑」标记，把已删除槽和真空槽区分开。

装载因子与扩容

装载因子是哈希表的时间-空间旋钮：调高省内存但冲突变多，调低查询快但桶位浪费。超过阈值就要扩容——申请更大的数组，把所有键重新散列。单次扩容是 O(n)，但只要容量每次翻倍，两次扩容之间至少插入了一半容量的元素，迁移总成本平摊到每次插入上仍是常数，这就是「摊还 O(1)」的含义。

// 最小拉链哈希表骨架：扰动、位运算定位、链上比较
class SimpleHashMap<K, V> {
    private static class Node<K, V> { K key; V value; Node<K, V> next; }
    private Node<K, V>[] table = new Node[16];
    private int size;
    private static final float LOAD_FACTOR = 0.75f;

    private int spread(K key) {
        int h = key.hashCode();
        return h ^ (h >>> 16);          // 高位混入低位，降低碰撞
    }

    public V get(K key) {
        int i = spread(key) & (table.length - 1);
        for (Node<K, V> p = table[i]; p != null; p = p.next)
            if (p.key.equals(key)) return p.value;
        return null;
    }
    // put：定位桶后链上查找，命中覆盖、未命中尾插；size 超过
    // table.length * LOAD_FACTOR 时把容量翻倍并重排全部节点。
}

工程实践

Java HashMap 是拉链法的教科书实现：容量恒为 2 的幂，用 (n-1) & hash 寻址；一次异或扰动弥补低位信息不足；默认装载因子 0.75 是空间与冲突率的统计折中；链表过长时树化兜底；扩容时利用 hash & oldCap 这一个比特把旧链拆成两条，免去全量重新哈希。

Redis 的 dict 展示了另一条路线：同样用拉链法，但常备两张表，平时只用 ht[0]。当元素数与桶数的比值达到 1（正在进行后台持久化时放宽到 5）就触发扩容，但并不一次性搬迁，而是把 rehash 摊到之后的每次增删改查里，每次操作顺带搬走一个非空桶——渐进式 rehash 让百万级键值对的扩容也不会造成延迟毛刺。同时，Redis 对字符串键使用带随机种子的 SipHash，专门防御哈希碰撞攻击。

JDK 的 ThreadLocalMap 则反其道而行，选择开放寻址加线性探测：键是弱引用对象，冲突时顺序向后找空槽，换取更紧凑的内存和更好的缓存局部性。三种工业实现，三种取舍。

对比与权衡

维度 拉链法 开放寻址
存储结构 桶外挂链表或树，有指针开销 全部元素在数组内，更紧凑
装载因子 可超过 1，性能随链长线性退化 必须小于 1，接近 1 时探测数陡增
缓存局部性 跳指针访问，较差 顺序探测，较好
删除 摘除节点即可 需要墓碑标记或重建探测链
极端退化防御 可以树化兜底 只能靠扩容和换哈希函数
代表实现 Java HashMap、Redis dict ThreadLocalMap

面试视角

拉链法和开放寻址怎么选？ 数据规模不稳定、可能超预期、删除频繁时用拉链法，它对高装载因子更宽容；键值小、规模可控、追求内存紧凑和缓存命中时用开放寻址。通用 Map 实现几乎都选拉链法。

扩容为什么摊还是 O(1)？ 单次扩容要迁移全部元素，是 O(n)；但容量翻倍意味着两次扩容之间至少有 n/2 次插入在「攒路费」，迁移总成本平摊到每次插入上是常数。Redis 的渐进式 rehash 则是把这笔账摊到每次操作上，连一次性的停顿都省掉。

HashMap 为什么要扰动？ 容量是 2 的幂时寻址只取哈希值低位，若键的 hashCode 高位差异大、低位雷同，冲突会集中爆发。把高 16 位异或进低位，让高位差异参与定位，碰撞率显著下降。

平均 O(1) 是绝对保证吗？ 不是，它依赖分布均匀与装载受控两个前提。恶意构造的碰撞键能让拉链法的桶退化成 O(n) 长链，这正是服务端采用随机种子哈希、JDK 8 引入树化的动因。

可变对象能做键吗？ 不能。放入后再修改参与哈希的字段，节点会卡在旧桶里，按新状态查找永远落空，形成逻辑丢失和内存泄漏。键应当不可变。

小结

  • 哈希表 = 数组 + 哈希函数 + 冲突策略；平均 O(1) 的前提是分布均匀、装载受控。
  • 拉链法宽容、易删、可树化；开放寻址紧凑、缓存友好但怕高装载因子。
  • 翻倍扩容把 O(n) 迁移摊还成常数；渐进式 rehash 进一步摊到每次操作上。
  • 工程三原则：键不可变且遵守 equals/hashCode 契约、预估容量避免反复扩容、并发场景不要裸用普通实现。