哈希表：散列函数、冲突解决与扩容

你有没有遇到过这种尴尬：数组按下标访问是 O(1)，可它要求"下标必须是整数"；而真实世界里的键往往是字符串（"apple"）、对象（一个 User）、甚至一段二进制。我们想问的是——能不能让任意类型的键，也拥有接近 O(1) 的查找速度？

哈希表（Hash Table，也叫散列表）就是这个问题的答案，也是 Java HashMap、Python dict、C++ unordered_map 背后的真正引擎。它把"键"压缩成一个数组下标，于是插入、查找、删除都甩掉了"逐个比较"的包袱。但它不是免费的午餐：冲突（collision） 一定会发生，怎么设计散列函数、怎么消解冲突、什么时候扩容，正是本篇要讲清楚的三件事。

一、是什么：哈希表的三件套

一句话：哈希表 = 一个数组（桶 buckets）+ 一个散列函数（hash function）+ 一套冲突解决机制。

散列函数 h(key) 把任意键映射到一个整数下标 0..m-1，我们就去数组的那个位置存取。理想情况下每次都 O(1)。

本质一句话：哈希表用"计算下标"代替"逐个比较"，把查找的期望代价压到 O(1)；代价是必须容忍并妥善处理冲突。

二、散列函数：把键压成下标

2.1 Java 里的 hashCode

Java 中每个对象都有 hashCode()，返回 int（32 位，可为负）。字符串的 hashCode 是经典多项式累加法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// String.hashCode() 的等价实现
public static int hashCode(String s) {
    int h = 0;
    for (int i = 0; i < s.length(); i++) {
        h = 31 * h + s.charAt(i);   // h = 31*h + c
    }
    return h;
}

public static void main(String[] args) {
    System.out.println("\"apple\".hashCode() = " + "apple".hashCode());
    System.out.println("\"banana\".hashCode() = " + "banana".hashCode());
    System.out.println("hashCode(\"apple\") = " + hashCode("apple"));
}

1
2
3

"apple".hashCode() = 93029210
"banana".hashCode() = -921901814
hashCode("apple") = 93029210

注意 banana 的 hashCode 是负数——所以压缩成下标时必须先抹掉符号位，否则 % m 会得到负下标越界。惯用写法 (h & 0x7fffffff) % m 或 (h % m + m) % m。

2.2 压缩函数（compression）

直接拿 32 位 hashCode 当下标不现实（数组没那么大）。常用两种压缩：

• 取模：index = (hashCode & 0x7fffffff) % m，m 取素数可减少聚集。
• 位与（Java 8+ HashMap 的做法）：容量 m 取 2 的幂，index = hashCode & (m - 1)。速度快，但要求 hashCode 自身高位也参与扰动（Java 用 hash ^ (hash >>> 16) 把高位混进来），否则容易冲突。

坑①：散列函数必须稳定（同一个键每次算出来一样）且分布均匀。若 h(key)=key % 2，所有偶数全挤在 0 号桶，直接退化成链表。

三、冲突解决： unavoidable，但可治

鸽巢原理告诉我们：桶数 m 少于键数 n 时，冲突必然发生。两大主流治法：

3.1 链地址法（separate chaining）

每个桶挂一条链表（Java 8 之后，桶过长会转成红黑树）。冲突的元素都串在同一个桶下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

// 简化版：链地址法哈希表（键为 String，值为 Integer）
import java.util.*;

class ChainingHash {
    static class Node { String key; int val; Node next;
        Node(String k, int v, Node n){key=k;val=v;next=n;} }
    private Node[] buckets;
    private int size = 0;
    ChainingHash(int m){ buckets = new Node[m]; }

    private int idx(String k){ return (k.hashCode() & 0x7fffffff) % buckets.length; }

    void put(String k, int v){
        int i = idx(k);
        for (Node p = buckets[i]; p != null; p = p.next)
            if (p.key.equals(k)) { p.val = v; return; }   // 已存在则更新
        buckets[i] = new Node(k, v, buckets[i]);          // 头插
        size++;
    }
    Integer get(String k){
        for (Node p = buckets[k.hashCode() & 0x7fffffff % buckets.length]; p != null; p = p.next)
            if (p.key.equals(k)) return p.val;
        return null;
    }
    boolean contains(String k){ return get(k) != null; }
    int size(){ return size; }

    public static void main(String[] args){
        ChainingHash h = new ChainingHash(4);
        h.put("apple", 3); h.put("banana", 5); h.put("cat", 7);
        System.out.println("get(\"apple\") = " + h.get("apple"));
        System.out.println("contains(\"dog\") = " + h.contains("dog"));
        System.out.println("size = " + h.size());
    }
}

1
2
3

get("apple") = 3
contains("dog") = false
size = 3

3.2 开放寻址法（open addressing）

不另开链表，冲突时按规则在数组内往后找空位：线性探测（i, i+1, i+2…）、二次探测、双重散列。查找时沿同一条探测序列走，直到命中或遇空。

坑②：开放寻址的"删除"不能简单置空——否则会切断后续元素的探测链。需标记为"已删除（tombstone）"，查找时跳过、插入时可复用。

怎么选？ 装载因子 α = n/m 低时两者都快；α 高时链地址法更稳（退化成 O(α)），开放寻址对缓存更友好但易"聚集"。

四、扩容（rehash）：为什么需要它

随着元素增多，α 上升，冲突暴涨，操作退化。当 α 超过阈值（Java 默认 0.75），就扩容：新建一个约 2 倍大的桶数组，把旧元素全部重新散列搬过去（rehash）。

1
2
3
4

// 触发扩容的伪逻辑（贴近 HashMap）
if (size > buckets.length * LOAD_FACTOR) {   // LOAD_FACTOR = 0.75
    resize(2 * buckets.length);              // 新容量翻倍
}

本质一句话（扩容）：扩容把 O(1) 的均摊代价"分期付款"——单次 rehash 是 O(n)，但均摊到每次插入仍是 O(1)（类似动态数组的均摊分析）。这正是哈希表能长期保持高效的秘密。

五、Java HashMap vs C++：对照看清

关键取舍：要"键有序"或"最坏稳定 O(log n)" → 用红黑树（std::map / TreeMap）；要"平均最快的查找" → 用哈希表。C++ 的 unordered_map 最坏仍是 O(n)（糟糕的散列会被故意攻击打满），这正是它和 Java 工程选择上的差异。

六、小结

哈希表是"用空间换时间、用计算换比较"的典范：

• 是什么：数组 + 散列函数 + 冲突解决，给任意键提供 O(1) 平均访问。
• 坑：冲突不可避免（鸽巢原理）；负 hashCode 要先抹符号；开放寻址删除要用 tombstone；α 过高会退化。
• 本质一句话：哈希表把"比较查找"变成"计算下标"，靠好的散列 + 冲突处理 + 适时扩容，把期望代价稳在 O(1)；它不保证有序，也不保证最坏情况——这两点恰恰是红黑树和堆的舞台。

带着三个问题读每一篇会更有收获：① 我的散列函数真的均匀吗？ ② 冲突用链还是开放寻址更合适？ ③ 负载因子设多少才不频繁扩容、又不浪费内存？