全域哈希推导

在 CLRS 上看到了 Chapter 12，讲解了 Hash 相关的内容，其中关于全域哈希（universal hash）和完美哈希（perfect hash）看的不是很懂。后来补了 MIT 的算法导论公开课，稍微弄懂了一些。这里做一个关于全域哈希简单的推导，加强记忆。

普通哈希函数的缺陷

对于一个给定的哈希函数 $h$ ，存在着一个明显的缺陷：我们总能找到一套特殊的 keys $K$，使得 $K$ 中的 $\forall k \in K$，其 $h(k)$ 均相等。这样的哈希函数的会导致哈希后的结果回退成一个链表，搜索操作将会是 $O(n)$ 的时间复杂度。

这样的后果就是，在应用当中你的哈希函数可能会被针对，导致整个算法的效率下降。

解决方案：全域哈希

为了解决普通哈希函数的这个缺陷，我们引入了全域哈希算法：即在映射时，我们可以从一个哈希函数集合中，随机地选择哈希函数，当选择函数足够随机时，我们可以保证两个不同的 key 落入同一个桶中，即计算 $h(key)$ 结果相同的概率很低。这个值多低呢？可以小于 $\frac{1}{m}$，$m$ 为桶的个数。

全域哈希的正式定义是：

给定 keys 的集合 $U$，哈希函数的集合 $H$，对于 $\forall x,y \in U$，$x \neq y$，$x, y$ 碰撞的概率小于 $\frac{|H|}{m}$，即在 $H$ 中任意选择一个函数，计算 $h(x) = h(y)$ 的概率小于 $\frac{1}{m}$，那么集合 $H$ 为一种全域哈希算法。

可行的全域哈希

定义全域哈希的方法不唯一，这里提供一个 CLRS 上的方法：

$$
H_{pm} = (h_{a,b}(x) = (ax+b) \ mod \ p) \ mod \ m, 1 \leq a \leq p-1, 0 \leq b \leq p-1
$$

这是一种可行的全域哈希算法，其中 $p$ 是一个比任何 key 都大的质数。

证明

首先我们设 $l, k \in U$，且不失一般性 $k > l$，此时对于 $h_{ab} \in H_{pm}$，会使 $h_{ab}(k) = h_{ab}(l)$。首先我们需要分析是哪一步计算可能导致了相等，即冲突的发生。

冲突的原因

显然，因为 $k > l$，所以不可能是 $ak+b$ 与 $al+b$ 相等。那么剩下的可能只有两处，$mod \ p$ 和 $mod \ m$。

设 $r = (ak+b) \ mod \ p, s = (al+b) \ mod \ p$。假设是在计算了 $mod \ p$ 之后导致了相等，那么 $r = s$，$r - s = 0$，最终就会得到如下的式子：

$$
a(k-l) \ mod \ p = 0
$$

因为 $a \neq 0$，而 $k > l$ 所以也不可能为 0，那么上面的式子不成立，也就不是 $mod \ p$ 导致了相等。而是 $mod \ m$。

(r, s) 和 (a, b) 一一对应

证明这一步的原因是， $(a, b)$ 对实际上是定义了从哈希函数集合 $H$ 中随机选出的一个哈希函数，而前面我们证明了 $(r, s)$ 在求了 $mod \ m$ 后导致了相等，即冲突。那么如果我们能够得到随机选择一组 $(r, s)$ 在求了 $mod \ m$ 后导致了哈希值相等的概率小于 $\frac{1}{m}$，我们也就证明了在 $H$ 中任意选择一个函数，计算 $h(x) = h(y)$ 的概率小于 $\frac{1}{m}$，说明 $H$ 是一个全域哈希集合。

根据

$$
r = (ak+b) \ mod \ p
$$

$$
s = (al+b) \ mod \ p
$$

我们可以得到

$$
a = ((r-s)((k-l)^{-1} \ mod \ p)) \ mod \ p
$$

$$
b = (r - ak) \ mod \ p
$$

因为 $r \neq s$，而 $p$ 比任何 key 都大，我们可以认为 $(r, s)$ 有 $p(p-1)$ 种取法。