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.

Properties and uses

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] 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. This is because any modification of the set leads to a non-perfect hash function. Solutions which update the hash function any time the set is modified 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

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 proven that a general purpose minimal perfect hash scheme requires at least 1.44 bits/key.[2] The best currently known minimal perfect hashing schemes use around 2.6 bits/key.[3]

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).[4] Order-preserving minimal perfect hash functions require necessarily Ω(n log n) bits to be represented.[5]

A minimal perfect hash function F is monotone if it preserves the lexicographical order of the keys. In this case, the function value is just the position of each key in the sorted ordering of all of the keys. If the keys to be hashed are themselves stored in a sorted array, it is possible to store a small number of additional bits per key in a data structure that can be used to compute hash values quickly.[6]

See also

References

  1. ↑ Fredman, M. L.; Komlós, J. N.; Szemerédi, E. (1984). "Storing a Sparse Table with 0(1) Worst Case Access Time". Journal of the ACM 31 (3): 538. doi:10.1145/828.1884.
  2. ↑ Belazzougui, D.; Botelho, F. C.; Dietzfelbinger, M. (2009). "Hash, Displace, and Compress". Algorithms - ESA 2009 (PDF). LNCS 5757. p. 682. doi:10.1007/978-3-642-04128-0_61. ISBN 978-3-642-04127-3.
  3. ↑ Baeza-Yates, Ricardo; Poblete, Patricio V. (2010), "Searching", in Atallah, Mikhail J.; Blanton, Marina, Algorithms and Theory of Computation Handbook: General Concepts and Techniques (2nd ed.), CRC Press, ISBN 9781584888239. See in particular p. 2-10.
  4. ↑ 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
  5. ↑ 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 - SIGIR '90. p. 279. doi:10.1145/96749.98233. ISBN 0897914082.
  6. ↑ Belazzougui, Djamal; Boldi, Paolo; Pagh, Rasmus; Vigna, Sebastiano (November 2008), "Theory and practice of monotone minimal perfect hashing", Journal of Experimental Algorithmics 16, Art. no. 3.2, 26pp, doi:10.1145/1963190.2025378.

Further reading

External links

This article is issued from Wikipedia - version of the Monday, March 07, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.