Hello 算法·哈希冲突练习精讲链式寻址、扩容重哈希与开放寻址的墓碑删除【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇以《Hello 算法》hello-algo俄语版文档 哈希表章节练习 为主线围绕哈希碰撞之后如何查找扩容时元素去向开放寻址下删除元素为何会破坏查找如何判断两串字符能否互换得到四类高频考点展开深度解析。全文将习题题干与标准答案完整还原并逐一对照仓库中 链式地址哈希表 与 开放寻址哈希表 的真实实现。读完后你将掌握两种主流碰撞处理方案的核心机制、扩容必须逐个重哈希的底层原因、以及删除标记TOMBSTONE的经典工程实践可直接迁移到各类语言的标准库与自研哈希表设计中。一、先建立共同语言三个绕不开的概念在逐题精解前先用仓库源码把习题反复使用的三个概念锚定下来后面所有推导都建立在这些机制之上。1. 哈希函数与桶bucket。习题统一采用最简单的取模哈希 $h(x)x \bmod \text{capacity}$用余数把键映射到 0 至capacity-1的桶。仓库实现如出一辙例如 hash_map_chaining.c 中的hashFunc即return key % hashMap-capacity;。2. 负载因子load factor。键值对数量与桶数量的比值用于衡量哈希表的拥挤程度。仓库实现中链式与开放寻址两版均将初始容量设为4、负载因子阈值设为2.0 / 3.0、扩容倍率设为2见 hash_map_chaining.c。put时一旦loadFactor loadThres便触发extend扩容。3. 两种碰撞解决方案。当两个不同键算出同一个桶号时链式地址法chaining桶内挂一个链表碰撞元素全部追加进同一链表开放寻址法open addressing桶数组本身存放元素碰撞时按探测规则习题与源码均为线性探测逐个向右找空位越过尾部回到头部另寻空位。习题的题型设计与《Hello 算法》教程中 哈希冲突、哈希表 两章的讲解脉络一一对应下面四道题正好覆盖这两种方案的插入、查找、扩容与删除全流程。二、自测题一哈希碰撞之后如何完成查找题干哈希表有 5 个桶使用哈希函数 $h(x)x\bmod 5$。发生碰撞时元素被依次放入对应桶的链表链式地址中。现在按顺序插入[1, 6, 11, 7]请回答写出编号 0–4 的每个桶的内容查找数字 6 时先进入哪个桶按顺序会检查哪些元素基于第 1 问的桶内容判断后插入的元素是否覆盖了先插入的元素请结合本题的碰撞处理方式解释原因。逐问推导与答案先计算四个键的哈希值$1\bmod51$$6\bmod51$$11\bmod51$$7\bmod52$。可见 1、6、11 三个键发生碰撞全部落入桶 17 独立落入桶 2。因此各桶内容为0: [] 1: [1, 6, 11] 2: [7] 3: [] 4: []查找 6 时先由 $h(6)6\bmod51$ 定位到桶 1再沿着桶内链表从头到尾逐一比较键第一次比较元素 1不相等第二次比较元素 6命中。也就是说哈希值只负责指路到桶桶内的定位仍要逐元素做相等比较。关于是否覆盖答案是不会覆盖。哈希值相同只说明元素被分到同一桶并不代表元素本身相等。链式地址把发生碰撞的所有元素都保存在桶中查找时按顺序比较因此 1、6、11 三者作为不同键各自完整保留、互不覆盖。源码印证在仓库的链式实现中这一机制体现得非常直接——get先hashFunc定位桶然后while (cur)沿链表逐一比较cur-pair-key key命中才返回值否则返回空串hash_map_chaining.c而put只有在链表里找到相同 key时才更新val找不到相同 key 就新建节点插入hash_map_chaining.c。这正是同一桶内不同 key 互不覆盖的工程落地。一个可补充的细节是该实现把新节点头插到链表newNode-next hashMap-buckets[index]所以桶内物理顺序与按插入先后排列的题目叙述可能相反例如桶 1 实际遍历顺序是 11 → 6 → 1但这不影响任何结论——链内查找始终是线性逐个比较找到 6 都需要经历两次比较。三、自测题二扩容之后元素都搬去了哪里题干一张采用链式地址的哈希表原有 5 个桶哈希函数 $h(x)x\bmod5$键[1, 6, 11]都在桶 1 中。现把表扩容到 7 个桶哈希函数相应变为 $h(x)x\bmod7$。请回答分别计算 1、6、11 的新桶号扩容后哪些桶是非空的能否把旧桶 1 中的链表原封不动拷贝到新桶 1请结合第 1、2 问的结果说明理由。逐问推导与答案重新计算余数$1\bmod71$$6\bmod76$$11\bmod74$。扩容后桶 1 存 1桶 4 存 11桶 6 存 6——原本挤在同一桶中的三个键就此分道扬镳。因此非空桶为桶 1、4、6。第三个问题答案是不能整链拷贝。桶号是通过键对桶数取模算出来的容量从 5 换成 7 后同一键的桶号可能随之改变所以必须为每一个键重新计算位置。若把旧桶 1 的链表照搬进新桶 1后续按新公式 $h(x)x\bmod7$ 查找 6 时会去桶 6、查找 11 时会去桶 4而它们实际都躺在桶 1 里必然查找失败。源码印证仓库链式哈希表的扩容函数正是这一过程的教科书实现hash_map_chaining.cvoid extend(HashMapChaining *hashMap) { // 1. 暂存旧桶数组 int oldCapacity hashMap-capacity; Node **oldBuckets hashMap-buckets; // 2. 容量翻倍并分配新桶数组 hashMap-capacity * hashMap-extendRatio; hashMap-buckets (Node **)malloc(hashMap-capacity * sizeof(Node *)); ... hashMap-size 0; // 3. 遍历旧桶的每一个节点调用 put 重新计算桶号并搬入新表 for (int i 0; i oldCapacity; i) { Node *cur oldBuckets[i]; while (cur) { put(hashMap, cur-pair-key, cur-pair-val); ... } } free(oldBuckets); }核心在于第三步put内部必然重新执行hashFunc新容量下的取模因此扩容开销与键值对总数成正比这就是重哈希rehash的全部含义。开放寻址版本的做法完全一致hash_map_open_addressing.c只不过额外跳过了TOMBSTONE删除标记与空位。延伸扩容并非随时发生而是由负载因子阈值触发。在put入口处先检查loadFactor(hashMap) hashMap-loadThres才调用extendhash_map_chaining.c以此把单次扩容的代价均摊到多次插入上——这正是哈希表平均 $O(1)$性能的工程前提。四、自测题三删掉 6 之后还能找到 11 吗题干哈希表有 5 个槽位索引 0–4使用哈希函数 $h(x)x\bmod5$。发生碰撞时从哈希函数算出的索引开始向右寻找第一个空位线性探测越过索引 4 后回到索引 0 继续。依次插入[1, 6, 11]请回答三个数最终各自落在哪个索引查找 11 时按顺序会检查哪些索引假设删除 6 时直接把它的槽位清空就像从未被使用过一样而查找遇到空槽就停止。那么下一次查找 11 会发生什么结果正确吗如果不对应该如何避免逐问推导与答案插入过程模拟1 的哈希值是 $1\bmod51$索引 1 为空直接放入索引 16 的哈希值同样是 $6\bmod51$但索引 1 已被占向右探测到索引 2 为空放入索引 211 的哈希值同样是 $11\bmod51$从索引 1 出发索引 1、2 均被占继续探测到索引 3 为空放入索引 3。因此三个数的最终位置是1 → 索引 16 → 索引 211 → 索引 3。查找 11 时依次检查索引 1、2、3在索引 3 处命中。关键在第 3 问这也是开放寻址方案最具陷阱感的知识点。删除 6 后如果把索引 2 置为从未使用过的空位再查找 11从索引 1 出发1 ! 11继续探测索引 2——此时索引 2 是空位按照遇到空槽即停止的规则查找会在索引 2提前终止并错误地判定11 不存在尽管 11 就安静地躺在索引 3。根因是线性探测形成的探测链被挖断了——11 之所以能放在索引 3是因为它继承了索引 1、2 曾被占用这一探测历史空槽被解释为探测链到此为止而索引 2 的空洞制造了一条本不存在的链尾。正确的工程做法是删除时不要清空槽位而是放置一个删除标记墓碑TOMBSTONE。查找遇到删除标记时视其为曾被占用继续向右探测越过尾部回到索引 0直到命中目标或遇到真正的空槽才停止而后续插入时墓碑位置可以再次被新键使用。源码印证仓库开放寻址实现完整复刻了这套逻辑hash_map_open_addressing.c用哨兵对象TOMBSTONEkey 与 val 均为 -1表示删除标记hash_map_open_addressing.cfindBucket的循环条件是while (buckets[index] ! NULL)空槽NULL才会终止探测推进方式是index (index 1) % hashMap-capacity天然实现越过尾部回到头部的环形回绕hash_map_open_addressing.cremoveItem删除目标键后用hashMap-buckets[index] hashMap-TOMBSTONE覆盖槽位而不是置 NULLhash_map_open_addressing.c。值得一提的是该实现还在findBucket中做了一处锦上添花的优化若在探测途中遇到过墓碑、随后又找到了目标 key就把目标键值对前移到首个墓碑位置把原位置替换为墓碑hash_map_open_addressing.c。这样既复用了死槽位又压缩了后续键的探测距离属于值得借鉴的细节。对照题一可知两种方案的删除差异链式地址删除只需把节点从链表摘下hash_map_chaining.c不会影响同桶其他元素因此不需要墓碑而开放寻址天然需要删除标记来维系探测链。五、编程题两串字符能否通过重排互相得到题目给定两个仅由小写英文字母组成的字符串s与t。s中的字符可以任意重排但不能新增、删除或替换字符。请判断能否通过重排s得到t能则返回true否则返回false。要求使用哈希表统计每种字母出现次数不要对字符串排序。分析与思路重排后相等的实质是两串的字符多集完全相同即每个字母的出现次数一致——这正是经典的异位词anagram判定问题。题目禁止排序、要求哈希计数是希望练习哈希表做频次统计的通用范式。文档给出的三条提示本身已构成完整解题链长度预判若两串长度不同字符构成不可能相同直接返回false正向计数遍历s在哈希表中把每个字母的计数加 1反向抵消遍历t把每个字母的计数减 1遍历结束后仅当哈希表中所有计数都为 0两串的字符构成才完全相同返回true。用哈希表而非排序的收益是明显的不需要生成全排列那是指数级也避开了排序的 $O(n\log n)$一趟加号、一趟减号、一趟校验整体时间复杂度 $O(\lvert s\rvert\lvert t\rvert)$空间开销与字母表规模有关。参考实现def is_anagram(s: str, t: str) - bool: if len(s) ! len(t): return False # 1. 哈希表记录 s 中各字符出现次数 counter {} for c in s: counter[c] counter.get(c, 0) 1 # 2. 遍历 t逐字符抵消计数 for c in t: if c not in counter: return False counter[c] - 1 if counter[c] 0: # 说明 t 中某字符比 s 更多提前退出 return False # 3. 所有计数归零即构成相同 return True实现细节上有两个值得留意的工程点越界即失败在抵消阶段若某字符计数减成负数说明t中该字符多于s可直接短路返回false无需等待最终全量校验本实现还顺带处理了s中不存在的字符固定字符集的可替代方案既然题目限定小写字母也可用长度为 26 的整型数组替代哈希表counter[ord(c) - ord(a)]自增/自减。数组在键空间确定、连续时往往更快而通用哈希表在键类型任意、稀疏时更灵活——两种思路对应同一频次统计模型的两种落地形态。由于题目要求不得排序务必规避将s、t各自排序后比较字符串的写法——那种做法虽然在语义上同样正确但时间复杂度为 $O(n\log n)$ 且绕开了本次练习的核心考点。六、把练习变成本地实验跑通仓库源码纸上推导之后最有效的巩固方式是直接运行仓库中与三道自测题对应的两份 C 实现观察插入、查找、删除时的真实桶布局。在 codes/c/chapter_hashing 目录下分别编译执行# 链式地址哈希表对应题一、题二 gcc hash_map_chaining.c -o hash_map_chaining ./hash_map_chaining # 开放寻址哈希表对应题三注意其使用 ../utils/common.h gcc hash_map_open_addressing.c -I../utils -o hash_map_open_addressing ./hash_map_open_addressing两份程序的main驱动都覆盖了添加 → 查询 → 删除 → 打印的完整生命周期hash_map_chaining.c、hash_map_open_addressing.c打印输出会直接展示每个桶/槽位的内容删除后的槽位会显示TOMBSTONE。若想观察扩容效果可以临时多插入几个键让负载因子突破2.0/3.0阈值对比扩容前后桶数组的打印结果即可直观复现题二描述的元素各奔东西过程。七、小结把四道练习收敛到一张认知地图上考点关键结论对应源码链式地址查找哈希只定位桶桶内线性比较碰撞键互不覆盖hash_map_chaining.c扩容重哈希桶号由键对容量取模决定容量改变后必须逐键重算hash_map_chaining.c开放寻址删除直接清空会切断探测链须用删除标记维持可查找性hash_map_open_addressing.c字符构成比较双趟加减计数、归零判定即为哈希频次统计范式本文参考实现哈希表的工程实现细节繁多本篇涉及的主题在教程正文中有更系统的展开碰撞处理策略的横向对比可读 docs/chapter_hashing/hash_collision.md哈希函数的选取与设计原则见 docs/chapter_hashing/hash_algorithm.md而本文聚焦的哈希冲突相关练习原文位于 ru/docs/chapter_hashing/exercises.md同章节英文版练习见 en/docs/chapter_hashing/exercises.md。建议将本文与上述文档、源码配套研读形成理论 → 习题 → 实现 → 实验的完整闭环。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
