Hello 算法 哈希表章节练习详解：链式地址查找、扩容重哈希、开放寻址删除与字符计数编程实战

本篇基于《Hello 算法》哈希表章节的练习文档 exercises.md，完整收录并深入解析该章全部练习：三道链式地址、哈希表扩容、开放寻址删除的知识巩固题，以及一道“比较两个字符串字符组成”的编程题。读完本文，你能亲手推演哈希冲突后的查找与删除机制、理解扩容时元素必须重哈希的原因，并掌握用哈希表做字符计数的标准写法，同时借助仓库中 链式地址哈希表 与 开放寻址哈希表 的 Python 源码，把每道练习背后的实现原理落到实处。

练习一：链式地址哈希表中，发生哈希冲突后怎样查找

题目设置

一个哈希表有 5 个桶，哈希函数为 h(x) = x mod 5，冲突时把元素依次放进该桶的列表中。依次插入 [1, 6, 11, 7]，请回答：

1. 写出 0～4 号桶中的内容；
2. 查找 6 时会先进入哪个桶，并依次检查哪些元素？
3. 根据第 1 问写出的桶内容，后插入的元素是否覆盖了先插入的元素？结合这种冲突处理方式说明理由。

参考答案与逐步推演

第 1 问：因为 1 mod 5 = 6 mod 5 = 11 mod 5 = 1，而 7 mod 5 = 2，各桶内容为：

0: []
1: [1, 6, 11]
2: [7]
3: []
4: []

第 2 问：查找 6 时先进入 1 号桶，再依次比较 1、6，第二次比较时找到目标。

第 3 问：哈希值相同只表示它们落入同一个桶，并不表示这些元素相等。链式地址把冲突元素都保存在桶内，查询时再逐个比较，因此 1、6、11 不会互相覆盖。

源码印证：HashMapChaining 的查询与插入

这道练习的机制在仓库源码 hash_map_chaining.py 中有完整实现。关键代码与练习一一对应：

def hash_func(self, key: int) -> int:
    """哈希函数"""
    return key % self.capacity        # 对应练习中的 h(x) = x mod capacity

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

• 初始化时 capacity = 4，buckets 是一个“桶数组”，每个桶是一个列表（见 构造方法）。这正是练习中“把元素依次放进该桶的列表”的做法——用列表代替链表以简化代码；
• get 方法的“先算桶号、再遍历桶内元素逐个比较”的过程，与练习第 2 问的推演步骤完全一致；
• put 方法（L44-L59）在桶内未找到 key 时执行 bucket.append(pair)，把新键值对追加到桶尾部，这就是“后插入的元素不覆盖先插入元素”的代码体现。

文档在 hash_collision.md 中还指出链式地址的两点局限：链表包含节点指针、比数组更耗费内存；查询需线性遍历链表。当链表很长时，可将其转换为 AVL 树或红黑树，把查询复杂度从 O(n) 优化至 O(log n)。

练习二：哈希表扩容后元素去哪儿

题目设置

一个使用链式地址的哈希表原有 5 个桶，哈希函数为 h(x) = x mod 5，键 [1, 6, 11] 都在 1 号桶中。现在把哈希表扩容为 7 个桶，哈希函数相应变为 h(x) = x mod 7，请回答：

1. 分别计算 1、6、11 的新桶号；
2. 扩容后哪些桶中有元素？
3. 扩容时能否把原来 1 号桶中的列表原样复制到新的 1 号桶？结合第 1、2 问的结果说明理由。

参考答案与逐步推演

第 1 问：新桶号分别为：

• 1 mod 7 = 1；
• 6 mod 7 = 6；
• 11 mod 7 = 4。

第 2 问：1 号桶保存 1，4 号桶保存 11，6 号桶保存 6。三个键不再挤在同一个桶中。

第 3 问：不能原样复制。桶号由“键对桶数取余”得到，桶数从 5 变成 7 后，同一个键的新桶号可能改变，因此必须重新计算每个键的位置。若把旧的 1 号桶原样复制过去，之后按新公式查找 6 和 11 时，会分别前往 6 号桶和 4 号桶，从而找不到它们。

源码印证：extend 方法为何逐个 put 回去

HashMapChaining.extend 的实现正是“重新哈希”的标准写法：

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

注意搬运时调用的是 put 而不是直接赋值：put 内部会先执行 hash_func 用新的 capacity 重新计算桶号，再决定放入哪个桶。这与练习第 3 问的结论一致——扩容必须对每个键重新取模，不能按旧桶号整体迁移。

另外两个实现细节值得注意：

• 触发扩容的时机是负载因子超过阈值 load_thres = 2/3，扩容倍数为 extend_ratio = 2（构造函数 与 put 方法 开头）；
• hash_map.md 中说明，负载因子（元素数量除以桶数量）衡量冲突严重程度并常作为扩容触发条件，例如 Java 的 HashMap 在负载因子超过 0.75 时扩容至 2 倍。不同实现的阈值与倍数不同，但“容量变化 ⇒ 全员重哈希”这一原则是通用的。

练习三：开放寻址中删除 6 后还能找到 11 吗

题目设置

一个哈希表有 5 个位置，索引为 0～4，哈希函数为 h(x) = x mod 5。发生冲突时，从哈希函数算出的索引开始，向右寻找第一个空位（即线性探测）。依次插入 [1, 6, 11]，请回答：

1. 三个数最终分别放在哪个索引？
2. 查找 11 时，会依次检查哪些索引？
3. 如果删除 6 时直接把它的位置改成“从未使用的空位”，而查找遇到空位就停止，再查找 11 时会发生什么？这个查找结果是否正确？如果有问题，应怎样避免？

参考答案与逐步推演

第 1 问：1 放在索引 1。6 也映射到索引 1，发生冲突后放在索引 2。11 同样从索引 1 开始，依次跳过已占用的索引 1、2，最终放在索引 3。

第 2 问：查找 11 时依次检查索引 1、2、3，在索引 3 找到它。

第 3 问：如果把索引 2 改成表示“从未使用”的空位，查找 11 时检查索引 1 后就会在索引 2 停止，从而错误地认为 11 不存在。删除时应留下“已删除”标记：查找遇到该标记时继续检查下一个索引（越过索引 4 后回到索引 0），而以后的插入仍可重新使用这个位置。

源码印证：TOMBSTONE 与 first_tombstone 优化

仓库中的 hash_map_open_addressing.py 完整实现了练习第 3 问给出的“正确解法”，核心是懒删除（lazy deletion）机制：

self.buckets: list[Pair | None] = [None] * self.capacity  # 桶数组
self.TOMBSTONE = Pair(-1, "-1")  # 删除标记

remove 方法并不真正移除元素，而是把该桶替换为删除标记（L81-L88）：

def remove(self, key: int):
    """删除操作"""
    index = self.find_bucket(key)
    # 若找到键值对，则用删除标记覆盖它
    if self.buckets[index] not in [None, self.TOMBSTONE]:
        self.buckets[index] = self.TOMBSTONE
        self.size -= 1

find_bucket（L34-L54）则体现了练习答案中的两条规则：

def find_bucket(self, key: int) -> int:
    """搜索 key 对应的桶索引"""
    index = self.hash_func(key)
    first_tombstone = -1
    # 线性探测，当遇到空桶时跳出
    while self.buckets[index] is not None:
        if self.buckets[index].key == key:
            # 若之前遇到了删除标记，则将键值对移动至该索引处
            if first_tombstone != -1:
                self.buckets[first_tombstone] = self.buckets[index]
                self.buckets[index] = self.TOMBSTONE
                return first_tombstone  # 返回移动后的桶索引
            return index  # 返回桶索引
        # 记录遇到的首个删除标记
        if first_tombstone == -1 and self.buckets[index] is self.TOMBSTONE:
            first_tombstone = index
        # 计算桶索引，越过尾部则返回头部
        index = (index + 1) % self.capacity
    # 若 key 不存在，则返回添加点的索引
    return index if first_tombstone == -1 else first_tombstone

• None 与 TOMBSTONE 语义不同：循环条件 while self.buckets[index] is not None 表明只有遇到“从未使用的空位”（None）才停止探测，遇到 TOMBSTONE 会继续向后找——这正是练习答案中“查找遇到该标记时继续检查下一个索引”的实现；
• 环形数组：index = (index + 1) % self.capacity 实现了“越过索引 4 后回到索引 0”的环形探测；
• first_tombstone 优化：hash_collision.md 指出，懒删除会不断积累删除标记、拖慢探测，因此该实现额外记录遇到的首个 TOMBSTONE 索引，找到目标元素后把它与该标记交换位置，使元素逐步移动到距离理想位置更近的桶中。这一“越过空桶即停、越过标记不停”的行为差异，正是练习三想考察的核心知识点。

编程练习：比较两个字符串的字符组成（判断字母异位词）

题目描述

给定两个只含小写英文字母的字符串 s 和 t。可以任意调整 s 中字符的位置，但不能添加、删除或替换字符。请判断调整后能否得到 t；可以则返回 true，否则返回 false。要求使用哈希表记录各字母的出现次数，不对字符串中的字符排序。

这道题即经典面试题“有效的字母异位词”（LeetCode 242）。

解题提示（原文档收录）

1. 两个字符串长度不同，它们的字符组成一定不同；
2. 用哈希表记录每种字母的数量；扫描 s 时把对应计数加 1；
3. 扫描 t 时把对应计数减 1；所有计数最终都为 0，字符组成才相同。

参考实现

按提示实现如下：

def valid_anagram(s: str, t: str) -> bool:
    """判断 t 是否是 s 的字母异位词（基于哈希表计数，不排序）"""
    # 提示 1：长度不同，字符组成一定不同
    if len(s) != len(t):
        return False
    # 提示 2：哈希表记录每种字母的数量，扫描 s 时对应计数加 1
    count: dict[str, int] = {}
    for c in s:
        count[c] = count.get(c, 0) + 1
    # 提示 3：扫描 t 时对应计数减 1
    for c in t:
        count[c] = count.get(c, 0) - 1
        # 若某字母在 t 中出现次数超过 s，字符组成必然不同，提前结束
        if count[c] < 0:
            return False
    return True

由于长度已相等，且扫描 t 时一旦某个字母的计数跌破 0 就说明 t 中该字母偏多，因此最终所有计数必然回到 0，可直接返回 True。

复杂度分析：时间复杂度 O(n)，只需两次线性扫描，远优于先排序再比较的 O(n log n) 做法（n 为字符串长度）；空间复杂度 O(1)，因为小写英文字母最多 26 种，哈希表大小是常数。

边界情况：空串对空串返回 True；两串长度相同但字符不同（如 "ab" 与 "ba" 的计数法结果为 True，而 "ab" 与 "aa" 会在第二个 a 处因计数变负而返回 False）。

相关源码与延伸阅读

本练习围绕的哈希表冲突处理机制，在仓库中对应的实现与文档路径如下：

主题	文件路径	说明
链式地址哈希表	hash_map_chaining.py	练习一、练习二的原型实现，含扩容逻辑
开放寻址哈希表	hash_map_open_addressing.py	练习三的原型实现，含 TOMBSTONE 懒删除
简单哈希表	array_hash_map.py	定义键值对 Pair 类，被上述两个实现引用
哈希冲突原理	hash_collision.md	链式地址、线性/平方探测、多次哈希与懒删除详解
哈希表基础	hash_map.md	哈希函数、扩容与负载因子
哈希算法设计	hash_algorithm.md	哈希算法目标、质数取模与简单哈希算法

以上源码文件均自带 __main__ 驱动程序，可直接运行 python codes/python/chapter_hashing/hash_map_chaining.py 或 python codes/python/chapter_hashing/hash_map_open_addressing.py 观察添加、查询、删除后哈希表的完整状态，配合本文三道练习的手推过程，即可形成“手算推演—源码验证—独立编程”的完整练习闭环。