4.1 哈希表基础

前置：数组与链表，约 35 分钟。本节从 key、哈希值、桶和相等性检查的关系出发，逐步实现一张支持增、改、查、删的链地址哈希表。

key、bucket 与 equality 的第一条规则

哈希表接收一个 key 和一个 value。查询同一 key 时，它先计算哈希值并定位 bucket，再在 bucket 的候选项中用 equality 确认身份。哈希负责缩小范围，不能替代相等性判断。

先建立一张地图

哈希表保存的是 key 到 value 的映射。电话簿里的姓名是 key，电话号码是 value；编译器符号表里的变量名是 key，类型与地址是 value。

一次查询会经过四步：

key
  │  哈希函数
  ▼
hash code（哈希值）
  │  根据容量定位，例如 hash code % bucket_count
  ▼
bucket（桶）
  │  用相等性比较确认具体 key
  ▼
value

这四个概念不能互换：

概念	职责	电话簿例子
key	标识一条映射	"Bob"
value	key 对应的数据	"456"
hash code	哈希函数计算出的整数	某个整数
bucket index	当前表容量下选中的桶位置	hash_code % 8

哈希值通常比桶下标的范围大。表扩容后，同一 key 的哈希值可以保持不变，桶下标却会随桶数量变化。

为什么不用数组逐项查

先看一份线性电话簿：

phone_book = [("Alice", "123"), ("Bob", "456"), ("Charlie", "789")]

def find_phone(entries, name):
    for key, value in entries:
        if key == name:
            return value
    raise KeyError(name)

assert find_phone(phone_book, "Bob") == "456"

数组支持按整数下标随机访问，但这里拿到的是姓名。线性表必须从头比较，最坏会看完 n 条记录，成本为 O(n)。

哈希表先用 key 计算一个桶位置，只在桶内核对候选项。在均匀散列模型下，桶数量随元素量增长并让平均桶长受控时，预期候选数可以保持 O(1)。还要另算哈希与 key 比较的成本。

哈希函数负责什么

下面的教学函数把字符串折叠成一个非负整数。它只用于展示过程，不适合密码、签名、持久化 ID 或真实哈希表实现。

def stable_hash(key):
    if not isinstance(key, str):
        raise TypeError("this teaching hash accepts strings only")

    value = 0
    for char in key:
        value = (value * 31 + ord(char)) & 0xFFFFFFFF
    return value

assert stable_hash("Bob") == 66965
assert stable_hash("Bob") == stable_hash("Bob")

ord(char) 取得 Unicode 码点，乘 31 让字符顺序参与结果。因此 "ab" 与 "ba" 通常得到不同哈希。& 0xFFFFFFFF 把教学结果限制在 32 位无符号范围内。

当前有 8 个桶时，可以用取模定位：

def bucket_index(hash_code, bucket_count):
    if bucket_count <= 0:
        raise ValueError("bucket_count must be positive")
    return hash_code % bucket_count

assert bucket_index(66965, 8) == 5
assert bucket_index(66965, 16) == 5
assert bucket_index(73, 8) == 1
assert bucket_index(73, 16) == 9

Bob 的桶下标在这次扩容中没变，I（哈希值 73）却从 1 变成 9。扩容要求重新计算位置，并不意味着每个 key 都一定换桶。

取模只是常见的教学方案。真实库会根据容量布局、哈希混合策略和运行时约束定位桶。理解“哈希值”和“桶下标”分属两层，比记住某个公式更可靠。

冲突为什么一定会出现

可能的 key 数量通常远多于桶的数量。只要 key 的可能取值多于桶，至少两个 key 就会落到同一桶，这就是鸽巢原理。

在上面的教学函数中，单字符 key "A" 和 "I" 的码点相差 8。容量为 8 时，它们都会落到桶 1：

stable_hash("A") % 8 = 65 % 8 = 1
stable_hash("I") % 8 = 73 % 8 = 1

冲突不表示两个 key 相等，也不说明哈希函数已经失效。哈希表必须在桶内继续比较 key。

key 的相等与哈希契约

一个哈希容器至少依赖两条规则：

1. 两个 key 若相等，它们必须产生相同哈希值。
2. key 存在于容器期间，它的哈希值和相等关系必须保持稳定。

反方向不成立。两个不同 key 可以拥有同一个哈希值，冲突处理正是为这种情况准备的。

Python 用 __eq__() 判断相等，用 __hash__() 提供哈希。按值比较的可变对象容易在插入后“换桶”，因此 list 和 dict 不能作为 dict 的 key；tuple 也只有在其元素都可哈希时才可作为 key。可变对象并非一律不可哈希：使用默认身份相等与身份哈希的自定义实例，可以修改与这两项规则无关的字段。

valid = {
    "apple": "fruit",
    (12, 7): "grid coordinates",
}

try:
    invalid = {["mutable", "list"]: "value"}
except TypeError:
    pass
else:
    raise AssertionError("a list must not be accepted as a dict key")

assert valid["apple"] == "fruit"

Python 默认会随机化 str 和 bytes 的哈希种子。hash("apple") 在同一进程内稳定，跨进程运行时可能变化。它适合当前进程的哈希容器，不适合写入文件后当作稳定编号，也不具备密码学安全性。

用链地址法实现第一张表

链地址法让每个桶保存一组 (key, value)。教学代码用 Python list 表示桶，重点放在映射契约；生产库可以选用其他桶结构。

def stable_hash(key):
    if not isinstance(key, str):
        raise TypeError("this teaching map accepts string keys only")
    value = 0
    for char in key:
        value = (value * 31 + ord(char)) & 0xFFFFFFFF
    return value

class ChainedHashMap:
    def __init__(self, capacity=8):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self._buckets = [[] for _ in range(capacity)]
        self._size = 0

    def __len__(self):
        return self._size

    def _bucket(self, key):
        index = stable_hash(key) % len(self._buckets)
        return self._buckets[index]

    def put(self, key, value):
        bucket = self._bucket(key)
        for position, (stored_key, _) in enumerate(bucket):
            if stored_key == key:
                bucket[position] = (key, value)
                return
        bucket.append((key, value))
        self._size += 1

    def get(self, key):
        for stored_key, value in self._bucket(key):
            if stored_key == key:
                return value
        raise KeyError(key)

    def remove(self, key):
        bucket = self._bucket(key)
        for position, (stored_key, value) in enumerate(bucket):
            if stored_key == key:
                bucket.pop(position)
                self._size -= 1
                return value
        raise KeyError(key)

notes = ChainedHashMap(8)
notes.put("A", "apple note")
notes.put("I", "ink note")       # 与 A 落到同一桶
notes.put("A", "new apple note") # 更新，不增加 size

assert len(notes) == 2
assert notes.get("A") == "new apple note"
assert notes.get("I") == "ink note"
assert notes.remove("A") == "new apple note"
assert notes.get("I") == "ink note"

沿着一次 put 走

假设容量为 8，先插入 "A"，再插入 "I"：

1. 两个 key 都被定位到桶 1。
2. put("A", ...) 扫描空桶，追加第一对映射。
3. put("I", ...) 扫描桶 1，发现 "I" != "A"，于是追加第二对映射。
4. 再次 put("A", ...) 时，循环找到相等 key，替换 value，size 保持 2。

桶内状态如下：

buckets[1] -> [("A", "new apple note"), ("I", "ink note")]

get("I") 不能看到桶 1 就返回 "A" 的 value。它必须逐项比较，直到找到真正相等的 key。

复杂度要连同条件一起记

设 n 为映射数量，m 为桶数量，L 为字符串 key 的长度。本节实现没有自动扩容，固定 m 时不能在 n 不断增长后仍保证平均桶长不变。

操作	桶分布良好且 n/m 受控	最坏桶内比较次数	额外说明
get	预期 O(1) 次桶内比较	O(n)	还要支付计算哈希的 O(L)
put	预期 O(1) 次桶内比较	O(n)	更新也要先找到 key
remove	预期 O(1) 次桶内比较	O(n)	本实现的桶内 pop 还会移动后续引用
空间	O(m + n)	O(m + n)	m 个桶加 n 对映射

“哈希表查询是 O(1)”省略了三个前提：哈希分布合理、负载受到控制、计算哈希和比较 key 的成本可控。若所有 key 都落到同一桶，查找会退化为线性扫描。

本例每次查询都会重新扫描 key 计算哈希，长度 L 时需 Θ(L) 时间；一次字符串相等比较也可能扫描整个字符串。若所有 key 长度至多 L，桶中有 b 项，一次查询最坏为 O((b+1)(L+1))。表中的 O(n) 是候选比较次数，不是忽略字符串长度后的总时间。空间一行统计桶和引用，不含 key/value 自身占用。

分析长字符串、复合对象或攻击者可控输入时，应把哈希计算和最坏碰撞纳入模型。业务代码若只处理长度有上限的 ID，工程上常把 key 操作视作常数成本。

直接使用语言自带映射

学习实现帮助你理解契约，业务代码通常应先选标准库：

语言	常用类型	顺序与失败语义
Python	dict	Python 3.7+ 保留插入顺序；d[key] 缺失时抛 KeyError
Java	HashMap<K,V>	不保证迭代顺序；允许 null key 和 value；不是线程安全容器
C++	std::unordered_map<Key,T>	不提供按 key 排序的遍历；接口区分 find、at 与 operator[]

Java HashMap 文档所说的常数时间依赖哈希分布。C++ 无序关联容器的标准契约要求：等价 key 必须得到相同哈希；多数操作平均很快，最坏仍可能线性。不同语言的返回值、异常和迭代器失效规则并不相同，写工程代码时应查对应版本的 API 文档。

常见误区

把哈希值当成桶下标

哈希值先产生，桶下标再由当前表布局计算。扩容可能改变桶下标，所以要按新布局重新安排旧元素；若实现缓存了哈希值，不必重新扫描 key。

只比较哈希值

相同哈希不代表 key 相等。命中桶后仍要执行相等性比较。

用可变内容做 key

若 key 的哈希在插入后改变，后续查询会去另一个桶。优先使用不可变值，或为自定义类型设计一致且稳定的 __eq__ / __hash__。

把 hash() 当作持久化 ID

Python 字符串哈希默认跨进程变化。需要稳定摘要时，应明确算法、编码与碰撞处理。摘要再稳定也不自动成为唯一编号；涉及密码、签名或防篡改时使用专门的密码学库与协议。

期待哈希表自动排序

Python dict 的插入顺序不等于 key 排序。要按 key 范围查询或有序遍历，应排序 key，或选择树等有序结构。

调试顺序

1. 写下 key 的类型、相等规则和哈希稳定性。
2. 分开打印哈希值与桶下标，确认没有混为一个概念。
3. 构造两个会落入同一桶的 key，测试插入、更新、查询和删除。
4. 检查更新已有 key 时 size 是否错误增加。
5. 检查缺失 key 的失败契约，是异常、空值还是显式结果。
6. 分析复杂度时，写出 n、m 与 key 长度各自代表什么。

动手验证哈希契约

难度	任务	验收点
基础	为 ChainedHashMap 增加 contains	value 为 None 时也能区分“存在”与“缺失”
基础	统计一段文本的词频	先定义大小写与标点规则
进阶	为链地址表加入扩容	旧映射按新容量重新定位，size 不重复累计
进阶	设计复合 key	相等 key 的哈希必须相同；不相等 key 允许碰撞
工程	比较 dict.get、in 和 []	写清缺失 key 的不同语义

再检查一次哈希契约

哈希表没有跳过查找，只是先用哈希缩小候选范围，再用相等性确认身份。预期 O(1) 也不是无条件承诺：哈希分布、负载因子以及 key 的哈希与比较成本都要受控。把这几层分开，扩容时为何必须重新定位、冲突时为何仍要比较 key，也就顺理成章了。

故意让 A 和 I 落入同一个 bucket，查询仍必须取回各自的 value。继续阅读哈希冲突与扩容，看冲突、墓碑删除与 rehash 怎样保持查找路径完整。

官方参考

• Python Data Model: __hash__
• Python Built-in Types: dict
• Java SE 17 HashMap
• C++ unordered associative container requirements