Hello 算法链式地址哈希表源码精读：从 Python 实现到多语言扩容机制

本篇以《Hello 算法》开源仓库中用于 Python Tutor 逐行可视化的教学文件 ja/codes/pythontutor/chapter_hashing/hash_map_chaining.md 为骨架，逐行拆解一个"链式地址（separate chaining）哈希表"的完整 Python 实现。读者将掌握哈希冲突的成因、用链表化解冲突的增删查改流程、基于负载因子的自动扩容触发时机，并通过仓库中 C / Java / Go 等多语言同构实现，理解同一算法在不同语言里的落地差异。

为什么需要链式地址：哈希冲突的必然性

教材章节 docs/chapter_hashing/hash_collision.md 明确指出：哈希函数的输入空间通常远大于输出空间，因此哈希冲突在理论上不可避免。以本实现为例，输入键是任意整数，而输出空间只是容量 capacity 个桶，必然存在多个整数被映射到同一个桶索引的情况。

处理冲突主要有两类思路：

1. 改良哈希表数据结构，使冲突发生时哈希表仍能正常工作——这正是链式地址与开放寻址的出发点；
2. 仅在必要时（冲突较严重时）执行扩容——引入负载因子阈值来控制扩容时机。

本篇文章聚焦第一种思路中的"链式地址"，对应仓库中日英等多语言教材的 哈希冲突章节 均以该实现为教学范例。

链式地址的设计原理与代价

链式地址的核心思想非常直观：把原本"一个桶只能放一个键值对"的数组，改造成"每个桶挂一条链表（教学实现中用动态数组代替）"，让所有哈希到同一桶的键值对都串在这条链上。下图展示了链式地址哈希表的典型形态：

基于此结构，增删查改的语义变为：

• 查询：对 key 求哈希得到桶索引 → 访问该桶的链表头 → 线性遍历链表、逐个比较 key；
• 添加：哈希定位桶 → 将新键值对追加到链表尾部（C 版本采用头插法）；
• 删除：哈希定位桶 → 遍历链表找到目标节点后摘除。

代价同样明显：链表节点携带指针，比纯数组更耗内存；而查找需线性遍历，最坏复杂度退化为 O(n)。因此教材提示：当链很长时，可把链表替换为 AVL 树或红黑树，把查询优化到 O(log n)——这正是 Java 的 HashMap 在生产环境中的真实做法。

逐模块精读 Python 实现

教学文件完整对应的可运行源码位于 codes/python/chapter_hashing/hash_map_chaining.py。其中 Pair 类复用自同目录下的 array_hash_map.py（定义见该文件第 8-13 行），实现了"键值对"这一基础载体。下面给出结构逐段剖析。

构造函数与四个关键参数

class HashMapChaining:
    """链式地址哈希表"""

    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)]  # 桶数组

四个实例变量承载了哈希表最重要的运行参数（源码 hash_map_chaining.py）：

参数	初始值	含义
size	0	当前键值对总数
capacity	4	桶的数量（数组长度）
load_thres	2.0 / 3.0	扩容触发阈值，约 0.667
extend_ratio	2	扩容倍数，即容量翻倍

buckets 是一个列表的列表：外层列表充当桶数组，内层每个列表充当一条"链"，从而把代码简化到无需手写链表节点。

哈希函数与负载因子

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

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

hash_func 采用最简单的取模映射（源码第 25-27 行），教学上便于用四则运算推算每个键落入哪个桶。load_factor 度量哈希表的"拥挤程度"，是判断是否扩容的唯一依据。

查询操作 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

流程：先由哈希函数定位桶，再在桶的链表中线性扫描（源码第 33-42 行）。找到即返回值，链扫完仍无匹配则返回 None。注意冲突不会让数据丢失——同一桶内的多个键值对都被保留，查询只是多走几步。

添加操作 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 承担"添加 + 更新"双重职责（源码第 44-59 行）：写之前先查负载因子，一旦 size / capacity > 2/3 便触发 extend()；随后哈希定位桶，若链中已存在相同 key 则直接覆盖 val 并返回，否则把新 Pair 追加到链尾并把 size 加一。这种"先判满载再写入"的顺序保证每次写入后负载因子不超过阈值与单次插入之和。

删除操作 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

删除同样先定位桶再线性扫描（源码第 61-70 行），命中后调用 Python 列表的 remove 移除该 Pair，size 减一后立刻 break。链式地址下删除是"物理删除"，与开放寻址"不可直接删、需懒删除墓碑标记"的困境形成鲜明对比。

扩容操作 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)

扩容分四步（源码第 72-83 行）：暂存旧桶数组 → 容量乘 extend_ratio 并新建空桶数组 → size 清零 → 遍历所有旧链、把每个键值对重新 put 进新表。关键点是 put 内部的"负载因子检查 + 取模哈希"都基于新容量执行，因此每个键的桶索引随 capacity 变化而重新分布，这正是"数据搬运"代价的来源，也解释了为何哈希表扩容昂贵。

打印操作 print

def print(self):
    """打印哈希表"""
    for bucket in self.buckets:
        res = []
        for pair in bucket:
            res.append(str(pair.key) + " -> " + pair.val)
        print(res)

逐个桶输出为 ["key -> val", ...] 形式的列表（源码第 85-91 行），方便直观观察每个桶的链长与数据分布，是验证冲突与扩容效果最直接的调试手段。

Driver 实测：算清冲突与扩容发生的精确时刻

__main__ 演示块（源码第 94-118 行）插入五名学生的学号-姓名映射，与中文版教材中的示例数据完全一致：

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：12836 % 4 = 0，落入桶 0，size = 1；
2. 插入 15937：15937 % 4 = 1，落入桶 1，size = 2，负载因子 0.5 < 0.667；
3. 插入 16750：16750 % 4 = 2，落入桶 2，size = 3，负载因子 0.75 > 0.667；
4. 插入 13276：方法开头检测到负载因子超限，首次触发扩容，capacity 变为 8，旧表四个键全部重哈希，随后 13276 % 8 = 4 落入桶 4，size = 4；
5. 插入 10583：10583 % 8 = 7，落入桶 7，size = 5。

值得注意的细节是：12836 与 13276 相差 440，而 440 是 8 的倍数，因此即使扩容到 8，二者仍被映射到同一个桶 4——直观展示了"换更大的表并不能消灭特定的冲突对，只能摊薄冲突密度"。而 get(13276) 正是在这条同桶链中跳过 12836 后命中"小法"；随后 remove(12836) 又只删掉桶 4 中对应节点，不影响其余数据。

本地验证命令为：

python codes/python/chapter_hashing/hash_map_chaining.py

预期输出依次打印"添加完成后哈希表"（每个桶一行列表）、"输入学号 13276，查询到姓名 小法"以及"删除 12836 后哈希表"。此外，ja/codes/pythontutor/chapter_hashing/hash_map_chaining.md 本身即编码后的 Python Tutor 单步执行入口，可配合动画直观观察每次 put、extend 时数据如何在桶间流动。

教科书简化版与真实链表版：以 C 实现为对照

Python 教学版用"列表套列表"省去了指针操作，而 codes/c/chapter_hashing/hash_map_chaining.c 给出了更贴近工业实现的"真链表"版本，二者接口一一对应：

• 数据结构：C 版以 Node（见该文件第 21-24 行）串起 Pair，buckets 是指向 Node * 的指针数组；删除时用 pre / cur 双指针摘链（第 147-168 行），需要手工 malloc / free 管理内存并配套析构函数 delHashMapChaining；
• 插入位置：Python 版 append 到链尾，C 版头插到链表头部（第 135-142 行），二者只是链序不同，不影响正确性；
• 同名常量：capacity = 4、loadThres = 2.0 / 3.0、extendRatio = 2 完全一致，演示数据同样为五个学号。

除 Python、C 外，该算法在仓库 14 种语言中均有同构实现，例如 Java 版、Go 版、C++ 版 与 TypeScript 版，接口统一为 hash_func / load_factor / get / put / remove / extend，便于对照学习各语言容器与内存模型的差异。

从教学走向工业：各语言的真实选型

教材 docs/chapter_hashing/hash_collision.md 末尾总结了主流语言的真实策略，可帮读者理解本实现所处的位置：

• Python：dict 采用开放寻址，用伪随机数探测，而非链式地址；
• Java：HashMap 采用链式地址，自 JDK 1.8 起，当内部数组长度达到 64 且链表长度达到 8 时，链表自动转为红黑树，把查询从 O(n) 优化到 O(log n)；
• Go：采用链式地址的变体，每个桶最多容纳 8 个键值对，超出则串联溢出桶，溢出桶过多时执行特殊的等量扩容以保证性能。

也就是说，本篇文章精读的链式地址实现，正是 Java、Go 等生产级哈希表的共同底层逻辑，区别仅在于"链的载体、树的升级阈值与扩容策略"。

下一步学习路线

掌握链式地址后，建议对比阅读同为冲突化解方案的开放寻址实现 hash_map_open_addressing.py，重点体会其"不可直接删除、需要 TOMBSTONE 懒删除、线性探测易聚集"等与链式地址截然相反的性质；随后可完成 docs/chapter_hashing/exercises.md 的练习，并通过 docs/chapter_hashing/summary.md 回顾本节的负载因子、扩容倍数、哈希函数设计等核心概念，形成对哈希表全貌的闭环理解。