📚 课程目录第3章哈希表原理

哈希表原理：从 O(n) 到 O(1) 的魔法

哈希表，说白了就是数组的「升级版」。数组用下标找元素，O(1) 搞定。但现实世界里，我们很少用整数当 key——更多时候是字符串、对象、甚至复杂结构。哈希表就是来解决这个问题的：把任意 key 映射成数组下标，然后继续享受 O(1) 的快乐。

我刚开始学的时候，觉得哈希表不就是个「高级数组」嘛。后来在项目中踩过坑才明白，哈希函数怎么写、冲突怎么处理、装多满了要扩容——这些细节才是决定性能的关键。

哈希函数：把任意 key 变成整数

哈希函数的核心任务就一个：输入任意 key，输出一个非负整数。这个整数再对数组长度取模，就得到了存储位置。

好的哈希函数要满足三个条件：

确定性：同一个 key 永远得到同一个哈希值
均匀性：不同 key 的哈希值尽量均匀分布
高效性：计算要快，不能比查找本身还慢

举个最简单的例子——Java 中 String 的哈希函数：

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + value[i];
        }
        hash = h;
    }
    return h;
}

为什么用 31？因为 31 是质数，而且 31 * h 可以被 JVM 优化成 (h << 5) - h，位运算比乘法快得多。我在项目中自己设计哈希函数时，也习惯选一个合适的质数做乘数——这能明显减少碰撞。

我的习惯：设计哈希函数时，先想想你的 key 有什么规律。如果 key 是连续的整数，直接取模就行；如果是字符串，用质数乘积累加；如果是自定义对象，把每个关键字段的哈希值组合起来。

冲突解决：两个 key 撞到同一个位置怎么办？

哈希函数再完美，也避免不了冲突——因为数组长度有限，而 key 的数量可能无限。这就是「鸽巢原理」：10 个格子放 11 只鸽子，至少有一个格子有两只。

业界主流有两种解决思路：链地址法和开放寻址法。

链地址法

每个数组元素不再存单个值，而是存一个链表（或红黑树）的头节点。冲突了？直接往链表后面挂。

Java 的 HashMap 就是典型代表：

// 简化版，实际源码更复杂
class HashMap<K, V> {
    Node<K, V>[] table;
    
    V put(K key, V value) {
        int index = hash(key) % table.length;
        Node<K, V> head = table[index];
        
        // 遍历链表，找有没有相同的 key
        for (Node<K, V> n = head; n != null; n = n.next) {
            if (n.key.equals(key)) {
                V old = n.value;
                n.value = value;
                return old;
            }
        }
        
        // 没找到，插到链表头部
        table[index] = new Node<>(key, value, head);
        return null;
    }
}

链地址法的优点是实现简单，删除方便。缺点是链表太长时，查找退化成 O(n)。Java 8 做了优化——链表长度超过 8 时转成红黑树，把最坏情况降到 O(log n)。

我曾经踩过的坑：用 HashMap 存大量数据时，如果哈希函数写得不好，所有 key 都撞到同一个桶里。结果 HashMap 退化成链表，O(1) 变 O(n)。那次线上接口超时报警，查了半天才发现是哈希冲突太严重。后来我养成了习惯——自定义对象做 key 时，一定重写 hashCode() 和 equals()，并且保证 hashCode() 的分布足够均匀。

开放寻址法

不额外申请链表，直接在数组里找下一个空位。常见的探测方式有三种：

探测方式	公式	特点
线性探测	`index = (hash + i) % size`	简单，但容易产生「一次聚集」
二次探测	`index = (hash + i²) % size`	减少聚集，但可能跳不到所有位置
双重哈希	`index = (hash1 + i * hash2) % size`	分布最均匀，但计算开销大

Python 的 dict 用的就是开放寻址法 + 二次探测。为什么 Python 不用链地址法？因为 Python 的对象都是指针，链表的额外内存开销太大。开放寻址法把所有数据存在连续内存里，缓存友好，查找更快。

但开放寻址法有个致命问题——删除很麻烦。你不能直接置空，否则会断掉探测链。通常用「懒删除」：标记为 deleted，而不是真的清空。

// 开放寻址法 - 线性探测的删除
V remove(K key) {
    int index = hash(key) % size;
    while (table[index] != null) {
        if (table[index].key.equals(key)) {
            V value = table[index].value;
            table[index] = DELETED;  // 标记删除，不是置空
            return value;
        }
        index = (index + 1) % size;
    }
    return null;
}

  选型建议：

  - 内存充足、删除操作少 → 链地址法（Java HashMap 风格）

  - 内存敏感、追求缓存性能 → 开放寻址法（Python dict 风格）

  - 数据量小、实时性要求高 → 开放寻址法更简单

  - 数据量大、删除频繁 → 链地址法更稳妥

装载因子：什么时候该扩容？

装载因子 = 已存储元素数量 / 数组总长度。它衡量的是哈希表的「拥挤程度」。

你想想看，装载因子越大，冲突概率越高，性能越差。但装载因子太小，内存浪费严重。这是个 trade-off。

场景	推荐装载因子	原因
时间敏感（查找为主）	0.5 - 0.6	冲突少，查找快
平衡模式	0.75	Java HashMap 默认值，时间和空间的折中
内存敏感（空间优先）	0.8 - 0.9	节省内存，但冲突增多

为什么 Java 选 0.75？我记得看过一个数学分析——在随机哈希函数下，装载因子 0.75 时，链表平均长度约 0.5，查找效率接近 O(1)。再高一点，性能就开始明显下滑了。

扩容时要做两件事：

申请一个更大的数组（通常是原来的 2 倍）
把所有旧数据重新哈希到新数组里

这个过程叫 rehash。为什么不能直接复制？因为数组长度变了，hash % size 的结果也变了，每个元素都得重新计算位置。

注意：rehash 是 O(n) 操作。如果你知道数据量大概有多大，最好在初始化时就指定容量，避免频繁扩容。我见过一个线上事故——HashMap 没设初始容量，数据从 100 万涨到 1000 万，期间扩容了 4 次，每次都要停顿几百毫秒。后来改成 new HashMap<>(size / 0.75f + 1)，一次扩容都没发生。

一张图看懂哈希表核心逻辑

下面这张 SVG 图展示了哈希表的完整工作流程：从 key 到哈希函数，再到冲突处理，最后到扩容决策。

实战中的几个关键决策

说了这么多理论，最后分享几个我在项目中用到的经验：

初始容量怎么设？ 如果你预估数据量是 N，设成 N / 0.75 + 1。这样刚好在扩容阈值附近，不会浪费太多内存，也不会频繁扩容。
自定义对象做 key 时，一定要同时重写 hashCode() 和 equals()。只写一个，HashMap 就废了——它俩是配套的，缺一不可。
并发场景别用 HashMap。Java 的 HashMap 在并发 put 时可能死循环（JDK 7 的 bug），用 ConcurrentHashMap 替代。
小数据量别用哈希表。如果数据少于 20 个，线性查找可能更快——哈希函数本身也有开销。

我的调试技巧：怀疑哈希表性能问题时，先打印每个桶的元素数量分布。如果某个桶的元素特别多，说明哈希函数有问题。我常用 table.length 和 size 算一下当前装载因子，如果超过 0.75 且性能下降明显，就该考虑扩容或优化哈希函数了。

哈希表看起来简单，但每个细节都藏着性能的魔鬼。理解了哈希函数、冲突解决和装载因子这三块，你就能写出真正 O(1) 的代码——而不是「看起来 O(1)，实际 O(n)」的伪哈希表。