hello-algo 链式地址哈希表实现指南：HashMapChaining、负载因子与再哈希扩容

本文基于 hello-algo 仓库中 链式地址哈希表的 PythonTutor 可视化片段 及其对应的可运行源码 hash_map_chaining.py，完整拆解 HashMapChaining 的数据结构、get/put/remove 三大操作、以负载因子 2/3 为阈值的扩容再哈希机制，帮助读者掌握哈希冲突治理中"分离链接（separate chaining）"方案的工程实现细节。

一、链式地址要解决的问题：桶内哈希冲突

在 哈希表 的最简实现中，每个桶（bucket）只能存放一个键值对。而哈希函数的输入空间（全体 key）远大于输出空间（数组索引），例如对容量为 100 的数组使用 key % 100，后两位相同的所有学号都会映射到同一个桶：

12836 % 100 = 36
20336 % 100 = 36

文档 hash_collision.md 将这种情况定义为哈希冲突（hash collision），并给出两条治理思路：

1. 改良哈希表数据结构，使其在出现冲突时仍能正常工作；
2. 仅当冲突比较严重（负载因子超过阈值）时才执行扩容。

链式地址（separate chaining） 即第一条思路的代表实现：将每个桶从"单个元素"改造为一条"链"，所有映射到同一索引的键值对都存放在同一条链中。hello-algo 的 Python 实现用列表（动态数组）代替了真正的链表来简化代码——因此哈希表结构变为"桶的数组，每个桶本身是一个列表"，如源码注释所示（桶数组）：

self.buckets = [[] for _ in range(self.capacity)]  # 桶数组

这一简化带来的代价在文档中有明确说明：占用空间增大（列表相比裸数组更耗费内存）与查询效率降低（需要线性遍历桶内列表来查找元素）。

二、HashMapChaining 的整体结构与关键参数

HashMapChaining 与配套的 Pair 键值对类是核心结构。在仓库可运行版本 hash_map_chaining.py 中，Pair 并非本地定义，而是从同目录的 array_hash_map.py 导入复用：

sys.path.append(str(Path(__file__).parent.parent))
from chapter_hashing.array_hash_map import Pair   # 复用键值对类

而 PythonTutor 可视化片段（即 hash_map_chaining.md 内嵌的 URL 编码代码）为了让单文件可独立在浏览器中可视化运行，自带了一份等价的 Pair 类定义：

class Pair:
    """键值对"""
    def __init__(self, key: int, val: str):
        self.key = key
        self.val = val

构造方法定义了 5 个关键成员变量（见 hash_map_chaining.py#L17-L23）：

def __init__(self):
    """构造方法"""
    self.size = 0                          # 键值对数量
    self.capacity = 4                       # 哈希表容量
    self.load_thres = 2.0 / 3.0             # 触发扩容的负载因子阈值
    self.extend_ratio = 2                   # 扩容倍数
    self.buckets = [[] for _ in range(self.capacity)]  # 桶数组

参数	默认值	作用
size	0	当前存储的键值对总数，用于计算负载因子、在 put/remove/extend 中维护
capacity	4	桶数组长度，也是哈希取模的除数；扩容时乘以 extend_ratio
load_thres	2/3	负载因子超过该值时触发扩容
extend_ratio	2	每次扩容的放大倍数（容量翻倍）
buckets	[[] for _ in range(capacity)]	桶数组，每个桶是一个列表（链），容纳冲突的键值对

哈希函数与负载因子（见 hash_map_chaining.py#L25-L31）：

def hash_func(self, key: int) -> int:
    """哈希函数"""
    return key % self.capacity

def load_factor(self) -> float:
    """负载因子"""
    return self.size / self.capacity

这里 hash(key) = key，桶索引即 key % capacity。capacity 是成员变量而非常量，是理解扩容机制的关键：扩容改变了 capacity，所有 key 的落桶位置都会随之改变，因此扩容后必须对全部键值对重新取模（再哈希）。负载因子的定义与 Java 中相同（元素数量 / 桶数量），在文档 hash_map.md 的"哈希冲突与扩容"一节中有详细说明，Java HashMap 的对应阈值是 0.75、扩容至 2 倍，本实现则采用 2/3 与 2 倍。

三、get / put / remove 三大操作

查询 get：定位桶后线性遍历

def get(self, key: int) -> str | None:
    """查询操作"""
    index = self.hash_func(key)
    bucket = self.buckets[index]
    # 遍历桶，若找到 key ，则返回对应 val
    for pair in bucket:
        if pair.key == key:
            return pair.val
    # 若未找到 key ，则返回 None
    return None

流程分两步：先用哈希函数把 key 映射到桶索引，再遍历该桶（链）逐一比对 pair.key。桶内为空时直接返回 None，时间开销为 O(1)；最坏情况需要遍历整条链，时间复杂度退化为 O(链长)——这正是文档指出的"查询效率降低"局限。

添加 put：先查扩容，再更新或追加

def put(self, key: int, val: str):
    """添加操作"""
    # 当负载因子超过阈值时，执行扩容
    if self.load_factor() > self.load_thres:
        self.extend()
    index = self.hash_func(key)
    bucket = self.buckets[index]
    # 遍历桶，若遇到指定 key ，则更新对应 val 并返回
    for pair in bucket:
        if pair.key == key:
            pair.val = val
            return
    # 若无该 key ，则将键值对添加至尾部
    pair = Pair(key, val)
    bucket.append(pair)
    self.size += 1

注意两个细节：

• 扩容检查前置：put 的第一步不是计算索引，而是检查 load_factor() > load_thres。这意味着扩容发生在"写入前"，保证新桶数组按新的 capacity 落桶；
• 更新语义：若链中已存在相同 key，只覆盖 pair.val 并立即返回，不增加 size；只有真正新增键值对时才执行 self.size += 1。

删除 remove：定位后从链中摘除

def remove(self, key: int):
    """删除操作"""
    index = self.hash_func(key)
    bucket = self.buckets[index]
    # 遍历桶，从中删除键值对
    for pair in bucket:
        if pair.key == key:
            bucket.remove(pair)
            self.size -= 1
            break

与 开放寻址哈希表 中"不能直接删除"（需 TOMBSTONE 懒删除标记）形成鲜明对比：链式地址可以安全地原地删除，因为删除链中某个节点不会截断任何探测路径，这是分离链接方案的显著优势之一。

用驱动代码走一遍完整流程

源码文件末尾（hash_map_chaining.py#L94-L118）内置了一段学生"学号 → 姓名"的演示驱动代码，PythonTutor 片段中的驱动代码与其一致：

hashmap = HashMapChaining()

# 添加操作
hashmap.put(12836, "小哈")
hashmap.put(15937, "小啰")
hashmap.put(16750, "小算")
hashmap.put(13276, "小法")
hashmap.put(10583, "小鸭")

# 查询操作
name = hashmap.get(13276)          # 得到 "小法"

# 删除操作
hashmap.remove(12836)

按初始 capacity = 4 逐步推演（均可由源码确定性得出）：

1. 12836 % 4 = 0 → 桶 0：[小哈]
2. 15937 % 4 = 1 → 桶 1：[小啰]
3. 16750 % 4 = 2 → 桶 2：[小算]
4. 13276 % 4 = 0 → 与 12836 冲突，追加到桶 0 尾部：[小哈, 小法]，此时 size = 4
5. 第 5 次 put 前，load_factor = 4/4 = 1.0 > 2/3，先触发扩容（见下一节），容量变为 8；随后 10583 % 8 = 3 → 桶 3：[小鸭]

扩容后各键落位：12836 % 8 = 0、13276 % 8 = 4、15937 % 8 = 1、16750 % 8 = 2、10583 % 8 = 3——原本挤在桶 0 的一对键值对被打散到桶 0 和桶 4，直观体现了"扩容即冲突消解"。

四、extend()：负载因子驱动的再哈希扩容

def extend(self):
    """扩容哈希表"""
    # 暂存原哈希表
    buckets = self.buckets
    # 初始化扩容后的新哈希表
    self.capacity *= self.extend_ratio
    self.buckets = [[] for _ in range(self.capacity)]
    self.size = 0
    # 将键值对从原哈希表搬运至新哈希表
    for bucket in buckets:
        for pair in bucket:
            self.put(pair.key, pair.val)

（见 hash_map_chaining.py#L72-L83）

从源码结构看，扩容是一个典型的"再哈希（rehash）"过程，分四步：

1. 暂存旧桶数组：buckets = self.buckets，引用旧数组以便遍历；
2. 容量翻倍：capacity *= extend_ratio（即 ×2），并新建空桶数组；
3. 计数清零：self.size = 0；
4. 逐项搬运：遍历旧桶中每个 pair，通过 self.put(pair.key, pair.val) 重新按新的 capacity 取模落桶，同时把 size 重新累加回来。

这里有一个值得注意的实现细节：搬运过程复用了 put 方法。put 内部也会做扩容检查，但由于容量刚翻倍，搬运过程中 load_factor = size / 新capacity 始终低于 1/2，不会构成递归扩容的死循环。

文档 hash_collision.md 也强调了扩容的代价："类似于数组扩容，哈希表扩容需将所有键值对从原哈希表迁移至新哈希表，非常耗时；并且由于哈希表容量改变，需要通过哈希函数重新计算所有键值对的存储位置"。这也解释了为什么扩容被设计为仅在负载因子超过 2/3 的严重时才触发，而不是"一遇冲突就扩容"。

五、复杂度、局限与工程化优化

综合文档说明与源码实现，链式地址方案在本实现中的复杂度画像为：

• 查询：桶定位 O(1)，桶内遍历 O(链长)；平均链长约为负载因子，控制在阈值 2/3 以下时接近 O(1)；
• 添加：同上，另需摊还均摊 O(n) 的扩容搬运开销；
• 删除：O(链长)，且可原地删除、无删除标记问题；
• 空间：每个桶是一个列表对象，存在固定的对象头开销。

文档还给出了一条重要的工程优化路径：当链表很长时，可以将链表转换为"AVL 树"或"红黑黑树"，将查询操作的时间复杂度从 O(n) 优化至 O(log n)。各语言标准库的做法可作为佐证（来自 hash_collision.md 的"编程语言的选择"一节）：

• Java 采用链式地址，自 JDK 1.8 起，当 HashMap 数组长度达到 64 且链表长度达到 8 时，链表转换为红黑树以提升查找性能；
• Go 采用链式地址，每个桶最多存储 8 个键值对，超出则挂接溢出桶，溢出桶过多时执行等量扩容；
• Python 则采用开放寻址（dict 用伪随机数探测），与链式地址形成对照。

六、本地运行与可视化验证

仓库中的 Python 实现可直接运行验证。由于 hash_map_chaining.py 通过 sys.path.append 把 codes/python 目录加入导入路径后再 from chapter_hashing.array_hash_map import Pair，在仓库根目录下执行即可：

python codes/python/chapter_hashing/hash_map_chaining.py

按源码逻辑，预期输出依次为：5 次 put 后打印的 8 个桶（桶 0 为 ['12836 -> 小哈', '13276 -> 小法']，桶 1/2/3 各含一个键值对，其余为空）；get(13276) 返回 "小法"；remove(12836) 后桶 0 仅剩 13276 -> 小法。

如需逐指令观察内存结构（buckets、size、capacity 的实时变化），仓库的 codes/pythontutor/chapter_hashing/hash_map_chaining.md 内嵌了 Python Tutor 可视化链接（Python 3.11 模式），其中代码与 hash_map_chaining.py 一一对应、额外内联了 Pair 类定义，可配合本文的推演逐步对照每一步 put/extend 的落桶过程。

参考文件

• 链式地址哈希表 PythonTutor 可视化片段
• HashMapChaining 可运行实现
• Pair 类与简单哈希表 ArrayHashMap
• 开放寻址哈希表（对照实现，含 TOMBSTONE 懒删除）
• 哈希冲突文档
• 哈希表文档
• 链式地址哈希表示意图