Hash Table

什么是哈希表

哈希表 (Hash Table) 通过哈希函数将键 (key) 映射为数组下标，从而实现近乎 O(1) 的查找、插入和删除。

核心流程：

flowchart LR
  A["key"] --> B["hash(key)"]
  B --> C["index = hash % size"]
  C --> D["buckets[index]"]
  D --> E["value"]

A Hash table is a data structure used to insert, look up, and remove key-value pairs quickly. It operates on the hashing concept, where each key is translated by a hash function into a distinct index in an array.

— GeeksforGeeks: Hash Table

时间复杂度

最坏情况发生在所有 key 都哈希到同一个桶，退化为链表遍历。好的哈希函数 + 合理负载因子可以避免这种情况。

哈希函数

好的哈希函数需要满足：

• 确定性：相同输入总是产生相同输出
• 均匀分布：输出均匀分散到各个桶，减少冲突
• 高效计算：计算速度快

常见方法

除留余数法 (Division Method) — 最常用

h(k) = k mod m

m 最好选质数，且不要接近 2 的幂次。

乘法取整法 (Multiplication Method)

h(k) = floor(m * (k * A mod 1))

Knuth 建议常数 A 取黄金比例 0.6180339887。

字符串哈希示例 (Stanford CS106B)：

int hashCode(string key) {
    int hashVal = 0;
    for (int i = 0; i < key.length(); i++) {
        hashVal = (127 * hashVal + key[i]) % 16908799;
    }
    return hashVal;
}

哈希冲突

不同的 key 映射到同一个桶，就产生了哈希冲突。根据生日悖论，2500 个 key 哈希到 100 万个桶中，冲突概率就高达 95%，所以冲突是不可避免的。(Stanford CS106B)

两种主流解决方案：

链地址法 (Separate Chaining)

每个桶维护一个链表，冲突的元素追加到链表尾部：

Bucket 0: --> [k1, v1] --> [k5, v5] --> null
Bucket 1: --> [k2, v2] --> null
Bucket 2: --> null
Bucket 3: --> [k3, v3] --> [k7, v7] --> null

优点：实现简单，不怕装满，删除方便

缺点：链表指针额外占内存，缓存局部性差

开放寻址法 (Open Addressing)

所有元素都存在数组内部，冲突时按照探测序列寻找下一个空槽：

线性探测 (Linear Probing)

h(k, i) = (h(k) + i) mod m     // i = 0, 1, 2, 3 ...

逐个往后找空位。缓存友好，但容易产生聚集 (clustering)，连续占用的槽越长，后续插入越慢。

二次探测 (Quadratic Probing)

h(k, i) = (h(k) + i^2) mod m   // i = 0, 1, 2, 3 ...

步长按平方增长 (+1, +4, +9, +16…)，缓解了线性探测的聚集问题。

双重哈希 (Double Hashing)

h(k, i) = (h1(k) + i * h2(k)) mod m

用两个哈希函数计算探测步长，分布最均匀，无聚集问题。h2(k) 必须与 m 互质。

三种探测方式对比

参考：GeeksforGeeks: Open Addressing

负载因子与扩容

负载因子 (Load Factor)：

α = n / m    // n = 已存元素数, m = 桶数量

负载因子越大，冲突概率越高，性能越差。当 α 超过阈值时，哈希表会扩容 (通常翻倍) 并对所有元素重新哈希 (Rehashing)。

单次扩容是 O(n)，但因为扩容频率很低，均摊插入复杂度仍为 O(1)。

TypeScript 实现

基于链地址法实现一个完整的哈希表，包含自动扩容（点击左下角 Console 查看输出）：

实现要点：

• 哈希函数：采用 hash * 31 + charCode (与 Java String.hashCode 同理)，| 0 保证 32 位整数运算
• 冲突处理：每个桶用链表存储，新节点插入链表头部 (O(1))
• 自动扩容：负载因子超过 0.75 时容量翻倍，所有元素重新哈希
• 删除操作：维护 prev 指针，处理头节点和中间节点两种情况

实际语言中的实现

几个有意思的实现细节：

• Java HashMap (Java 8+)：当某个桶的链表长度超过 8 且桶总数大于等于 64 时，链表会转换为红黑树，查找从 O(n) 优化到 O(log n)。 (Java HashMap Internals)
• Python dict (3.6+)：使用 Compact Dict 结构，索引数组 + 紧凑条目数组，既节省内存又保持插入顺序。 (Python Behind the Scenes)
• V8 Map：使用确定性哈希表维护插入顺序 (ES6 规范要求)，哈希码是随机数，与对象值无关。 (V8 Blog)

参考资料

• Wikipedia: Hash Table
• MIT 6.006: Hashing
• Stanford CS106B: Hashing
• GeeksforGeeks: Hash Table