散列：排解冲突
看完你能用生日悖论解释冲突为何必然，并用装载因子预判其频率
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
散列：排解冲突
看完你能用生日悖论解释冲突为何必然，并用装载因子预判其频率
什么是散列冲突
假设班里 30 个同学，但只有 10 个储物柜。班主任按学号尾数分配——两个尾数相同的同学，必然被指到同一个柜子。谁也挤不进去，这就叫冲突。
学号尾数 = 哈希函数；尾数相同的两人都被指到同一格，即冲突
一山二虎：冲突场景
26 把钥匙要挂到 10 个挂钩上——挂得下吗？必然挂不下。key 永远比槽位多，冲突不是程序员的失误，是数学的必然。
两虎=两个不同的 key，一山=同一个槽位，都想独占那一个位置
冲突解决的总体策略
中心向外辐射：先看两大阵营，再看各自内部的具体实现手法。
泾渭分明：开放定址 vs 链地址
上页说冲突有两条路可走。这页走进这两条路，看它们如何一个在原地腾挪、另一个向外延伸。
你座位被占了，就挨个往后挪一位找最近的空位坐下
两种策略的优劣对比
两种策略都能解决冲突，但'哪个更好'没有标准答案——取决于负载因子和操作类型。
- 空间：元素全存数组内，无额外指针开销
- 时间：缓存友好，负载因子高时急剧退化
- 删除：必须用墓碑标记，不能直接置空
- 空间：每桶挂链表/树，节点需额外指针
- 时间：负载可>1，平均O(1)，最坏O(n)
- 删除：直接摘除节点，无需特殊标记
开放定址的基本思想
上页做完对比，开放定址和链地址走了完全不同的路。这页专门拆开开放定址——它的招数一句话就能说清：冲突发生后不另起炉灶，就在这张表里按规则继续找空位。
指定座位被占就往后挪一格，挨个试直到找到空座
开放定址的插入流程
沿箭头从左侧开始：先定位起始槽，再检查空位、重复键和容量，最终走向处理成功或插入失败。
线性试探的规则
上一页说开放定址要找新位置。怎么找？最朴素的办法：从原位开始，一位一位往后挪。这就是线性试探。
指定车位被占就挨个往后挪，直到找到空位
线性试探插入实例
表长 7，连续插入 hash 值都是 1 的四个键，看线性试探如何逐个占位。
线性试探查找实例
以 h(K)=3、3号和4号槽非空为例，查找一直查到5号空槽。
一次聚集与二次聚集
线性试探看起来简洁优雅，但它藏着一个致命缺陷：被占用的格子会像滚雪球一样连成一片，越滚越长。新来的元素只要哈希落在长链覆盖的区域，无论原本想去哪里，都得沿着这条链一步步试探。
队伍越长，新乘客不管从哪个口来，都得并进这条长队里挪
为什么不能真删除
想想线性试探的链式布局：元素 A 因冲突挪到位置 3，元素 B 又被迫挪到位置 5。若此时「真删除」A，会发生什么？
撤走中间任一位，后面的路就断了
懒惰删除的工作原理
从左到右看：删除先把目标槽改成墓碑，再分出查找继续探测与插入复用两条支路。
墓碑带来的问题
上一页我们用'墓碑'巧妙解决不能真删的问题，看起来很完美。但跑得越久，墓碑越来越多——数据结构也会'老去'。
房间空了但牌子占位，新客住不进——空槽有墓碑就落不进新元素
墓碑的解决思路
上页说到墓碑越积越多，探测链越来越长，查找效率会断崖式下跌。那该怎么办？两个思路：一是让墓碑槽也能「再就业」，二是攒多了就一次性重建。
纸条＝墓碑：可上新书于纸条位，但找旧书不能跳过；纸条太多就重整书架
知识点回顾
- ✓冲突由鸽巢原理注定，不可避免
- ✓开放定址与链地址是空间与聚集的权衡
- ✓试探序列质量决定开放定址的性能
- ✓墓碑是删除的补丁，会污染查找路径
自测题
在使用线性试探的开放定址法中，为什么不能直接把已删除键所在的槽设为"空"？
课后思考
先合上答案,自己动笔算一算;实在想不出再点开参考答案看思路。
参考答案插入遇到"空"槽就停。若中间被直接置空,查找会在那里提前终止,误以为目标不存在——查找路径被"切断"了。
参考答案提示公式 0.5×(1+1/(1-α)²),代入 α=0.7 数量级在 5~6;成功查找约一半。这就是工业上把装载因子压到 0.5 以下的原因。
参考答案不能。二次试探只缓解一次聚集,同一起点的多个键仍会撞车(二次聚集);且高 α 下空槽稀疏,探测序列越来越长,雪崩依旧。