### MIT麻省理工算法课程-第八节-讲义(经典！)
#### Universal Hashing与Perfect Hashing
在本节MIT的算法课程中，主要探讨了两种重要的哈希技术：Universal Hashing（通用哈希）与Perfect Hashing（完美哈希）。这两种哈希技术在解决数据结构中的冲突问题上具有非常重要的作用。
##### Universal Hashing
**定义**：设\(U\)为一个关键字的集合（即关键字宇宙），\(H\)为一组有限的哈希函数集合，每个函数都将\(U\)映射到\(\{0,1,...,m-1\}\)。我们称\(H\)是通用的，如果对于所有的\(x,y \in U\)（其中\(x \neq y\)），满足\(|\{h \in H : h(x) = h(y)\}| = |H|/m\)。也就是说，如果从\(H\)中随机选择一个哈希函数\(h\)，那么\(x\)和\(y\)发生冲突的概率为\(1/m\)。
**优点**：
- **降低冲突概率**：通过选择合适的通用哈希函数集，可以大大降低冲突的可能性。
- **对抗性攻击防御**：即使攻击者知道哈希函数的选择机制，由于每次运行时选择的哈希函数都是随机的，因此很难找到能够造成冲突的关键字集合。
**应用场景**：
- 数据库索引
- 缓存管理
- 字符串匹配
**构造通用哈希函数**：
- **多项式哈希函数**：选择一个素数\(p\)以及一个随机数\(a \in [1,p-1]\)，则哈希函数可表示为\(h_k(x) = ((\sum_{i=0}^{|k|} x_i * a^i) \mod p) \mod m\)，其中\(x_i\)为关键字\(x\)的第\(i\)位。
- **线性组合哈希函数**：假设\(H\)为一组函数，每个函数将\(U\)映射到\([m]\)，则可以通过线性组合这些函数来构建新的哈希函数。
##### Universality Theorem
**定理**：设\(h\)是从通用哈希函数集\(H\)中均匀随机选取的一个哈希函数，如果用\(h\)对\(n\)个任意关键字进行哈希处理，并放入含有\(m\)个槽的哈希表\(T\)中，则对于给定的关键字\(x\)，其平均冲突次数小于\(n/m\)。
**证明**：
1. **定义随机变量**：设\(C_x\)为关键字\(x\)与其他关键字在表\(T\)中发生冲突的总次数，对于每个\(y \in T\)且\(y \neq x\)，定义一个指示变量\(c_{xy}\)：
- 如果\(h(x) = h(y)\)，则\(c_{xy} = 1\)；
- 否则，\(c_{xy} = 0\)。
2. **计算期望**：由于\(H\)是通用的，所以对于每个\(y \in T\)，有\(E[c_{xy}] = 1/m\)。因此，
\[ E[C_x] = E[\sum_{y \in T \backslash \{x\}} c_{xy}] = \sum_{y \in T \backslash \{x\}} E[c_{xy}] = \sum_{y \in T \backslash \{x\}} (1/m) = (n-1)/m < n/m \]
##### Constructing a Set of Universal Hash Functions
- **构造方法**：构造一个通用哈希函数集的关键在于找到一种方式，使得任何两个不同的键值通过该集合中的哈希函数映射后发生冲突的概率足够低。
- **示例**：多项式哈希函数和线性组合哈希函数是两种常用的构造方法。
##### Perfect Hashing
**定义**：完美哈希是一种特殊的哈希技术，它能够在最坏的情况下实现\(O(1)\)的时间复杂度查找操作。这种哈希函数设计通常包含两层哈希过程：第一层用于将关键字映射到较小的哈希表中；第二层用于解决第一层哈希过程中产生的冲突。
**特点**：
- **无冲突**：第二层哈希函数确保了在第二层哈希表中没有冲突。
- **空间效率**：虽然完美哈希可能需要额外的空间来存储第二层哈希表，但总体上它的空间效率较高。
- **动态更新**：虽然静态完美哈希可以轻松实现，但动态完美哈希（即支持插入和删除操作）的实现较为复杂。
**应用场景**：
- 字典编纂
- 数据库系统中的主键索引
- 编译器符号表
通过学习本节的内容，我们可以了解到通用哈希和完美哈希在解决实际问题中的应用价值。它们不仅提高了哈希表的性能，还为我们提供了更强大的工具来处理大规模数据集。
