💻 CSC4120 Week 5 哈希与密码学

Lithos

CSC4120 W05 Hashing and Cryptography

I. Key Principles of Hashing

哈希表 是一种直接计算元素应该存在哪里，从而实现平均 O(1) 搜索的 ADT：

数据结构 Search Insert Delete
Unsorted Array | O(n) | O(1) | O(1)*
Sorted Array | O(log n) | O(n) | O(n)
AVL Tree | O(log n) | O(log n) | O(log n)
vEB Tree | O(log log u) | O(log log u) | O(log log u)
Hash Table | 平均 O(1) | 平均 O(1) | 平均 O(1)

数组的问题：假设存储来自于 U = {0, 1, 999999} 的 n = 100 个元素，即使数组宽度很短，但如果想 O(1) 查询，用 BitSet 就要 106 个 key，最终仅利用庞大 key universe 的 0.01%，浪费。


哈希函数

Hash Function (哈希函数)：将任意大小的输入映射为固定大小的输出值的所有函数

  • MD5 哈希函数将所有长度的输入转化为一段 16B 信息；
  • 模运算也是哈希函数，桶的个数等于模数 (即除数)
  • 甚至如果输入有界 (收敛)，Identity Function y=x 也是哈希函数，虽然很差

哈希 h: U → {0,1, … ,m-1}，其中 h(k) 表示 key k 的映射结果，m 为桶数 (哈希表 T 的大小)

  1. 哈希函数结果不必随机，比如模运算可预期且永远一致。

  2. 哈希函数无需双射 (逐一对应)，但希望不同输入尽可能均匀地分散到不同位置：把键映射为尽量不同的整数。

    应尽可能避免输入数据的规律造成大量碰撞 (落到同个桶) 导致退化回数组

    仅当我们知道所有键时可以设计出完美哈希 (双射)


Mid-square Method

平方取中法是一种简单的整数 key 的哈希方法：

将 key 平方；从结果中截取中间 r bits；将截取结果作为 hash value ∈ {0, 2r -1}

取 d 位就是 {0, 10d -1}

平方比简单取余更好，因为平方运算会使输入中不同位置的数字相互影响。例如，输入高位发生变化，也可能影响平方结果的中间位，因此它可以减轻某些输入规律对哈希分布的影响。不过平方取中并不能保证均匀分布。


非数值键哈希

首先可以将字符转通过 ASCII 编码转为数字，比如 a ≡ 97DEC ≡ 61HEX, A ≡ 65DEC ≡ 41HEX

因此可以把字符串看作一个 base-128 的数字，即，每个字符定长 7-bit

  • E.g.：ABC → 65 x 1282 + 66 x 128 + 67 = 1073475 并使用这个整数键做哈希

  • 字符串编码为整数 和 整数映射到哈希表位置 可以合并实现，但概念上不是同个步骤


Hash Collision

冲突不可避免，因为不完美的哈希函数和有限的桶，导致不同 key 被映射到同个桶

根据 Pigeonhole Principle (鸽巢原理)：当输入数量 |U| 大于输出位置数量 m 时，必存在 k1 ≠ k2 使 h(k1) = h(k2)，称为 Collision (冲突).

C++ std::unordered_map 采用分离链表/链地址法 (separate chaining) 解决冲突，让每个桶保存一条小链表，所有哈希值相等的元素存到链结构中。此时 ⚠️ 哈希表的搜索效率取决于 Collision 导致的链表长度 L：O(1+L) 计算哈希 + 遍历链表

Worst-case Lemma：根据鸽巢原理，对于任意哈希函数 hU→m ，存在一个桶，至少 ⌈|U|/m⌉ 个不同 universal keys 映射到这个桶

如果恶意程序故意挑选这些 key 全部插入哈希表，就会形成长链表，导致 Worst-case Search = O(n)

（⚠️ 这不意味着实际存储的 n 个 key 必然产生这么多碰撞）



2 Types of Randomness Models

虽然 wcc hashing search 为 O(n)，但平均 O(1)

这是因为我们引入了概率模型：

  1. Simple Uniform Hashing Assumption（SUHA）
  2. Universal Hashing

SUHA

SUHA 假设 Hash Function h 固定，key 随机均匀的从 U 抽取。在此前提下，当 h(k) 结果均匀分布在 {1, …, m} 上，即 $P_k(h(k)=i) = {1\over m},\ \forall i \in {1, …, m}$ 时——

  • 我们认为 h 是一个“好”的哈希函数
  • h 是伪随机的均匀分布

SUHA 的缺点是它对 key 的分布提出了要求，而实际上往往无法控制用户输入数据的分布


Universal Hashing

Universal Hashing 与 SUHA 正相反，固定 Key，但 h 随机从一个全局哈希函数集合 H 中均匀抽取。在此前提下，当任意两键碰撞的概率不高于 1/m，即 $P_h(h(k_1)=h(k_2)) ≤ {1\over m}\ \forall k_1 ≠ k_2$ 时——

  • 我们认为 H 是一个 Universal 的哈希函数集合
  • 对于任意两个不同 key，在 H 中最多只有 |H|/m 个函数会让它们发生碰撞。

⚠️ SUHA 和 Universal Hashing 并不等价，但可以得到类似的平均复杂度分析。直觉来说，我们默认使用 SUHA 模型。


Division Method

以 h(k)=k mod m 为例，m 个桶分别对应 |U|/m 个 key。如果从 Universe 随机选 Key，$P_k(h(k)=i) = {1\over m}$，因此 h(k) 满足 SUHA；但如果 key 都是 4 的倍数就不满足

所以一个哈希函数是否满足 SUHA，要结合 key 的概率分布判断。


Multiplication Method

h(k) = ⌊m(kA mod 1)⌋，其中 A = ${\sqrt{5} -1\over 2}$ ≈ 0.618；mod 1 表示取小数部分。

这个方法利用乘法和取小数部分，将 key 分散到不同位置。在实践中，它近似均匀散列，近似 SUHA。



SUHA 概率计算

哈希结果的本质等同于 将 n 个球随机扔进 m 个箱子 的概率问题

Load Factor

将桶 (slot) i 中的元素数量记作 Xi，n = Σω=0m-1Xω，取期望 n = Σω=0m-1E[Xω]，每个位置概率均等，故 E[Xi] = n/m = α

所有桶中键的数量 n；哈希表桶的个数 m，⚠️ 装载因子 LoadFactor = ${n \over m} = E[X_i] = α$，就是每个桶平均装了多少键，直接反映了哈希表的拥挤程度。对于链地址法，α 可以大于 1。


Empty Slots

定义指示随机变量 Yi ∈ {0, 1|Y=1 if slot empty, Y=0 if not}，所以 E[Yi] = P(slot i 为空) = 1xP(Yi=1) + 0xP(Yi=0) = P(Yi=1)

每个键落进桶 i 的概率为 1/m，反之不落入就是 1-1/m，在键相互独立的前提下 E[Yi] = P(slot i 为空) = (1-1/m)n

⚠️ 所以总共的空位数期望就是 E[Y] = Σi=0m-1E[Yi] = m(1-1/m)n

当 n=m 时 E[Y] = m(1-1/m)m，${E[Y] \over m} = (1- {1\over m})^m$，因为 $\lim_{m → \infty} (1- {1\over m})^m = {1\over e}$ ≈ 36.79%

即使键和桶数量一样多，平均上仍有约 36.8% 的桶为空，36.8% 的桶有一个元素，26.4% 的桶存储至少两个元素，即发生 Collision。

如果要用上所有 m 个桶，先考虑“当有 k 个非空 slots，平均哈希多少个键才进入一个空 slot？”—— 下一次进入空 slot 的概率 pk = (n-k) / n，问题符合 ⚠️ 几何分布：对于成功概率为 p 的几何分布，直到首次成功所需的试验次数的期望为 E[Xk] = 1 / pk = n / (n-k)

所以让所有桶非空需要 T = Σk=0n-1Xk 次，故 E[T] = n/n + n/(n-1) + … + n/1 = n(1 + 2-1 + 3-1 + … + n-1) = ⚠️ nΣi=1n (i-1)。

即让所有桶都至少有一个键的期望为 n x n 的几何级数次哈希，⚠️ E[T] = Θ(nlogn)

n 个球投入 n 个 bins，最拥挤的 bin 有多少球？

X1 ～ Binomial(n, 1/n)，P(X1 = k) = ${n \choose k} ({1\over n})^k (1-{1\over n})^{n-k}$，当 n → ∞，使用 Poisson Approx. P(X1 = k) = e-1/k!，Union Bound P(X1 ≥ k) ≤ (e/k)k，P(max{Xi} ≥ k) ≤ n(e/k)k

考虑 n(e/k)k，取对 ln(n) + k(1-ln(k)) 临界位置 ≈ 0，即 k(ln(k)-1) ≈ ln(n)，k 大时近似 k = $\ln n \over \ln \ln n$，所以 E[max{Xi}] = Θ($\ln n \over \ln \ln n$)



哈希表 T 搜索 Search(k) 需要计算 h(k) 然后遍历 T[h(k)]，O(1+L) 其中 L 表示 h(k) 链表长度。

  • Successful Search：假设 k 存在于 T，在 Universal Hashing 下：对于任意 y≠k，P(h(y)=h(k)) ≤ 1/m

    对于 k 以外的 n-1 个元素中，与 k 碰撞的期望数量不超过 (n-1) / m

    加上 k 本身 E[L] ≤ 1 + (n-1)/m

    ⚠️ 这是对整条链表长度的界，因此也给出了搜索工作量的上界；实际成功查找可能在遍历完整条链表之前就找到目标

  • Unsuccessful Search：目标不存在时必然遍历 n 个键，即 E[L] ≤ n/m

加上计算 Hash Function 的常数时间：E[T] = O(1 + n/m) = O(1 + α) 当 n 为 m 的常数 c 倍，α = c，那么 E[T] = O(1) 常数时间。

当负载因子保持为常数时，在良好的随机性模型下，平均链表长度也是常数，哈希搜索就是常数时间




II. Universal Hashing, String Matching and Table Doubling

comments powered by Disqus