通用哈希与完美哈希：k-统一性和强k-统一性在算法设计中的应用

在算法与数据结构设计课程的2021/22学年的第三部分中，重点讲解了通用哈希（Universal Hashing）和完美哈希（Perfect Hashing）的概念。这部分课程的内容基于Mitzenmacher和Upfal的著作《概率与计算》第二版，第十五章第三节。 通用哈希函数家族是关键概念，它们假设之前的哈希函数是完全随机且独立的，即对于任意的k个不同的元素x1, x2, ..., xk，它们的哈希值h(x1), h(x2), ..., h(xk)应该是均匀且独立分布的。然而，在实际应用中，完全随机的哈希函数难以实现，因为它们需要存储大量的信息来保证每个输入映射到不同的输出，这在空间效率上并不理想。 为了克服这个问题，引入了k-universality的概念。当一个从大宇宙U（至少包含n个元素）到小宇宙V（大小为0到n-1的集合，通常用于构建哈希表）的哈希函数族H是k-universal时，对于任何k个不同的输入x1, x2, ..., xk，如果随机选择一个h属于H，那么同时满足h(x1)=h(x2)=...=h(xk)的概率不超过1/(k-1)n。例如，二元通用性（2-universality）意味着对于任意两个不同元素，哈希冲突的概率不大于1/n。 进一步提升的是强k-universality。同样在大宇宙U和小宇宙V之间，一个哈希函数族H被称为强k-universal，它确保了对于任意k个不同的输入，即使是最坏情况下，使得h(x1)=...=h(xk)的概率也是有限的，并且这个概率比k-universality的定义更严格。强k-universality提供了更强的碰撞抵抗特性，有助于减少哈希表的冲突，并保持查询效率。 在设计算法和数据结构时，理解并利用这些哈希原理至关重要，尤其是在处理大量数据或需要快速查找、插入操作的场景中。通用哈希和完美哈希技术被广泛应用于数据库索引、程序代码优化、数据压缩等领域，通过提供高效且近似无冲突的哈希机制，显著提高了程序的执行效率和空间利用率。