浅谈现代哈希设计

尽管 lecture 里面其实介绍了非常现代的哈希表设计思想，但我在这里应该只会介绍一些基本的内容，主要包括 Universal Hashing 、Perfect Hashing ，以及可能的 Succinct Dictionary 。

FKS Perfect Hashing

• 现在我们先要介绍一些基本的现代哈希设计思想。

问题建模

• 考虑这样的问题，对于全集 ，我们要将其中的 个元素（构成集合 ）通过某一哈希函数 映射到 上。我们有一个大小为 的表 ，对于 ，我们将 填入 上的 这一位置。我们希望支持查询操作 ，其检查是否 ，即 是否位于表 中。特别的，若存在 使得 ，我们称发生了哈希碰撞。

  此处我们认为集合 是预先给定的，这被称为静态哈希。

Universal Hashing

• 我们先要介绍 Universal Hashing 这个概念。不妨想想基本的 Hash 有什么坏处：以散列表为例，其为确定性的算法，可以被精心构造的数据卡到 的查询复杂度下界。所以为了对抗外部的攻击，我们考虑引入随机化，从而保证操作复杂度以极高的概率位于可接受的范围。 具体的，对于一族哈希函数 ，我们称其为 k-Universal Hash Family ，当且仅当对于任意不同的 使得 ，从 中均匀随机的取出一个哈希函数 ，有：

  即我们期待每个元素的映射都是独立随机的。如果把这个性质更严格的表述出来，就得到了 strongly k-universal 的定义，即对于任意不同的 与可以相同的 使得 ，均有：

• 一个有趣且常用的结论是，任意有限域上 次多项式构成的函数族就恰好是 strongly k-universal 的。这其实是一个简单的结果，只需考察范德蒙德矩阵的可逆性即可。¹

FKS Perfect Hashing

• Perfect Hashing 是指不存在碰撞的静态哈希。最早实现的 Perfect Hashing 之一就是 FKS 方法，其为一个两层的哈希，在第一层通过 2-universal hashing² 进行分桶，然后在第二层直接使用 2-universal hashing 。具体的，现在我们希望将 个元素通过哈希函数 映射到 个桶中，然后在第 个桶里直接通过 进行映射。我们的目的是安排每个哈希函数的值域大小，使得在存在完美哈希的情况下总空间开销尽可能小。

  FKS 的设计思想来自生日悖论，形式化的描述是，对于总共的 个元素与 个桶，我们为每个元素均匀随机的选择一个桶，那么当 时，以常数概率每个元素都会位于不同的桶中。³因此若第 个桶中具备 个元素，我们就令 的值域为 。

  考察第一层哈希的碰撞次数的期望，其为： 其可以使用桶的大小来表达： 从而第一层和第二层的总期望查找表大小为： 令 时，查找表大小即为 。而因为哈希函数是在离散空间中均匀随机选取的，由概率方法，必然存在对 的选法使得以上方法的总空间开销不超过 。现在我们考察第二层哈希，对于 ，显然其存在哈希碰撞的期望恰为： 从而由概率方法，必然存在对于 的选取方式使得此处不存在哈希碰撞。这样，我们就证明了对于任意的 个元素，必然存在仅需 大小查找表（即 空间，因为还需存储键本身和哈希函数）的完美哈希，并且查询时间复杂度为 。

Succinct Dictionary

• 懒得写。

---

1. 这应该可以从实数域上的线性空间推广到有限域上。说到底，这部分结论应该是只依赖于域的基本性质的，验证应该不难。↩︎

2. 使用线性同余实现即可。↩︎

3. 自证不难。↩︎