对集合S的完美散列函数是一个将S的每个元素映射到一系列无冲突的整数的哈希函数。一个完美散列函数的应用与其他哈希函数的应用基本一致，但不需要任何冲突解决方案。在数学术语中，这是一个完全单射函数.
特性及使用
对于特定集合S的完美散列函数能在常数时间中被计算出，其映射值在一个相对小的范围内，能被一个随机化算法发现，该算法的操作次数与S的大小成正比.任何适合在哈希表中使用的完美散列函数需要至少与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是一个最小完美散列函数iff F(j)=F(k)只在j=k的情况下成立(单射)；并且存在整数a，使得F的范围为a..a+|K|−1。已经在数学上证明，通用的完美hash函数至少需要每个键（key）1.44 比特（bit） 。而当前已知的最小完美hash散列函数每个键需要2.6 比特。
对一个最小完美散列函数F，若键以a1, a2, ..., an次序给出，对任意键aj and ak, j<k，意味着F(aj)<F(ak). Order-preserving minimal perfect hash functions require necessarily Ω(n log n) bits to be represented.，我们称该最小完美散列函数F是保序的。
若对一个最小完美散列函数F，其应用变换后得到的值保持了键（key）的字典序，我们称该最小完美散列函数F为单调的。在此情况下，函数产生的值就是输入的键在所有可能的有序键序列中的位置。若被hash的键被存储于有序数组中，已实现一种策略，对每个键存储少量附加位（bits），以取得更快计算hash值的优势。
原文地址：
https://zh.wikipedia.org/wiki/%E5%AE%8C%E7%BE%8E%E6%95%A3%E5%88%97
在知识共享 署名-相同方式共享 3.0协议之条款下提供
