哈希表：O(1) 的代价

第八章：哈希表 — O(1) 的代价

你在一个有 100 万条记录的数据库里查找用户名 "alice"。如果数据是数组，你需要遍历 100 万次；如果数据是排序数组加二分查找，需要约 20 次比较；如果数据在哈希表里，平均只需要 1 次。

O(1) 查找听起来像魔法。但魔法是有代价的——额外的内存、哈希冲突、扩容开销、以及最坏情况下的退化。这一章会告诉你哈希表到底怎么工作，代价是什么，以及什么时候不该用它。

Level 1 · 你需要知道的

8.1 哈希表的基本思想

哈希表的核心思想极其简单：用一个函数把键映射到数组下标，然后直接定位。

# 最简单的哈希表：用取模做哈希函数
class SimpleHashTable:
    def __init__(self, capacity=8):
        self.capacity = capacity
        self.buckets = [None] * capacity

    def _hash(self, key):
        return hash(key) % self.capacity

    def put(self, key, value):
        idx = self._hash(key)
        self.buckets[idx] = (key, value)  # 注意：这里没处理冲突！

    def get(self, key):
        idx = self._hash(key)
        pair = self.buckets[idx]
        if pair and pair[0] == key:
            return pair[1]
        return None

但这个实现有致命缺陷：如果两个不同的键映射到同一个下标（哈希冲突），后面的会覆盖前面的。

8.2 哈希冲突解决：链地址法

最直觉的解决方案：每个桶不是存一个元素，而是存一个链表（或列表）。

class ChainedHashTable:
    def __init__(self, capacity=8):
        self.capacity = capacity
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]

    def _hash(self, key):
        return hash(key) % self.capacity

    def put(self, key, value):
        idx = self._hash(key)
        bucket = self.buckets[idx]
        # 如果 key 已存在，更新
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        # 否则追加
        bucket.append((key, value))
        self.size += 1
        # 检查是否需要扩容
        if self.size / self.capacity > 0.75:
            self._resize(self.capacity * 2)

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        return None

    def delete(self, key):
        idx = self._hash(key)
        bucket = self.buckets[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        return False

    def _resize(self, new_capacity):
        old_buckets = self.buckets
        self.capacity = new_capacity
        self.buckets = [[] for _ in range(new_capacity)]
        self.size = 0
        for bucket in old_buckets:
            for k, v in bucket:
                self.put(k, v)

负载因子（Load Factor）= 元素数量 / 桶数量。当负载因子超过阈值（通常 0.75），触发扩容。

8.3 哈希冲突解决：开放寻址法

另一种策略：冲突时不用链表，而是在数组中寻找下一个空位。

class OpenAddressHashTable:
    EMPTY = object()
    DELETED = object()  # 墓碑标记

    def __init__(self, capacity=8):
        self.capacity = capacity
        self.size = 0
        self.keys = [self.EMPTY] * capacity
        self.values = [None] * capacity

    def _hash(self, key):
        return hash(key) % self.capacity

    def _probe(self, key):
        """线性探测：找到 key 所在位置或第一个空位"""
        idx = self._hash(key)
        first_deleted = -1
        for _ in range(self.capacity):
            if self.keys[idx] is self.EMPTY:
                return (first_deleted if first_deleted >= 0 else idx), False
            if self.keys[idx] is self.DELETED:
                if first_deleted < 0:
                    first_deleted = idx
            elif self.keys[idx] == key:
                return idx, True
            idx = (idx + 1) % self.capacity  # 线性探测
        return (first_deleted if first_deleted >= 0 else -1), False

    def put(self, key, value):
        if self.size * 3 >= self.capacity * 2:  # 负载因子 > 2/3
            self._resize(self.capacity * 2)
        idx, found = self._probe(key)
        if not found:
            self.size += 1
        self.keys[idx] = key
        self.values[idx] = value

    def get(self, key):
        idx, found = self._probe(key)
        if found:
            return self.values[idx]
        return None

    def delete(self, key):
        idx, found = self._probe(key)
        if found:
            self.keys[idx] = self.DELETED  # 不能直接设为 EMPTY
            self.values[idx] = None
            self.size -= 1
            return True
        return False

    def _resize(self, new_capacity):
        old_keys, old_values = self.keys, self.values
        self.capacity = new_capacity
        self.keys = [self.EMPTY] * new_capacity
        self.values = [None] * new_capacity
        self.size = 0
        for i, k in enumerate(old_keys):
            if k is not self.EMPTY and k is not self.DELETED:
                self.put(k, old_values[i])

为什么删除要用墓碑（DELETED）而不是直接设为 EMPTY？ 因为如果 A 和 B 冲突（B 在 A 后面），删除 A 后设为 EMPTY，查找 B 时会在 A 的位置提前终止，以为 B 不存在。墓碑告诉探测算法："这里曾经有人住过，继续往下找。"

8.4 两种方法对比

Python dict 用的是哪种？ 开放寻址法。因为 CPython 追求紧凑的内存布局和更好的 Cache 性能。Java HashMap 用的是链地址法（桶内先链表，长度 > 8 转红黑树）。

8.5 Python dict 使用技巧

# 常见用法
d = {}
d["key"] = "value"           # O(1) 插入
val = d.get("key", "default") # O(1) 查找，key 不存在返回默认值
"key" in d                    # O(1) 存在性检查
del d["key"]                  # O(1) 删除

# 计数器模式
from collections import Counter
counts = Counter("abracadabra")
# Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})

# defaultdict 避免 KeyError
from collections import defaultdict
graph = defaultdict(list)
graph["a"].append("b")  # 不需要先检查 "a" 是否存在

# 字典推导式
squares = {x: x**2 for x in range(10)}

# 有序性：Python 3.7+ dict 保持插入顺序
d = {"b": 2, "a": 1, "c": 3}
list(d.keys())  # ['b', 'a', 'c'] — 保持插入顺序

8.6 set：只有键没有值的哈希表

Python 的 set 底层就是一个哈希表，只存键不存值。

s = set()
s.add(42)           # O(1)
42 in s             # O(1)
s.remove(42)        # O(1)，不存在则 KeyError
s.discard(42)       # O(1)，不存在不报错

# 集合运算
a = {1, 2, 3}
b = {2, 3, 4}
a | b  # 并集 {1, 2, 3, 4}
a & b  # 交集 {2, 3}
a - b  # 差集 {1}
a ^ b  # 对称差 {1, 4}

# 去重
unique = list(set(items))  # 注意：会丢失顺序
# 保序去重
seen = set()
unique = [x for x in items if x not in seen and not seen.add(x)]

Level 2 · 它是怎么运行的

8.7 哈希函数的设计

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

1. 均匀分布：不同的键尽可能映射到不同的桶
2. 快速计算：哈希函数本身要足够快

整数哈希：最简单的是取模 key % capacity，但如果 capacity 是 2 的幂，取模等价于取最低几位，高位信息被丢弃。所以很多实现会先做一次"扰动"（mixing），把高位信息混入低位。

Python 对小整数的哈希就是其本身：hash(42) == 42。但对字符串和大对象，Python 使用 SipHash 算法（Python 3.4+），这是一种密码学安全的哈希函数，能防御哈希碰撞攻击（HashDoS）。

# Python 整数的哈希
hash(42)    # 42
hash(-1)    # -2（特殊处理，因为 -1 在 CPython 内部表示错误）
hash(0)     # 0

# 字符串的哈希每次启动都不同（随机种子）
hash("hello")  # 每次运行结果不同（防 HashDoS）

Java 的扰动函数（HashMap.hash）：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

把高 16 位异或到低 16 位，使得即使数组长度较小（只看低位），也能利用高位的信息。

8.8 CPython dict 的内部实现

CPython 3.6+ 的 dict 使用了一种巧妙的紧凑布局（compact dict），由 Raymond Hettinger 在 2012 年提出。

旧版布局（Python < 3.6）：

[hash|key|value, hash|key|value, —, hash|key|value, —, —, —, —]

问题：大量空槽浪费内存，而且空槽也占据 hash + key + value 的完整空间。

新版布局（Python 3.6+）：

indices:  [1, —, 0, —, 2, —, —, —]   ← 小整数数组（1/2/4/8 字节每项）
entries:  [(hash₀, key₀, val₀),        ← 紧凑数组，按插入顺序
           (hash₁, key₁, val₁),
           (hash₂, key₂, val₂)]

优势：

1. indices 数组每项只需要 1-8 字节（而不是完整的 hash+key+value）
2. entries 数组是紧凑的，没有空洞，天然保持插入顺序
3. 内存节省 20-25%

探测序列：CPython 不是简单的线性探测，而是使用扰动探测（perturbation probing）：

# CPython 的探测序列（伪代码）
perturb = hash_value
idx = perturb % capacity
while slot_occupied:
    idx = (5 * idx + perturb + 1) % capacity
    perturb >>= 5  # 逐渐衰减，最终退化为 (5*idx+1) % capacity

这个序列保证了：

• 初始阶段利用哈希值的所有位（通过 perturb）
• 后期退化为一种特殊的线性同余序列
• 当 capacity 是 2 的幂时，5*idx+1 能遍历所有位置

8.9 扩容（Rehash）机制

当负载因子超过 2/3 时，CPython 触发扩容：

1. 分配新的 indices + entries 数组（容量翻倍或 ×4，取决于当前大小）
2. 遍历旧 entries 数组，重新计算每个键的位置
3. 插入到新数组
4. 释放旧数组

关键问题：rehash 是 O(n) 的，但均摊到每次插入是 O(1)（和动态数组扩容的分析完全一样，详见第 1 章均摊分析）。

缩容：Python dict 不会自动缩容。即使删除了大量元素，内存也不会释放。如果需要释放内存，可以创建一个新的 dict：

# 强制释放内存
d = {k: v for k, v in d.items()}

8.10 一致性哈希

传统哈希：server = hash(key) % N，当 N 变化时（加减服务器），几乎所有键都需要重新映射。

一致性哈希（Consistent Hashing，David Karger 等人 1997 年在 MIT 提出）解决了这个问题：

import hashlib
import bisect

class ConsistentHash:
    def __init__(self, nodes, replicas=150):
        self.replicas = replicas
        self.ring = []           # 排序的哈希环
        self.ring_map = {}       # 哈希值 → 节点
        for node in nodes:
            self.add_node(node)

    def _hash(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def add_node(self, node):
        for i in range(self.replicas):
            h = self._hash(f"{node}:{i}")
            self.ring.append(h)
            self.ring_map[h] = node
        self.ring.sort()

    def remove_node(self, node):
        for i in range(self.replicas):
            h = self._hash(f"{node}:{i}")
            self.ring.remove(h)
            del self.ring_map[h]

    def get_node(self, key):
        if not self.ring:
            return None
        h = self._hash(key)
        idx = bisect.bisect_right(self.ring, h) % len(self.ring)
        return self.ring_map[self.ring[idx]]

# 使用
ch = ConsistentHash(["server-1", "server-2", "server-3"])
print(ch.get_node("user:alice"))  # 映射到某个 server
# 添加 server-4 时，只有约 1/4 的键需要迁移（而不是全部）

为什么用虚拟节点（replicas）？ 如果只有 3 个物理节点，哈希环上只有 3 个点，分布极不均匀。每个节点创建 150 个虚拟节点，总共 450 个点均匀分布在环上，保证负载均衡。

应用：Redis Cluster、Memcached、CDN 负载均衡、分布式数据库的分片策略。

Level 3 · 规范怎么定义的

8.11 哈希表的理论基础

完美哈希（Perfect Hashing）：如果提前知道所有键，可以构造一个没有任何冲突的哈希函数。Fredman、Komlós 和 Szemerédi 在 1984 年证明了这是可能的（FKS 完美哈希），空间 O(n)，查询 O(1) 最坏情况。

实现思路：两级哈希。第一级把 n 个键分到 n 个桶，第二级对每个桶构造一个无冲突的小哈希表。Szemerédi 的定理保证了第二级的总空间是 O(n)。

Cuckoo Hashing（Pagh & Rodler, 2001）：使用两个哈希函数 h₁ 和 h₂，每个键可以在两个位置之一。插入时，如果两个位置都被占了，"踢走"其中一个（像布谷鸟把其他鸟蛋踢出巢），被踢走的键再去自己的另一个位置。

# Cuckoo 哈希的插入伪代码
def cuckoo_insert(key):
    for _ in range(MAX_KICKS):
        pos1 = h1(key) % capacity
        if table1[pos1] is empty:
            table1[pos1] = key
            return
        key, table1[pos1] = table1[pos1], key  # 踢走
        pos2 = h2(key) % capacity
        if table2[pos2] is empty:
            table2[pos2] = key
            return
        key, table2[pos2] = table2[pos2], key  # 再踢
    # 踢了太多次，需要 rehash
    rehash_with_new_functions()
    cuckoo_insert(key)

优点：查找最坏情况 O(1)（只看两个位置）。缺点：插入可能触发连锁踢出。

Robin Hood Hashing（Pedro Celis, 1986）：开放寻址的变体。在探测过程中，如果当前元素的"偏移量"（实际位置离理想位置的距离）小于待插入元素的偏移量，就交换。这使得所有元素的偏移量趋于均匀，减小了最坏情况的查找长度。Rust 的 HashMap（早期版本）曾使用这种策略。

8.12 Python SipHash 与 HashDoS 防御

2011 年，Alexander Klink 和 Julian Wälde 在 28C3（Chaos Communication Congress）上展示了一种攻击：通过构造大量哈希冲突的字符串，使得 Web 框架的哈希表退化为 O(n²)，用少量请求就能打垮服务器（HashDoS）。

Python、Ruby、Perl、PHP 等语言在随后的更新中引入了随机化哈希种子。Python 3.4+ 默认使用 SipHash-2-4（Jean-Philippe Aumasson 和 Daniel J. Bernstein, 2012），这是一种密码学级别的短输入哈希函数：

• 启动时随机生成 128 位种子
• 相同的字符串在不同进程中产生不同的哈希值
• 攻击者无法预测哈希值，因此无法构造冲突

# 验证：每次运行结果不同
import sys
print(sys.hash_info.algorithm)  # 'siphash24'

# 同一进程内 hash 是确定的
assert hash("hello") == hash("hello")

# 但不同进程间 hash 不同
# python3 -c "print(hash('hello'))"  → 不同的值

8.13 通用哈希（Universal Hashing）

Carter 和 Wegman 在 1979 年提出了通用哈希族的概念：一组哈希函数的集合 H，从中随机选一个函数 h，对任意两个不同键 x ≠ y，碰撞概率 Pr[h(x) = h(y)] ≤ 1/m（m 是桶数）。

这是一个非常强的保证：不管输入数据有多恶意，随机选择哈希函数就能让期望冲突数最优。

一个简单的通用哈希族（适用于整数键）：

h_{a,b}(x) = ((a * x + b) mod p) mod m

其中 p 是大于所有键值的素数，a ∈ {1, ..., p-1}，b ∈ {0, ..., p-1} 随机选择。

Level 4 · 边界与陷阱

8.14 可变对象不能做 dict 的键

Python 的 dict 要求键是可哈希的（hashable），即实现了 __hash__ 方法且值不变。列表（list）不可哈希：

d = {}
d[[1, 2]] = "value"  # TypeError: unhashable type: 'list'
d[(1, 2)] = "value"  # OK，tuple 是可哈希的

# 但 tuple 里包含 list 也不行
d[([1], [2])] = "value"  # TypeError: unhashable type: 'list'

为什么？ 如果键可以被修改，修改后的哈希值变了，就再也找不到原来的位置了。这是哈希表正确性的基本要求。

自定义对象做键：需要同时实现 __hash__ 和 __eq__：

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return isinstance(other, Point) and self.x == other.x and self.y == other.y

d = {Point(1, 2): "A"}
print(d[Point(1, 2)])  # "A"

规则：如果两个对象 __eq__ 相等，它们的 __hash__ 必须相同。反过来不要求（不同对象可以有相同的哈希值——这就是冲突）。

8.15 dict 遍历时修改的陷阱

d = {"a": 1, "b": 2, "c": 3}

# 错误：遍历时修改大小
for key in d:
    if d[key] == 2:
        del d[key]  # RuntimeError: dictionary changed size during iteration

# 正确：先收集要删除的键
to_delete = [k for k, v in d.items() if v == 2]
for k in to_delete:
    del d[k]

# 或者用字典推导创建新 dict
d = {k: v for k, v in d.items() if v != 2}

8.16 哈希表的最坏情况

面试考点：哈希表的平均复杂度是 O(1)，但最坏情况是 O(n)。什么时候会出现最坏情况？

1. 所有键冲突到同一个桶：链地址法退化为链表 O(n)；开放寻址法探测整个数组 O(n)
2. 恶意输入（HashDoS）：攻击者构造冲突键，详见 Level 3 SipHash
3. 扩容时的短暂卡顿：rehash 是 O(n) 的，虽然均摊是 O(1)，但单次操作可能很慢

Redis 的渐进式 rehash 解决了第 3 个问题：Redis 不是一次性 rehash，而是在后续的每次读写操作中，顺便迁移一小部分键。这样单次操作的延迟不会突然飙升，但代价是在 rehash 期间同时维护新旧两个哈希表。

详见本站 Redis 书第 6 章"Hash 表与渐进式 rehash"。

8.17 面试高频题

题目 1：两数之和（LeetCode #1）

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

核心：用哈希表把 O(n²) 的嵌套循环变成 O(n) 的单次遍历。

题目 2：字母异位词分组（LeetCode #49）

from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))  # 排序后作为哈希键
        groups[key].append(s)
    return list(groups.values())

# 更优：用字母频率作为键，避免排序
def group_anagrams_v2(strs):
    groups = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        groups[tuple(count)].append(s)
    return list(groups.values())

题目 3：最长连续序列（LeetCode #128）

def longest_consecutive(nums):
    num_set = set(nums)
    max_len = 0
    for num in num_set:
        # 只从序列起点开始计数
        if num - 1 not in num_set:
            length = 1
            while num + length in num_set:
                length += 1
            max_len = max(max_len, length)
    return max_len

看起来像 O(n²)（两层循环），实际是 O(n)。因为内层 while 在整个外层 for 过程中总共只执行 n 次（每个元素最多被内层访问一次）。

题目 4：LRU Cache（LeetCode #146）

哈希表 + 双向链表实现 O(1) 的 get 和 put。这是面试中"设计类数据结构"的经典题，我们将在第 38 章详细实现。

本章小结

练习题：

1. 实现一个支持 put, get, delete 的哈希表，使用 Cuckoo Hashing。
2. 为什么 Python 的 frozenset 是可哈希的但 set 不是？
3. 设计一个哈希函数，使得相似的字符串（如 "abc" 和 "abd"）映射到不同的桶。（提示：思考多项式哈希）
4. 一致性哈希中，如果某个节点宕机，它的虚拟节点上的键会迁移到哪里？这些键的分布是否均匀？

下一章预告：第 9 章将介绍布隆过滤器和概率数据结构——当你不需要 100% 准确的答案时，如何用极小的内存实现近似查询。