完美散列

对集合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值的优势。

请参阅
*Dynamic perfect hashing
*Pearson hashing
*Succinct data structure
*Universal hashing

索引
延伸内容
Richard J. Cichelli. Minimal Perfect Hash Functions Made Simple*, Communications of the ACM, Vol. 23, Number 1, January 1980.

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 11.5: Perfect hashing, pp. 245–249.
• Fabiano C. Botelho, Rasmus Pagh and Nivio Ziviani. [http://arxiv.org/pdf/cs/0702159 "Perfect Hashing for Data Management Applications"].
• Fabiano C. Botelho and Nivio Ziviani. [http://homepages.dcc.ufmg.br/~nivio/papers/cikm07.pdf "External perfect hashing for very large key sets"]. 16th ACM Conference on Information and Knowledge Management (CIKM07), Lisbon, Portugal, November 2007.
• Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna. [https://web.archive.org/web/20140125080021/http://vigna.dsi.unimi.it/ftp/papers/MonotoneMinimalPerfectHashing.pdf "Monotone minimal perfect hashing: Searching a sorted table with O(1) accesses"]. In Proceedings of the 20th Annual ACM-SIAM Symposium On Discrete Mathematics (SODA), New York, 2009. ACM Press.
• Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna. [https://web.archive.org/web/20121018172528/http://siam.org/proceedings/alenex/2009/alx09_013_belazzouguid.pdf "Theory and practise of monotone minimal perfect hashing"]. In Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 2009.
• Douglas C. Schmidt, [https://web.archive.org/web/20120725000244/http://www.cs.wustl.edu/%7Eschmidt/PDF/gperf.pdf GPERF: A Perfect Hash Function Generator], C++ Report, SIGS, Vol. 10, No. 10, November/December, 1998.

外部链接
*[http://burtleburtle.net/bob/hash/perfect.html Minimal Perfect Hashing] by Bob Jenkins
*[http://www.gnu.org/software/gperf/ gperf] is an Open Source C and C++ perfect hash generator
*[http://cmph.sourceforge.net/index.html cmph] is Open Source implementing many perfect hashing methods
*[http://sux.di.unimi.it/ Sux4J] is Open Source implementing perfect hashing, including monotone minimal perfect hashing in Java
*[https://web.archive.org/web/20130729211948/http://www.dupuis.me/node/9 MPHSharp] is Open Source implementing many perfect hashing methods in C#