COMP5270 Assignment 2 Problem 2(a), Pairwise Independent Hash Functions

中文题目

实现课程中讲到的两两独立哈希函数族（pairwise independent hash functions）。

原题

Implement the family of pairwise independent hash functions seen in the unit.

知识点

• universal hashing
• pairwise independence
• 模素数线性哈希
• rejection sampling
• 只用 random.getrandbits(k) 生成随机数

---

核心思路

课程里最标准的一族两两独立哈希函数是：

\[ h_{a,b}(x)=((ax+b) \bmod p) \bmod m \]

其中：

• \(p\) 是一个大于输入范围的素数
• \(a \in \{1,2,\dots,p-1\}\)
• \(b \in \{0,1,\dots,p-1\}\)
• \(m\) 是哈希值范围，比如桶的个数

随机选择 \(a,b\) 后，就得到一个具体的哈希函数 \(h_{a,b}\)。这一族函数满足 pairwise independence，也就是对任意不同的 \(x_1,x_2\)，它们的哈希值分布是成对独立的。

---

为什么这个构造可行

在模素数 \(p\) 的域上，映射

\[ x \mapsto ax+b \pmod p \]

是最经典的随机线性哈希构造。

对于任意不同的两个输入 \(x_1 \neq x_2\)，以及任意两个目标值 \(y_1,y_2\)，联立方程

\[ ax_1+b \equiv y_1 \pmod p \]

\[ ax_2+b \equiv y_2 \pmod p \]

有唯一解 \((a,b)\)。这意味着从所有可能的 \((a,b)\) 中均匀随机选取时，不同输入的像会呈现两两独立的分布。因此这就是课程里常见的 pairwise independent family。

---

实现时的关键点

题目特别限制，你的 Python 代码只能通过：

import random
random.getrandbits(k)

来产生随机性。所以不能直接用 random.randrange() 或 random.randint()。

因此标准做法是自己写一个 randbelow(n)，用 rejection sampling 从 \(\{0,1,\dots,n-1\}\) 中均匀采样。

randbelow(n) 的思路

1. 令 \(k = \text{bit\_length}(n-1)\)
2. 调用 random.getrandbits(k) 得到一个 \(k\) 位随机整数
3. 如果这个数小于 \(n\)，就接受
4. 否则丢弃，重新抽一次

这样可以保证采样是均匀的。

---

参考实现

import random

def randbelow(n):
    if n <= 0:
        raise ValueError("n must be positive")
    k = (n - 1).bit_length()
    while True:
        r = random.getrandbits(k)
        if r < n:
            return r

def make_pairwise_hash(m, p=2147483647):
    a = randbelow(p - 1) + 1   # 1..p-1
    b = randbelow(p)           # 0..p-1

    def h(x):
        return ((a * x + b) % p) % m

    return h

如果 Ed 的接口要求你返回参数而不是闭包，也可以保存 a,b,p,m，然后单独写一个 hash(x) 方法，思路完全一样。

---

代码含义解释

这里：

• a = randbelow(p - 1) + 1 保证 \(a \neq 0\)
• b = randbelow(p) 保证 \(b\) 在 \([0,p-1]\) 内均匀分布
• ((a * x + b) % p) % m 先在模 \(p\) 的域里做随机线性映射，再映射到目标范围 \(\{0,1,\dots,m-1\}\)

通常课程里要求你实现的，就是这个 family，而不是去重新证明它。

---

容易错的地方

1. 让 a = 0

如果 \(a=0\)，哈希函数就退化成常数平移，失去课程里要求的性质。所以必须保证 \(a \in \{1,\dots,p-1\}\)。

2. 直接对 getrandbits(k) 取模

如果写成：

random.getrandbits(k) % n

通常会引入偏差，不能保证均匀分布。正确方法是 rejection sampling。

3. 选的 \(p\) 不是素数

这个构造依赖模素数域的性质，所以 \(p\) 应该取素数。

4. 忘记根据题目限制控制随机数来源

如果作业明确要求只能用 random.getrandbits(k)，那就不要调用别的随机 API。

---

可以直接写进作业说明的简短版本

We use the standard pairwise independent family

\[ h_{a,b}(x)=((ax+b) \bmod p) \bmod m, \]

where \(p\) is prime, \(a \in \{1,\dots,p-1\}\), and \(b \in \{0,\dots,p-1\}\). Since the task only allows random.getrandbits(k), we implement a uniform randbelow(n) using rejection sampling, then sample \(a\) and \(b\) uniformly and return the resulting hash function.