[科普中国]-完美散列

对集合S的完美散列函数 是一个将S的每个元素映射到一系列无冲突的整数的 哈希函数。一个完美散列函数的应用与其他哈希函数的应用基本一致，但不需要任何冲突解决方案。在数学术语中，这是一个完全单射函数。

特性及使用对于特定集合S的完美散列函数能在常数时间中被计算出，其映射值在一个相对小的范围内，能被一个随机化算法发现，该算法的操作次数与S的大小成正比1。任何适合在哈希表中使用的完美散列函数需要至少与S的大小成正比的位数。

一个值的位数被限定范围的完美散列函数能应用于高效查找操作中：假定查找键(key)与集合S（或与集合S关联的值）对应，然后将完美散列函数应用于查找键，得到哈希值（一个整数），然后在查找表中取出该整数对应的值。在集合S极少更新且查询频率非常多的情况下，使用完美hash函数是非常有效的。对集合S更新频率的限定是由于对任何集合S的修改，都将导致该完美散列函数退化为非完美散列函数。每次集合S被修改后自动更新hash函数的解决方案被称为dynamic perfect hashing，但这类方法非常复杂，难以实现。一个简单的允许动态更新集合S的完美散列函数的替代品叫cuckoo hashing。

最小完美散列函数最小完美散列函数是一个能将n个键（key）映射到n个连续的整数的完美散列函数。 产生的值通常为 [0..n−1] 或 [1..n]。正式表述如下：设j和k是有限集合K的两个元素。F是一个最小完美散列函数 只在j=k的情况下成立(单射)；并且存在整数a，使得F的范围为a~a+|K|−1。已经在数学上证明，通用的完美hash函数至少需要每个键（key）1.44 比特（bit）。而当前已知的最小完美hash散列函数每个键需要2.6 比特。

对一个最小完美散列函数F，若键以a1,a2, ...,an次序给出，对任意键和，意味着 。我们称该最小完美散列函数F是保序的。

若对一个最小完美散列函数F，其应用变换后得到的值保持了键（key）的字典序，我们称该最小完美散列函数F为单调的。在此情况下，函数产生的值就是输入的键在所有可能的有序键序列中的位置。若被hash的键被存储于有序数组中，已实现一种策略，对每个键存储少量附加位（bits），以取得更快计算hash值的优势。

本词条内容贡献者为:

王慧维 - 副研究员 - 西南大学