Perfect hash function
A perfect hash function for a set S is a hash function that maps distinct elements in S to a set of integers, with no collisions. A perfect hash function has many of the same applications as other hash functions, but with the advantage that no collision resolution has to be implemented. In mathematical terms, it is a total injective function.
Contents |
Properties and uses [edit]
A perfect hash function for a specific set S that can be evaluated in constant time, and with values in a small range, can be found by a randomized algorithm in a number of operations that is proportional to the size of S.[1] The minimal size of the description of a perfect hash function depends on the range of its function values: The smaller the range, the more space is required[citation needed]. Any perfect hash functions suitable for use with a hash table require at least a number of bits that is proportional to the size of S.
A perfect hash function with values in a limited range can be used for efficient lookup operations, by placing keys from S (or other associated values) in a table indexed by the output of the function. Using a perfect hash function is best in situations where there is a frequently queried large set, S, which is seldom updated. Efficient solutions to performing updates are known as dynamic perfect hashing, but these methods are relatively complicated to implement. A simple alternative to perfect hashing, which also allows dynamic updates, is cuckoo hashing.
Minimal perfect hash function [edit]
A minimal perfect hash function is a perfect hash function that maps n keys to n consecutive integers—usually [0..n−1] or [1..n]. A more formal way of expressing this is: Let j and k be elements of some finite set K. F is a minimal perfect hash function iff F(j) =F(k) implies j=k (injectivity) and there exists an integer a such that the range of F is a..a+|K|−1. It has been proved that a general purpose minimal perfect hash scheme requires at least 1.44 bits/key.[2] However the smallest currently use around 2.5 bits/key.[citation needed]
A minimal perfect hash function F is order preserving if keys are given in some order a1, a2, ..., an and for any keys aj and ak, j<k implies F(aj)<F(ak).[3] Order-preserving minimal perfect hash functions require necessarily Ω(n log n) bits to be represented.[4]
A minimal perfect hash function F is monotone if it preserves the lexicographical order of the keys. Monotone minimal perfect hash functions can be represented in very little space.
See also [edit]
References [edit]
- ^ Fredman, M. L., Komlós, J., and Szemerédi, E. 1984. Storing a Sparse Table with 0(1) Worst Case Access Time. J. ACM 31, 3 (Jun. 1984), 538-544 http://portal.acm.org/citation.cfm?id=1884#
- ^ Djamal Belazzougui, Fabiano C. Botelho, Martin Dietzfelbinger (2009). Hash, displace, and compress (PDF). Springer Berlin / Heidelberg. Retrieved 2011-08-11.
- ^ Jenkins, Bob (14 April 2009), "order-preserving minimal perfect hashing", in Black, Paul E., Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology, retrieved 2013-03-05
- ^ Fox, E. A.; Chen, Q. F.; Daoud, A. M.; Heath, L. S. (1990). "Order preserving minimal perfect hash functions and information retrieval". Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval (ACM): 279–311. doi:10.1145/96749.98233. ISBN 0-89791-408-2.
Further reading [edit]
- 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. "Perfect Hashing for Data Management Applications".
- Fabiano C. Botelho and Nivio Ziviani. "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. "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. "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, GPERF: A Perfect Hash Function Generator, C++ Report, SIGS, Vol. 10, No. 10, November/December, 1998.
External links [edit]
- Minimal Perfect Hashing by Bob Jenkins
- gperf is an Open Source C and C++ perfect hash generator
- cmph is Open Source implementing many perfect hashing methods
- Sux4J is Open Source implementing perfect hashing, including monotone minimal perfect hashing in Java
- MPHSharp is Open Source implementing many perfect hashing methods in C#
