在 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$ 为一种全域哈希算法。