Perfect hash function
From Wikipedia, the free encyclopedia
A Perfect hash function of a set S is a hash function which maps different keys (elements) in S to different numbers. A perfect hash function with values in a range of size some constant times the number of elements in S can be used for efficient lookup operations, by placing the keys in a hash table according to the values of the perfect hash function.
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. 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. 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. Many common implementations require a number of bits that is proportional to n log(n), where n is the size of S. This means that the space for storing the perfect hash function can be comparable to the space for storing the set.
Using a perfect hash function is best in situations where there is a large set which is not updated frequently, and many lookups into it. 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.
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 set K. F is a minimal perfect hash function iff F(j) =F(k) implies j=k and there exists an integer a such that the range of F is a..a+|K|-1.
A minimal perfect hash function F is order-preserving if for any keys j and k, j<k implies F(j)<F(k).
[edit] See also
[edit] References
- 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 [1].
- 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 [2].
[edit] External links
- Minimal Perfect Hashing by Bob Jenkins
- gperf is a Free software C and C++ perfect hash generator
- cmph is another Free Software implementing many perfect hashing methods
