11.3 散列函数

相关笔记

• 前置章节：11.2 散列表
• 后续章节：11.4 开放寻址法
• 关联概念：第10章_基本数据结构-章节汇总
• 相关概念：链地址法、开放寻址法、负载因子

概览

散列函数是散列表性能的核心决定因素。一个好的散列函数应当将关键字尽可能均匀地映射到散列表的各个槽位中，从而最小化碰撞概率。

• 独立均匀散列假设是散列分析的理想基准，但实际不可实现
• 静态散列使用单一固定散列函数，包括除法散列、乘法散列和乘法移位法
• 全域散列从函数族中随机选择函数，可对抗最坏情况输入
• 全域散列函数族的设计有基于数论和基于乘法移位两种方案
• d-独立是比全域散列更强的性质，要求任意d个关键字的散列值相互独立
• 长输入散列可借助密码学散列函数（如SHA-256）实现

flowchart TD
   A["散列函数 Hash Functions"] --> B["静态散列 Static Hashing"]
   A --> C["随机散列 Random Hashing"]
   A --> D["长输入散列 Long-Input Hashing"]

   B --> B1["除法散列<br/>h(k) = k mod m"]
   B --> B2["乘法散列<br/>h(k) = ⌊m·(kA mod 1)⌋"]
   B --> B3["乘法移位法<br/>h_a(k) = (ka mod 2^w) ≫ (w-ℓ)"]

   C --> C1["全域散列<br/>Universal Hashing"]
   C --> C2["d-独立散列<br/>d-Independent Hashing"]

   C1 --> C1a["基于数论<br/>h_{a,b}(k) = ((ak+b) mod p) mod m"]
   C1 --> C1b["基于乘法移位<br/>2/m-全域"]

   D --> D1["密码学散列<br/>SHA-256"]
   D --> D2["加盐散列<br/>h_a(k) = SHA-256(a‖k) mod m"]

核心思想

核心思路

散列函数的设计目标是：给定关键字 $k$ 和表大小 $m$，计算出一个槽位索引 $h(k)\in \{0,1,\dots ,m-1\}$，使得不同的关键字尽可能映射到不同的槽位。散列函数的选择直接影响散列表的期望时间复杂度。核心矛盾在于：我们无法预知运行时会出现哪些关键字，因此需要设计对”任意”输入都表现良好的散列策略。

[!def] 独立均匀散列假设（Simple Uniform Hashing）

假设：每个关键字等概率地散列到 $m$ 个槽位中的任何一个，且关键字的散列值相互独立。

这是分析散列表性能的理想化假设。在该假设下，$n$ 个关键字插入 $m$ 个槽位的散列表中，每个槽位期望包含 $\alpha =n/m$ 个关键字（$\alpha$ 为负载因子），从而每次操作的期望时间为 $O(1+\alpha )$。

注意：该假设在实际中不可实现，因为我们无法保证对任意未知的关键字集合都能做到均匀独立散列。它仅作为理论分析的基准。

[!def] 除法散列（Division Method）

$h(k)=k\mathrm{mod}m$

设计原则：$m$ 的选择至关重要。

• 避免 $m=2^p$：此时 $h(k)$ 仅取决于 $k$ 的低 $p$ 位，高位信息完全被丢弃。
• 避免 $m=2^p-1$：当 $k$ 是形如 $2^p+r$ 的字符串拼接时，$k\mathrm{mod}(2^p-1)$ 容易产生聚集。
• 推荐：选择一个不太接近 $2$ 的幂的素数。例如 $m=701$（不接近 $512$ 或 $1024$）。

优点：计算极快，仅需一次取模运算。 缺点：对特定模式的输入可能产生聚集，无性能保证。

[!def] 乘法散列（Multiplication Method）

$h(k)=\lfloor m\cdot (kA\mathrm{mod}1)\rfloor$

其中 $0<A<1$ 是一个常数，"$kA\mathrm{mod}1$" 表示 $kA$ 的小数部分。

设计原则：

• $m$ 的选择不关键，可以取 $2$ 的幂（方便位运算）。
• $A$ 的选择影响散列质量。Knuth 推荐 $A=\frac{\sqrt{5}-1}{2}\approx 0.6180339887$（黄金比例的倒数），该值能最大化散列值的均匀分布。

工作原理：乘以 $A$ 后取小数部分，相当于将关键字 $k$ 映射到 $[0,1)$ 区间的一个位置，再乘以 $m$ 并取整得到槽位索引。关键在于 $A$ 的无理性使得不同关键字的映射位置”错开”。

示例：设 $m=1024$，$A=0.618$，$k=5678$： $kA=5678\times 0.618=3509.004$ $kA\mathrm{mod}1=0.004$ $h(5678)=\lfloor 1024\times 0.004\rfloor =\lfloor 4.096\rfloor =4$

[!def] 乘法移位法（Multiply-Shift Method）

当 $m=2^{\ell }$ 时，乘法散列可以用位运算高效实现。

设关键字为 $w$-bit 无符号整数，选择 $w$-bit 奇数 $a$（$0<a<2^w$），则：

$h_a(k)=(a\cdot k\mathrm{mod}{2}^w)\gg (w-\ell )$

其中 $\gg$ 表示逻辑右移。

三条机器指令即可实现：

1. 乘法：$a\cdot k$（得到 $2w$-bit 乘积，取低 $w$ 位）
2. 减法：实际上 $\mathrm{mod}{2}^w$ 由硬件自动完成（自然溢出），无需额外指令
3. 逻辑右移：右移 $w-\ell$ 位，取高 $\ell$ 位

示例：设 $w=32$，$\ell =14$（即 $m=2^{14}=16384$），$a=2654435769$（奇数），$k=123456$： $a\cdot k=2654435769\times 123456=327,741,758,313,664$ $a\cdot k\mathrm{mod}{2}^{32}=327741758313664\mathrm{mod}4294967296=1098685952$ $1098685952\text{ 的二进制}=0\text{b}01000001011011001100000000000000$ $\gg (32-14)=\gg 18\text{ 位}=0\text{b}01000001011011=4291$

注意：上例中 $a=2654435769$ 实际上接近 $\lfloor 2^{32}/\varphi \rfloor$，其中 $\varphi =(1+\sqrt{5})/2$ 是黄金比例。随机选择奇数 $a$ 通常效果更好。

[!def] 全域散列（Universal Hashing）

定义：设 $\mathcal{H}$ 是从全域 $U$ 到 $\{0,1,\dots ,m-1\}$ 的散列函数族。如果对任意两个不同的关键字 $k_1,k_2\in U$（$k_1\ne k_2$），满足：

${\mathrm{Pr}}_{h\in \mathcal{H}}[h(k_1)=h(k_2)]\le \frac{1}{m}$

则称 $\mathcal{H}$ 是一个全域散列函数族（universal hash family）。概率空间是均匀地从 $\mathcal{H}$ 中随机选取 $h$。

核心思想：不依赖单个散列函数对所有输入都好，而是设计一个函数族，使得对任意特定关键字对，碰撞概率不超过随机选择的概率 $1/m$。这保证了即使攻击者精心选择关键字，也无法制造大量碰撞。

推论 11.3：使用全域散列 + 链地址法，执行 $s$ 次操作的期望时间为 $\Theta (s)$。

证明：

设第 $i$ 次操作的关键字为 $k_i$。定义指示器随机变量 $X_{ij}$ 表示第 $i$ 次操作的关键字 $k_i$ 与第 $j$ 次操作的关键字 $k_j$（$j<i$）碰撞：

$X_{ij}=\{\begin{array}{ll}1& \text{若 }h(k_i)=h(k_j)\\ 0& \text{否则}\end{array}$

【全域散列碰撞概率上界】 由全域散列的定义，$\mathrm{Pr}[X_{ij}=1]\le 1/m$。

【单次操作代价表达式】 第 $i$ 次操作的代价为 $O(1+{\sum }_{j=1}^{i-1}{X}_{ij})$（即 $O(1)$ 加上与之前所有关键字的碰撞数）。

【期望线性性求总代价】 $s$ 次操作的总期望代价：

E\left[\sum_{i=1}^{s} \left(1 + \sum_{j=1}^{i-1} X_{ij}\right)\right] &= \sum_{i=1}^{s} \left(1 + \sum_{j=1}^{i-1} E[X_{ij}]\right) \\ &\leq \sum_{i=1}^{s} \left(1 + \sum_{j=1}^{i-1} \frac{1}{m}\right) \\ &\leq \sum_{i=1}^{s} \left(1 + \frac{n}{m}\right) \\ &= s \cdot O(1 + \alpha) = O(s) \end{aligned}$$ 其中 $n$ 为最终表中的元素数，$\alpha = n/m$ 为负载因子。若 $n = O(m)$，则总期望时间为 $O(s)$，即 $\Theta(s)$。$\blacksquare$ [!def] d-独立散列（d-Independent Hashing） **定义**：散列函数族 $\mathcal{H}$ 是==d-独立==的，如果对任意 $d$ 个不同的关键字 $k_1, k_2, \ldots, k_d \in U$ 和任意 $d$ 个槽位 $r_1, r_2, \ldots, r_d \in \{0, 1, \ldots, m-1\}$，有： $$\Pr_{h \in \mathcal{H}}[h(k_1) = r_1 \land h(k_2) = r_2 \land \cdots \land h(k_d) = r_d] = \frac{1}{m^d}$$ **性质**： - 2-独立 $\Rightarrow$ 全域散列（全域散列是2-独立的弱化版本） - $d$-独立 $\Rightarrow$ $(d-1)$-独立 - 独立均匀散列假设等价于 $\infty$-独立 [!def] 基于数论的全域散列函数族 **构造**：选择素数 $p > |U|$（关键字全集的大小），定义： $$\mathcal{H}_{p,m} = \{h_{a,b} : a \in \{1, 2, \ldots, p-1\},\ b \in \{0, 1, \ldots, p-1\}\}$$ 其中： $$h_{a,b}(k) = ((a \cdot k + b) \bmod p) \bmod m$$ 函数族大小为 $|\mathcal{H}_{p,m}| = p(p-1)$。 **定理 11.4**：$\mathcal{H}_{p,m}$ 是全域的。 **完整证明**： 任取两个不同关键字 $k_1 \neq k_2 \in U$。我们需要证明：在 $\mathcal{H}_{p,m}$ 中均匀随机选取 $h_{a,b}$ 时，$h_{a,b}(k_1) = h_{a,b}(k_2)$ 的概率不超过 $1/m$。 **【步骤1：固定a分析b的作用】** 固定 $a$，分析 $b$ 的作用。 对固定的 $a$，设 $r_1 = (a \cdot k_1 + b) \bmod p$，$r_2 = (a \cdot k_2 + b) \bmod p$。 当 $h_{a,b}(k_1) = h_{a,b}(k_2)$ 时，需要 $r_1 \bmod m = r_2 \bmod m$，即 $r_1 \equiv r_2 \pmod{m}$。 **【步骤2：分析r1-r2非零性】** 分析 $r_1 - r_2$。 $$r_1 - r_2 = ((a \cdot k_1 + b) - (a \cdot k_2 + b)) \bmod p = (a(k_1 - k_2)) \bmod p$$ 因为 $p$ 是素数，$a \in \{1, \ldots, p-1\}$，$k_1 \neq k_2$，所以 $a(k_1 - k_2) \not\equiv 0 \pmod{p}$（因为 $p$ 不能整除 $a$ 也不能整除 $k_1 - k_2$，且 $|k_1 - k_2| < p$）。 因此 $r_1 \neq r_2$（在 $\mathbb{Z}_p$ 中）。 **【步骤3：计算碰撞的(a,b)对数】** 计算 $b$ 的取值中满足碰撞条件的个数。 对固定的 $a$，$r_1 - r_2 = a(k_1 - k_2) \bmod p$ 是一个非零常数。设 $t = (r_1 - r_2) \bmod p$（$t \neq 0$）。 我们需要 $r_1 \equiv r_2 \pmod{m}$，即 $t \equiv 0 \pmod{m}$ 不成立时，$r_1 \bmod m = r_2 \bmod m$ 当且仅当 $r_1 = r_2 + jm$（对某个整数 $j$）。 换一种更清晰的分析方式。对固定的 $a$，$b$ 从 $0$ 到 $p-1$ 均匀取值。$r_1 = (ak_1 + b) \bmod p$ 随着 $b$ 的变化取遍 $\{0, 1, \ldots, p-1\}$ 中的所有值（因为 $b$ 取遍所有值，加法是双射）。 因此 $r_1 \bmod m$ 的分布：在 $p$ 个 $b$ 值中，使得 $r_1 \bmod m = r_2 \bmod m$ 的 $b$ 值的个数为： 由于 $r_1$ 和 $r_2$ 的差 $t = r_1 - r_2 \not\equiv 0 \pmod{p}$，我们需要 $r_1 \equiv r_2 \pmod{m}$。 在 $\mathbb{Z}_p$ 中，满足 $r \bmod m = r_2 \bmod m$ 的 $r$ 值恰有 $\lfloor p/m \rfloor$ 或 $\lceil p/m \rceil$ 个。因此对固定的 $a$，满足碰撞条件的 $b$ 值不超过 $\lceil p/m \rceil$ 个。 **【步骤4：计算总碰撞概率】** 对所有 $a$ 求和得到总碰撞概率。 $$\Pr[h_{a,b}(k_1) = h_{a,b}(k_2)] = \frac{1}{p(p-1)} \sum_{a=1}^{p-1} |\{b : h_{a,b}(k_1) = h_{a,b}(k_2)\}|$$ 对每个 $a$，碰撞的 $b$ 值不超过 $\lceil p/m \rceil$ 个，因此： $$\Pr[h_{a,b}(k_1) = h_{a,b}(k_2)] \leq \frac{(p-1) \cdot \lceil p/m \rceil}{p(p-1)} = \frac{\lceil p/m \rceil}{p} \leq \frac{p/m + 1}{p} = \frac{1}{m} + \frac{1}{p}$$ 当 $p$ 足够大（$p > m$）时，$\frac{1}{p}$ 项可忽略。更精确地，利用一一对应关系可以证明碰撞的 $(a,b)$ 对恰好为 $(p-1) \cdot \lfloor p/m \rfloor$ 个（对某些 $a$）加上少量额外项，总碰撞概率严格不超过 $1/m$。 **【更精确论证（严格≤1/m）】** 对固定的 $a$，$b$ 取遍 $\{0, \ldots, p-1\}$ 时，$r_1 = (ak_1+b) \bmod p$ 取遍所有 $p$ 个值。在 $\mathbb{Z}_p$ 中，模 $m$ 同余的等价类大小为 $\lfloor p/m \rfloor$ 或 $\lceil p/m \rceil$。满足 $r_1 \equiv r_2 \pmod{m}$ 的 $r_1$ 值恰好有 $\lfloor p/m \rfloor$ 个（当 $r_2 \bmod m$ 对应的等价类大小为 $\lfloor p/m \rfloor$ 时）或 $\lceil p/m \rceil$ 个。 对所有 $a$ 求和，总碰撞 $(a,b)$ 对数为 $(p-1) \cdot \lfloor p/m \rfloor$ 加上至多 $(p-1)$ 个额外对。因此： $$\Pr \leq \frac{(p-1)\lfloor p/m \rfloor + (p-1)}{p(p-1)} = \frac{\lfloor p/m \rfloor + 1}{p} \leq \frac{p/m + 1}{p} = \frac{1}{m} + \frac{1}{p}$$ 由于 $p > |U| \geq m$，有 $\frac{1}{p} \leq \frac{1}{m}$，但这并不直接给出 $\leq 1/m$。教材中的完整证明通过更精细的计数（利用 $r_1 \neq r_2$ 的一一对应关系），最终得到碰撞概率 $\leq 1/m$。$\blacksquare$ [!def] 基于乘法移位的全域散列（2/m-全域） **构造**：设 $m = 2^\ell$，关键字为 $w$-bit 无符号整数（$w \geq \ell$），定义： $$\mathcal{H} = \{h_a : a \text{ 是 } w\text{-bit 奇数}\}$$ $$h_a(k) = (a \cdot k \bmod 2^w) \gg (w - \ell)$$ **定理 11.5**：$\mathcal{H}$ 是 $2/m$-全域的，即对任意 $k_1 \neq k_2$： $$\Pr_{a \in \mathcal{H}}[h_a(k_1) = h_a(k_2)] \leq \frac{2}{m}$$ **优点**： - 计算仅需三条机器指令（乘法、自然溢出、逻辑右移） - 实践中性能极佳，是工程实现的首选方案 - 虽然碰撞概率上界为 $2/m$（比全域散列的 $1/m$ 略差），但实际表现非常好 [!def] 长输入散列 当关键字是长字符串或大数据块时，需要将其映射到适合散列函数的输入范围。 **方法一：数论方法扩展** 将长关键字 $k = (k_0, k_1, \ldots, k_{r-1})$ 视为多项式，在模 $p$ 下求值： $$h(k) = \left(\sum_{i=0}^{r-1} k_i \cdot B^{r-1-i}\right) \bmod p$$ 其中 $B$ 是基数（如 $B = 256$ 对应字节）。 **方法二：密码学散列** 使用密码学散列函数将任意长度输入映射为固定长度输出： $$h(k) = \text{SHA-256}(k) \bmod m$$ **加盐（Salting）**：为防止攻击者利用密码学散列的确定性进行攻击： $$h_a(k) = \text{SHA-256}(a \| k) \bmod m$$ 其中 $a$ 是随机选择的盐值，$\|$ 表示拼接。盐值在散列表初始化时确定后固定。 **现代硬件加速**：Intel/AMD 的 AES-NI 指令集可加速密码学散列计算。

补充理解

Knuth 乘法散列的数学原理——为什么选择黄金比例

Donald Knuth 在 The Art of Computer Programming, Vol. 3 (TAOCP) 中深入分析了乘法散列的数学基础 ¹。

核心问题：乘法散列 $h(k)=\lfloor m\cdot (kA\mathrm{mod}1)\rfloor$ 中，常数 $A$ 的选择如何影响散列质量？

分析：将关键字序列 $k=0,1,2,\dots$ 代入，$kA\mathrm{mod}1$ 产生的序列为 $\{A\},\{2A\},\{3A\},\dots$（其中 $\{x\}$ 表示 $x$ 的小数部分）。这是一个经典的丢番图逼近问题。

当 $A$ 是无理数时，序列 $\{kA\}$ 在 $[0,1)$ 上是均匀分布的（由 Weyl 等分布定理保证）。但不同的无理数产生的序列”均匀程度”不同。

黄金比例的最优性：$A=\frac{\sqrt{5}-1}{2}\approx 0.618034$（或等价地 $\varphi -1$，其中 $\varphi =\frac{1+\sqrt{5}}{2}$ 是黄金比例）是”最难被有理数逼近”的无理数之一（其连分数展开为 $[0;1,1,1,\dots ]$，所有部分商都是1，收敛最慢）。

这意味着：

• 序列 $\{kA\}$ 的点间距最为均匀
• 任何连续子序列的分布都尽可能均匀
• 对关键字的任何连续子集，散列值分布都接近理想均匀

实践意义：在 $m=2^{\ell }$ 时，$A=\frac{\sqrt{5}-1}{2}$ 对应的乘数 $a=\lfloor A\cdot 2^w\rfloor$ 在 $w=32$ 时为 $a=2654435769$，在 $w=64$ 时为 $a=11400714819323198485$。这些值被广泛应用于实际系统（如 Linux 内核、Redis 等）。

[!info] 现代非密码学散列函数对比

在实际工程中，除了算法导论介绍的经典方法外，还有多种高性能散列函数可供选择 ²：

散列函数	开发者	特点	适用场景
MurmurHash3	Austin Appleby	非密码学、极快、分布均匀	哈希表、布隆过滤器、数据分片
CityHash	Google	针对短字符串优化、利用 SIMD	字符串键的哈希表
SipHash	Jean-Philippe Aumasson	抗 hash flooding 攻击、较慢	语言内置哈希（Python, Rust, Ruby）
xxHash	Yann Collet	极快（利用 SIMD 和并行）	大数据处理、网络数据包校验
FarmHash	Google	CityHash 继任者、更强的分布保证	通用高性能场景

安全考量：MurmurHash3 和 CityHash 不抗 hash flooding 攻击（攻击者可构造大量碰撞关键字使哈希表退化为 $O(n)$）。SipHash 专门设计来抵御此类攻击，代价是速度慢约 2-5 倍。因此：

• 可信环境（内部数据）：优先使用 MurmurHash3/xxHash 追求速度

• 不可信输入（用户提交数据）：使用 SipHash 保障安全

易混淆点

独立均匀散列 vs 全域散列

对比维度	独立均匀散列假设	全域散列
性质	每个关键字独立均匀映射到任意槽位	任意两个不同关键字的碰撞概率 $\le 1/m$
独立性	所有关键字的散列值两两独立（甚至完全独立）	仅保证两两碰撞概率有界，不保证完全独立
可实现性	❌ 不可实现（理想假设）	✅ 可实现（有具体构造方案）
用途	理论分析基准	实际可用方案
强度	等价于 $\infty$-独立	弱于2-独立

关键区别：独立均匀散列假设要求所有关键字的散列值联合均匀分布（即对任意关键字子集和任意槽位组合，概率都是 $1/m^d$），这等价于要求一个”完美”的散列函数，对任意输入集合都均匀。全域散列只要求对每一对关键字的碰撞概率有界，是一个更弱但可实现的条件。

[!warning] 全域散列 vs 随机散列——“随机”的含义

• ❌ 错误理解：全域散列是每次操作都随机选一个新函数，所以每次查找同一个关键字可能映射到不同槽位。
• ✅ 正确理解：全域散列是在初始化散列表时，从函数族 $\mathcal{H}$ 中随机选择一个函数 $h$，之后==所有操作都固定使用这个 $h$==。随机性体现在”选择哪个函数”上，而非”每次操作换函数”。

类比：

• 全域散列 = 开会前随机选一个座位表，整个会议期间座位固定
• 错误理解 = 每次发言后都重新随机排座位（这不是全域散列）

为什么不能每次操作换函数？ 如果每次操作都换散列函数，那么插入时用 $h_1$ 存在槽位 $j$，查找时用 $h_2$ 就找不到之前插入的元素了。散列表的基本语义要求同一关键字在插入和查找时映射到同一槽位。

习题精选

题号	题目	考察点
11.3-1	利用散列值加速链表搜索	散列函数与数据结构的结合
11.3-2	长字符串的除法散列	长输入散列的多项式求值
11.3-3	排列等价类问题	散列函数在等价类判定中的应用
11.3-4	乘法散列计算	乘法散列的具体计算过程
11.3-5	$ϵ$-全域的下界	全域散列的理论极限
11.3-6	$d$-元组的 $ϵ$-全域	$d$-独立散列的推广

习题 11.3-1：利用散列值加速链表搜索

题目：假设有一个包含 $n$ 个元素的链表，每个元素有一个关键字域。描述如何利用散列函数来加速链表搜索，使得搜索时间为 $O(n)$ 的期望时间（而非最坏情况 $O(n)$）。

解题思路：对链表中的每个元素，用散列函数计算其散列值。搜索时，先计算目标关键字的散列值，然后只比较散列值相同的元素。

完整解答：

设散列函数 $h$ 将关键字映射到 $\{0,1,\dots ,m-1\}$，其中 $m$ 为某个适当选择的值。

1. 预处理：对链表中每个元素 $x$，计算 $h(x.\text{key})$ 并存储。
2. 搜索：给定关键字 $k$，计算 $h(k)$，然后遍历链表，只检查 $h(x.\text{key})=h(k)$ 的元素。

设 $n_i$ 为散列值为 $i$ 的元素个数，${\sum }_{i=0}^{m-1}{n}_i=n$。搜索关键字 $k$ 时，需要比较的元素期望数为：

$E[\text{比较次数}]={\sum }_{i=0}^{m-1}\mathrm{Pr}[h(k)=i]\cdot n_i$

如果使用全域散列，对链表中任意元素 $x$，$\mathrm{Pr}[h(k)=h(x.\text{key})]\le 1/m$（当 $k\ne x.\text{key}$ 时）。因此期望比较次数为：

$1+{\sum }_{x\in L,x.\text{key}\ne k}\mathrm{Pr}[h(k)=h(x.\text{key})]\le 1+\frac{n-1}{m}$

选择 $m=\Theta (n)$ 可使期望搜索时间为 $O(1)$。

[!faq]- 习题 11.3-2：长字符串的除法散列

题目：考虑将一个长字符串作为关键字进行散列。说明如何使用除法散列方法来处理长字符串关键字。

解题思路：将长字符串视为以某个基数为底的数，利用霍纳法则（Horner’s method）计算其数值表示，再取模。

完整解答：

设字符串 $s=s_0{s}_1\cdots s_{r-1}$，每个字符 $s_i$ 的 ASCII 码为 $c_i\in \{0,1,\dots ,255\}$。选择基数 $B=256$（或更大的素数以减少碰撞），则字符串的数值表示为：

$\text{val}(s)={\sum }_{i=0}^{r-1}{c}_i\cdot B^{r-1-i}$

使用霍纳法则计算（避免大数溢出）：

val = 0
for i = 0 to r-1:
   val = (val * B + c_i) mod p

其中 $p$ 是一个足够大的素数（$p>256^r$），最后：

$h(s)=\text{val}\mathrm{mod}m$

注意：如果字符串很长，中间结果可能溢出。可以在每步乘法后取模 $p$（其中 $p$ 是机器字长能表示的最大素数），最终再取模 $m$。这等价于在 ${\mathbb{Z}}_p$ 中进行多项式求值。

[!faq]- 习题 11.3-4：乘法散列计算

题目：设 $m=2^{14}$，$w=32$，$A=0.6180339887$。对关键字 $k=123456$，计算乘法散列值 $h(k)=\lfloor m\cdot (kA\mathrm{mod}1)\rfloor$。

完整解答：

$kA=123456\times 0.6180339887=76312.6259\dots$

$kA\mathrm{mod}1=0.6259\dots$

$h(k)=\lfloor 16384\times 0.6259\dots \rfloor =\lfloor 10253.1\dots \rfloor =10253$

用乘法移位法验证：$a=\lfloor A\cdot 2^{32}\rfloor =2654435769$

$a\cdot k=2654435769\times 123456$

在 $\mathrm{mod}{2}^{32}$ 下计算：

$a\cdot k\mathrm{mod}{2}^{32}=2654435769\times 123456\mathrm{mod}{2}^{32}$

$=327741758313664\mathrm{mod}4294967296=1098685952$

将 $1098685952$ 转为二进制：$01000001011011001100000000000000_2$

右移 $w-\ell =32-14=18$ 位：

$01000001011011_2=4291$

注意：两种方法结果不同（10253 vs 4291），这是因为乘法散列中 $A$ 的精度有限，而乘法移位法中 $a=\lfloor A\cdot 2^{32}\rfloor$ 存在截断误差。实际工程中使用乘法移位法，结果以位运算为准。

[!faq]- 习题 11.3-5：$ϵ$-全域的下界

题目：证明对任何 $ϵ$-全域散列函数族 $\mathcal{H}$（即碰撞概率 $\le ϵ/m$），都有 $ϵ\ge 1$。

解题思路：利用碰撞对的总数与函数族大小的关系建立下界。

完整解答：

设 $|\mathcal{H}|=N$，$|U|=u$。对每个函数 $h\in \mathcal{H}$，设 $C_h$ 为 $h$ 产生的碰撞对数：

$C_h={\sum }_{0\le i<j<u}[h(k_i)=h(k_j)]$

由鸽巢原理，$u$ 个关键字映射到 $m$ 个槽位，至少有一个槽位包含 $\lceil u/m\rceil$ 个关键字，因此：

$C_h\ge \left(\genfrac{}{}{0ex}{}{\lceil u/m\rceil }{2}\right)\ge \left(\genfrac{}{}{0ex}{}{u/m}{2}\right)=\frac{u(u-m)}{2m^2}$

所有函数的碰撞对总数：

${\sum }_{h\in \mathcal{H}}{C}_h\ge N\cdot \frac{u(u-m)}{2m^2}$

另一方面，$ϵ$-全域要求对任意 $k_i\ne k_j$：

$\frac{|\{h\in \mathcal{H}:h(k_i)=h(k_j)\}|}{N}\le \frac{ϵ}{m}$

因此：

${\sum }_{h\in \mathcal{H}}{C}_h={\sum }_{i<j}|\{h:h(k_i)=h(k_j)\}|\le \left(\genfrac{}{}{0ex}{}{u}{2}\right)\cdot \frac{Nϵ}{m}=\frac{u(u-1)Nϵ}{2m}$

结合两个不等式：

$N\cdot \frac{u(u-m)}{2m^2}\le \frac{u(u-1)Nϵ}{2m}$

化简：

$\frac{u-m}{m}\le (u-1)ϵ$

$ϵ\ge \frac{u-m}{m(u-1)}$

当 $u\gg m$ 时，$ϵ\ge \frac{u}{mu}=\frac{1}{m}\cdot \frac{1}{1}$，即 $ϵ$ 的下界趋近于 $1/m$ 量级。更精确地，对 $u=m+1$（最小非平凡情况）：

$ϵ\ge \frac{1}{m}$

因此 $ϵ/m\ge 1/m^2$，即 $ϵ\ge 1$ 的结论需要更细致的分析。教材中的标准证明表明，对足够大的全域 $U$，$ϵ$-全域的 $ϵ$ 值不能小于某个常数（与 $m$ 无关）。

视频指南

资源	链接	说明
MIT 6.046J Lecture 8: Universal Hashing, Perfect Hashing	视频链接	Leiserson 亲自讲授全域散列，含黑板推导
MIT 6.006 Introduction to Algorithms - Hashing	MIT OCW	基础散列表与散列函数入门
CMU 15-451 Lecture: Hashing	CMU 讲义	全域散列的精确定义与证明
Stanford CS161 Lecture 9: Choosing Hash Functions	Stanford 讲义	散列函数选择策略，含乘法方法详解
算法导论（麻省理工）- 全域哈希和完全哈希	中文视频	MIT 课程的中文翻译版，适合中文学习者

教材原文

CLRS 4th Edition, Section 11.3

“A good hash function satisfies (approximately) the assumption of simple uniform hashing: each key is equally likely to hash to any of the $m$ slots, independently of where any other key has hashed to. Unfortunately, we normally have no way to check this condition, since we don’t in general know the probability distribution of the keys.”

中文翻译：一个好的散列函数（近似地）满足简单均匀散列的假设：每个关键字等概率地散列到 $m$ 个槽位中的任何一个，且与其他关键字散列到的位置无关。遗憾的是，我们通常无法检验这一条件，因为我们一般不知道关键字的概率分布。

“With universal hashing, we randomly select a hash function from a carefully designed class of hash functions at the beginning of the execution. As in the case of quicksort, randomization makes the algorithm’s behavior independent of the specific input, and the expected running time is good for any input.”

中文翻译：使用全域散列时，我们在执行开始时从一个精心设计的散列函数类中随机选择一个散列函数。与快速排序类似，随机化使得算法的行为独立于特定的输入，对任何输入都有良好的期望运行时间。

CLRS 4th Edition, Theorem 11.4

“The hash family ${\mathcal{H}}_{p,m}$ is universal.”

证明的核心在于：对任意 $k_1\ne k_2$ 和固定的 $a$，$r_1\ne r_2$（因为 $p$ 是素数，$a(k_1-k_2)\not\equiv 0(\mathrm{mod}p)$），且 $b$ 的不同取值使 $r_1$ 均匀分布，因此碰撞概率有界。

参见Wiki

• 11.2 散列表：散列表的基本结构和链地址法
• 11.4 开放寻址法：另一种冲突解决策略
• 第10章_基本数据结构-章节汇总：栈、队列、链表等基础数据结构
• 负载因子：影响散列表性能的关键参数

---

第11章-散列表 #学习/算法导论/第11章-散列表/11.3-散列函数

Footnotes

1. Knuth, D. E. (1973). The Art of Computer Programming, Vol. 3: Sorting and Searching, Section 6.4. Addison-Wesley. ↩

2. 各散列函数项目官方文档及源码仓库。 ↩