(c)散列：散列函数

官官方信息技术老师·14 页·深入（追求细节与边界）·0 次浏览·3 天前

✦ (c)散列：散列函数信息技术 (c)散列：散列函数 M+A+D

散列函数冲突处理复杂度工程取舍

(c)散列：散列函数

看清哈希从原理到冲突处理的全部代价，掌握工程取舍依据

按空格/→ 演示下一步

1 / 14 页

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

散列函数冲突处理复杂度工程取舍

(c)散列：散列函数

看清哈希从原理到冲突处理的全部代价，掌握工程取舍依据

1第 1 页 · (c)散列：散列函数

冲突难免

上页讲散列函数把任意输入压缩到固定长度输出。一个硬事实紧随其后：输出位数有限、输入空间无限，撞车不可避免。这页说清楚冲突为何必然、三类抗性的差别，以及工程上如何与其相处。

数学上必然发生

鸽巢原理：输入无穷、输出有限，必有不同 key 落到同一散列值

三类安全抗性

抗碰撞、抗第二原像、抗原像；攻击难度逐级递增

生日攻击砍掉一半

n 位输出的抗碰撞强度仅约 n/2 位，MD5/SHA-1 由此退场

冲突被主动利用

签名摘要、一致性校验、负载均衡都依赖冲突的均匀性

100 个苹果塞 99 个抽屉对应 →无限输入映射到有限散列值

抽屉数小于物品数，必有一格装 ≥2 个；冲突是数学必然而非算法失败

P(\text{冲突})\approx 1-e^{-k^2/2^{n+1}},\quad n\text{-bit},\ k\text{ samples}

2第 2 页 · 冲突难免

何谓优劣

冲突既然避免不了，问题就变成了——什么样的散列函数才算「好」？这就需要一把尺子来衡量。

均匀分布

散列值尽可能均匀落到所有槽位，不出现扎堆

计算迅速

算出散列值的开销要低，否则得不偿失

确定性

相同输入必须映射到同一槽位，否则查不到

雪崩效应

输入改一比特，输出应大面积变化，防止相邻键扎堆

给新生随机分班对应 →散列函数好坏

均匀散=好函数；总把同姓氏塞进同一班=坏函数

3第 3 页 · 何谓优劣

整除留余

散列函数要把关键字变成槽号，整除留余是最朴素的一招：key 除以 m 取余。水全在「表长 m 怎么选」里——选错，键里的规律会原样传染到槽位分布上。

基本形式

h(k) = k mod m，余数即槽号，范围 0 ≤ r < m

m 选素数

取不接近 2 的幂的素数，教科书常推 131、163、257

为什么是素数

素数与任何键的公因子为 1，键的因式结构带不到槽位上

典型应用

整数键最常用的散列方式，教材里的「默认选项」

按编号入座对应 →整除留余

编号÷列数取余得列号；列数是合数时，偶数编号全挤到偶数列

h(k) = k \bmod m

4第 4 页 · 整除留余

以蝉为师

北美的蝉在地下蛰伏13年或17年后集体出洞。这两个数字都是质数——错峰出土能最大程度避开天敌与竞争。散列函数的设计，竟和蝉的生存智慧异曲同工。

散列函数

把任意键值 key 映射到固定范围内存储位置 h(key) 的函数

三个目标

均匀分散键、减少碰撞冲突、计算本身要快

典型应用

字典快速查找、数据库索引、缓存去重、密码摘要

蝉的质数生命周期对应 →散列函数取模运算

蝉用13/17错开出土高峰；散列函数用质数作模数，让键均匀落桶

h(k) = k \bmod p,\quad p \text{ 为质数}

5第 5 页 · 以蝉为师

M+A+D

上页讲到蝉启示的乘法散列、整除留余——这只是冰山一角。几乎所有散列函数的构造都逃不开三类基本运算：M+A+D。掌握这三板斧，就能拆解绝大多数设计。

M=乘法散列

H(k)=⌊m·frac(k·A)⌋，A 取黄金比例等无理数时分布最佳

A=加法/折叠

把关键字分段求和或叠加，适合超长键且计算极简

D=除法散列

H(k)=k mod p，p 取小于 m 的素数时冲突最少

面点师三种基本手法对应 →三类散列方法

乘法=抻面改变长宽比；加法=折叠压成多层；除法=切段取份

H(k) = k \bmod p, \; p \text{ 为素数且 } p \leq m

6第 6 页 · M+A+D

平方取中

前面我们看了除留余数和乘法哈希，都需要表长。平方取中反其道而行——把 key 平方后直接从结果中间挖一段，完全不依赖表长。但这种『自由』是有代价的：分布可能严重退化。

操作步骤

把 key 平方得到 k²，再从 k² 中间挖出 r 位作为散列地址

关键参数 r

r 决定地址范围 [0, 10^r−1]，也间接决定适配的表长

实例演示

1234² = 1522756，取中 3 位 = 227；取中 4 位 = 5227

不依赖表长

只做乘法和截位，无需取模，对表大小无硬约束

分布会退化

key 高位相近时平方中段也相近；小 k 位数少，中段易坍成 0

拉面中间切一段对应 →平方取中

平方等于把数字『拉长』成位数更多的数，从拉长的数中间切下 r 位

h(k)=\lfloor k^2/10^{(d-r)/2}\rfloor\bmod 10^r,\ d=\lfloor\log_{10}k^2\rfloor+1

7第 7 页 · 平方取中

折叠汇总

从「整除留余」一路走到「平方取中」，我们手里攒了四种构造法。它们各自能解决什么问题，又在哪里失灵？这一页折叠汇总。

本质是映射

把关键码 k 唯一确定地变换为地址 H(k)，是查找的前置工序

三大设计目标

均匀分布、确定性、高效计算，三者缺一不可

冲突是宿命

鸽巢原理：地址空间有限、关键码无穷，碰撞不可避免

四种构造武器

除留余数、平方取中、MAD 线性组合、乘法/蝉法

选型看边界

整数/浮点/字符串键各有偏好；M 取 2 的幂便于位运算取模

快递柜取件码对应 →散列函数定位

取件码=关键码，格口=桶位，系统查码开格=散列映射

H(k) \in [0, M),\ M = 2^p

8第 8 页 · 折叠汇总

伪随机数

回想上一页的 MAD：X_{n+1}=(aX_n+c) mod m。这串递推正是最经典的伪随机数生成器 LCG——散列与伪随机本就同源。

算法确定

按递推规则演化，每步输出看似随机的数；本质是确定性状态机

种子定序列

同一种子产出同一序列；这是「伪」的来源，也是实验可复现的基础

必有周期

状态有限，鸽巢原理下序列必然循环；周期长度是质量硬指标

质量分梯度

统计均匀(LCG)→密码学不可预测(CSPRNG)；散列一般只要求前者

散列的好搭档

探测步长、universal hashing 参数、rehash 策略都依赖它

魔术师的固定手法对应 →PRNG

手法固定→每次表演抽出同一张牌；观众觉得神奇，魔术师对每步心知肚明

X_{n+1} = (aX_n + c) \bmod m

9第 9 页 · 伪随机数

多项式

前面学过的方法都把键当成整数处理，可'姓名'、'学号'、'网址'是字符串，怎么变成数字？多项式给出一条优雅路径：把整串字符当作一个多项式来求值。

字符串即多项式

"abc" 对应 a·x² + b·x + c，每字符是一个系数

底数 x 多取素数

31、37、127 是常用值，影响分布是否均匀

Horner 迭代累乘

h = h·x + aᵢ 边乘边 mod，避免指数级膨胀

末了 mod M 收尾

把多项式值压回散列表大小，呼应整除留余

十进制首位决定量级对应 →多项式首位权重最大

1200 与 1024 差 176，量级由首位决定；a₀·xⁿ⁻¹ 贡献远大于末位

H(\text{key}) = \sum_{i=0}^{n-1} a_i\, x^{n-1-i} \bmod M

10第 10 页 · 多项式

Vorldmort

前面讲了除法、乘法、折叠等构造法。Vorldmort 另辟蹊径——它不追求算得快，而是追求「让人看不出规律」。

设计目标

把「不可预测」放在第一位的散列函数

雪崩效应

输入动一位，输出约半数位都翻转

抗分析

难以从输出反推输入的统计特征

典型应用

密码学摘要、哈希表、布隆过滤器

调酒师的隐藏配方对应 →Vorldmort 的混淆效果

原料差一点，出来的酒味道天差地别；尝一口推不出配方

11第 11 页 · Vorldmort

DSA@THU

前面我们盘点了整除留余、数字分析、平方取中、折叠汇总、伪随机数、多项式这些构造方法。现在回到根本：散列函数到底是什么？评判它好坏的尺度是什么？它在工程里又有哪几片用武之地？

本质：键到桶号

将任意查找键 K 映射到 [0, M) 区间内的一个整数，指明记录应落入哪个桶

三条性质

确定性：同一键每次映到同一桶；均匀性：桶号尽可能均匀；高效性：O(1) 内算出

只管映射，不管存储

散列函数本身不解决冲突，冲突化解（开放寻址/桶链）是它之外的另一套机制

典型应用

哈希表判重、字符串检索、密码盐摘要、一致性哈希、缓存分片、布隆过滤器

图书馆索书号系统对应 →散列函数

把书名/作者这种长串缩成一个短码——中图法号直接告诉你去哪个书架，散列号直接告诉你去哪个桶

h(k) \equiv \sum_{i=0}^{n-1} k_i \cdot p^i \pmod{M}

12第 12 页 · DSA@THU

本节要点

✓冲突是必然：鸽巢原理决定 N > M 时必撞
✓好散列函数看均匀性与确定性两件事
✓整数键三法宝：除留余数、MAD、多项式
✓M 选素数且远离 2 的幂，分布才均匀
✓字符串用多项式滚动，要防溢出与顺序错位

延伸主题：冲突解决：开放寻址 vs 链地址rehash：何时扩容、如何搬家加密哈希（SHA）vs 普通哈希

13第 13 页 · 本节要点

课后思考

先自己想 30 秒，再对照参考答案——开放题没有标准答案，思路对就行。

1为什么「整除留余」法对 M 的选择很挑剔？若 M 取 2 的幂，会丢掉 k 的什么信息？

参考答案M 若为 2 的幂，h(k) 只看 k 的低几位，高位被整段丢弃，分布严重不均；所以经典教材才反复强调「尽量用素数」。

2如果关键字不是整数（比如字符串、人名），前面学的散列函数还能直接套用吗？该怎么办？

参考答案不能。需要先把字符串「翻译」成整数——例如按字符编码累加、或做多项式求值——再喂给整数散列函数。

3乘法散列里那个 0.618…（黄金分割数）真的不可替代吗？换个别的小数当乘数会差多少？

参考答案不绝对。0.618… 的连分数展开各商最小，是「最无理数」，低阶散落少、分布均匀；其他小数要看小数展开是否同样「无规律」。

14第 14 页 · 课后思考