哈希表

哈希表是工程中使用最频繁的数据结构：以均摊 $O(1)$ 完成插入、查找、删除。它把任意键映射到数组下标——"任意"带来了冲突、扩容与安全性三组设计问题。

原理

两个组成部分：

哈希函数 $h$ ：把键映射到 $[0, m)$ 。要求确定性（同键同值）与均匀性（键均匀散布，最坏情况才不退化）。
冲突解决： $m$ 小于键的取值空间，冲突不可避免。

哈希表的期望 $O(1)$ 来自均匀性假设，最坏情况是 $O(n)$ （所有键冲突）。

冲突解决

链地址法（separate chaining）

每个桶挂一个链表，冲突的键串在同一桶。装填因子 $\alpha = n/m$ 可以超过 1，期望查找 $O(1 + \alpha)$ 。实现简单、删除容易，是指针语言（Java HashMap）的主流。

开放寻址（open addressing）

冲突后按探查序列在数组内另找位置：线性探查（ $h+i$ ）、二次探查、双重哈希。无需指针、缓存友好（探查是连续内存），但装填因子必须保持较低（ $\alpha \lesssim 0.7$ ），删除要用墓碑标记。现代高性能实现（Google dense_hash_map、Facebook F14、Rust hashbrown）都是开放寻址。

扩容

$\alpha$ 超过阈值就扩容：分配更大的数组（通常 2 倍）并把所有元素重新哈希（rehash）。单次扩容 $O(n)$ ，均摊到每次插入仍是 $O(1)$ （→ 均摊分析）。对延迟敏感的服务要避免单次扩容的停顿：增量式扩容（新旧表并存、逐步迁移，Redis 的做法）把 $O(n)$ 摊到多次操作。

哈希函数的选择

通用场景：SipHash、xxHash——兼顾速度与抗碰撞；
哈希表用的哈希与密码学哈希是两回事：前者只求快与均匀，不要求抗碰撞；后者（SHA-256）要求抗原像与碰撞，慢得多（→ 哈希函数与消息认证）；
哈希碰撞攻击（HashDoS）：攻击者构造全部冲突的键，把 $O(1)$ 退化成 $O(n)$ 。对策：带随机种子的哈希（SipHash 的设计动机之一）、限制请求体。

一致性哈希

分布式场景下，"服务器数量变化"就是哈希表的扩容：普通取模 $h \bmod m$ 会让几乎所有键重新分配。一致性哈希把键与节点都放到环上，键归属顺时针遇到的第一个节点——增删节点只迁移约 $1/m$ 的键。虚拟节点（每物理节点多个环上位置）让负载更均匀。它是分布式缓存（Memcached 集群、Dynamo）的基础，与复制与分片直接相关。

代码示例

class OpenAddressingMap:
    def __init__(self, cap=8):
        self.cap, self.size = cap, 0
        self.keys, self.vals = [None] * cap, [None] * cap

    def _probe(self, key):
        i = hash(key) % self.cap
        while self.keys[i] is not None and self.keys[i] != key:
            i = (i + 1) % self.cap      # 线性探查
        return i

    def put(self, key, val):
        if self.size + 1 > 0.7 * self.cap:   # 装填因子阈值
            self._resize(2 * self.cap)
        i = self._probe(key)
        if self.keys[i] is None:
            self.size += 1
        self.keys[i], self.vals[i] = key, val

    def get(self, key):
        i = self._probe(key)
        return self.vals[i] if self.keys[i] == key else None

本章要点

哈希表的 $O(1)$ 是期望，来自均匀性假设；最坏 $O(n)$ （全部冲突或被攻击）
链地址法简单且删除容易；开放寻址缓存友好但要求低装填因子
扩容均摊 $O(1)$ ；延迟敏感服务用增量式扩容避免停顿
哈希表哈希不要求抗碰撞，与密码学哈希是两回事；带种子防 HashDoS
一致性哈希让增删节点只迁移约 $1/m$ 的键，是分布式缓存的基础