(d2)散列：排解冲突(2)

官官方信息技术老师·11 页·深入（追求细节与边界）·0 次浏览·3 天前
✦ (d2)散列：排解冲突(2)信息技术(d2)散列：排解冲突(2)4k + 3

(d2)散列：排解冲突(2)

第九章 词典 · 知识图解

按 空格/→ 演示下一步

1 / 11 页

全部页面点击任意一页，跳回舞台从这页播放

(d2)散列：排解冲突(2)

第九章 词典 · 知识图解

(d2)散列：排解冲突(2)
第九章 词典 · 知识图解
1第 1 页 · (d2)散列：排解冲突(2)

平方试探

上一节用线性试探处理冲突,但每次只挪 1 格——连续占用的长块会越滚越大,叫『一次聚集』。本节看一种用平方步长把块切散的策略,以及它带来的新代价。

核心做法
冲突后跳 i² 个槽位,i=1,2,3 时依次尝试 h+1、h+4、h+9…
公式表达
第 i 次试探位置 = (h(k) + i²) mod m,m 是表长
缓解一次聚集
跳跃距离递增,长块附近不再被一格一格挤满
二次聚集
散列值相同的不同键必沿同一条探测序列走,共享同一路径
表长约束
m 宜取质数且 m≡3(mod4),保证覆盖至少一半槽位
停车场找车位对应 →平方试探的步长

第 1 次挪 1 个,第 2 次挪 4 个,第 3 次挪 9 个——距离平方增长绕开堵塞带

hi(k)=(h(k)+i2) mod  mh_i(k)=\bigl(h(k)+i^{2}\bigr)\bmod\,m
2第 2 页 · 平方试探

一利一弊

平方试探跳着找位置（1、4、9…）避开了线性试探的扎堆毛病。但这跳跃本身也带来新麻烦——这就是它的一利一弊。

利：避免一级聚集
步长 1、4、9… 跳跃递增，冲突元素被甩到远处不再扎堆
弊：仍存二级聚集
同义词走完全相同的探测序列，仍会彼此撞车
弊：不一定探到空位
跳跃幅度有限，可能跨过仍有空位的槽而插入失败
登车跳号选座对应 →平方试探的探测序列

跳过邻位避开扎堆，但跳太远可能漏掉空座

3第 3 页 · 一利一弊

至多半载

上一页说到平方试探有「找不到空位」的隐患——其实只要控制好一个数字，这个隐患就能彻底避免。它就是装载因子 α。

装载因子 α
已存元素数 n 与槽位数 m 之比，α=n/m，衡量表的「拥挤程度」
α < 1/2 必成功
试探序列至少扫过 ⌈m/2⌉ 个不同槽位，必能撞上空位
α = 1/2 临界
恰好一半满，插入可能成功也可能失败，不再有保证
α > 1/2 有风险
表未满也可能插不进，应扩容或改用链表法
电影院只卖一半票对应 →至多半载保证

卖出去的票不超座位一半，任何持票人都能找到位——总有空位

α=nm≤12⇒平方试探插入必成功\alpha = \frac{n}{m} \leq \frac{1}{2} \Rightarrow \text{平方试探插入必成功}
4第 4 页 · 至多半载

M + Lemda

平方试探虽然避开了「扎堆」，却把装填因子死死压在 0.5 以下，探测序列才兜得回来。要打破这层天花板，得换一个每条记录自带步长的规则——这就是 M + λ。

探测公式
H_i(key) = (H_1(key) + i · H_2(key)) mod M，两次散列相加取模
λ 的含义
λ = H_2(key) 是随关键字变化的「步长」，每条记录走自己的节奏
互素硬约束
gcd(H_2(key), M) = 1 必须成立，否则探测序列兜不全 M 个槽位
选 M 的诀窍
把 M 设为质数，且 H_2 返回 1..M-1，几乎自动满足互素
电影院找座位对应 →双散列探测

第一次按票号定位排数，找不到就每次往后挪 λ 排，而不是只挪一排

Hi(key)=(H1(key)+i⋅H2(key)) mod MH_i(\text{key}) = \bigl(H_1(\text{key}) + i \cdot H_2(\text{key})\bigr) \bmod M
5第 5 页 · M + Lemda

双蜓点水

前面我们看到 λ 不能太高——因为大家都挤着挪动会形成聚集。有没有办法让每个 key「跳的步子」本来就不同？双散列就是答案。

第二个哈希函数 h₂
专门决定探测时每一步跨多远，且不能让它的值为 0
探测序列公式
第 i 次落到 h₁(k) + i·h₂(k) mod M
步长与 M 互质
h₂(k) 与 M 互质，才能保证走遍整张表不漏格
分布更均匀
不同 key 步长不同，大大缓解聚集现象
跳房子的小孩对应 →双散列的探测序列

每个孩子按自己编号跳不同格数，比大家都只挪一格更不容易扎堆

h(k,i)=(h1(k)+i⋅h2(k)) mod Mh(k, i) = \big(h_1(k) + i \cdot h_2(k)\big) \bmod M
6第 6 页 · 双蜓点水

4k + 3

上一页说平方试探「至多半载」——只能探测到一半的槽位。但有个巧办法：只要表长取成 4k+3 的素数，再把试探方向从单向改成 ±i²，就能走遍全表。

表长取 4k+3 素数
M 必须是 4k+3 形式的素数，如 3、7、11、19、23、31…
双向试探 ±i²
第 i 步同时探测 +i² 和 -i² 两个偏移，覆盖更多位置
遍历全部槽位
两个方向合起来，M 个槽位全都不漏，没有探测盲区
单行道停车场对应 →环形双向停车场

原来只往一个方向开（+i²），改造成环后顺逆都能走，所有车位都到得了

h(k,i)=(h(k)±i2) mod M,  M 为 4k+3 型素数h(k,i)=(h(k)\pm i^2)\bmod M,\;M\text{ 为 }4k+3\text{ 型素数}
7第 7 页 · 4k + 3

双平方定理

上一页我们说，只要表长 M 是 4k+3 形式的素数，平方探测就能覆盖至少一半的槽位——但这是经验直觉还是可证明的事实？这一页把它写成定理。

定理陈述
若 M 是 4k+3 型素数，则 i=0,1,…,⌈M/2⌉−1 对应的 i² mod M 两两不同
两个条件都必要
「素数」排除小因子干扰；「4k+3」保证 −1 不是模 M 的二次剩余
探测通式
第 i 次落在 (h(k) + i²) mod M 上，前 ⌈M/2⌉ 步偏移两两不同
直接推论
负载因子 α ≤ 0.5 时，平方探测必能在 ⌈M/2⌉ 步内命中空槽
图书馆按 1、4、9… 步跳着找空位对应 →平方探测的探查序列

跳距由完全平方数决定；书架总数是 4k+3 型素数时，跳一半也碰不到重复格

h(k,i)=(h(k)+i2) mod M,i=0,1,…,⌈M/2⌉−1h(k,i)=\bigl(h(k)+i^{2}\bigr)\bmod M,\quad i=0,1,\dots,\lceil M/2\rceil-1
8第 8 页 · 双平方定理

泾渭分明

双平方定理告诉我们 M 取 4k+3 型素数时平方试探能走通；但实际中表长未必总能精挑，于是 M + Λ 成了兜底。两种策略思路截然不同。

策略一：精选 M
M 取 4k+3 型素数，数学上保证平方试探能命中每一槽
策略二：M + Λ
表长不挑，遇阻塞把基准偏移 Λ 后重启探测，绕开死簇
泾渭之处
前者预先一次性投入、严格无遗漏；后者临场应变，但可能漏探部分空槽
出门前选路 vs 路上遇堵再绕对应 →4k+3 素数 vs M + Λ

同解一道难题：让平方试探走通。一个事前规划、一个临场反应

M=4k+3,k≥0M = 4k + 3,\quad k \geq 0
9第 9 页 · 泾渭分明

本节要点

  • ✓α 越逼近 0.5，探测长度非线性上升，性能塌陷
  • ✓表长取 4k+3 素数可证遍历全表，背后是二次互反律
  • ✓次聚束是平方探测的结构性宿命，源于初探位相同的键
  • ✓双散列并非万能：h₂ 为零时仍会退化为线性探测
  • ✓所有探测法都是探测开销与聚束程度的折中
延伸主题：再散列：扩容与批量重哈希布谷鸟散列的常数时间查找通用散列族与指纹法
10第 10 页 · 本节要点

课后思考

先想，再对。三个问题没有标准答案，参考答案只是抛砖引玉。

1为什么平方探测只在负载因子不超过 1/2 时，才能保证找到空槽？

参考答案探测序列 ±k² 在表中对称跳跃，负载因子超过 1/2 时，空槽可能落在所有跳跃点的间隙里。

2若散列表容量 M 不是 4k+3 型素数，平方探测可能出什么问题？

参考答案探测序列可能提早陷入循环，找不到空槽，即便表未满。4k+3 型素数保证前 ⌈M/2⌉ 步覆盖所有槽位。

3与线性探测相比，平方探测何时明显占优，何时反而吃亏？

参考答案平方探测缓解了主聚类，但仍有次聚类，且跳跃会牺牲缓存局部性。冲突少时差别不大，冲突密集时它更稳健。

11第 11 页 · 课后思考