# Perfect hash function

(Redirected from Perfect hash)

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. 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

A minimal perfect hash function is a perfect hash function that maps $n$ keys to $n$ consecutive integers—usually $\{0\ldots n-1\}$ or $\{1\ldots 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, \ldots, 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 most effective 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 $a_1, a_2, \ldots, a_n$ and for any keys $a_j$ and $a_k$, $j.[4] Order-preserving minimal perfect hash functions require necessarily $\Omega(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. Monotone minimal perfect hash functions can be represented in very little space.[citation needed]

## 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. edit
2. ^ Belazzougui, D.; Botelho, F. C.; Dietzfelbinger, M. (2009). "Hash, Displace, and Compress". Algorithms - ESA 2009. Lecture Notes in Computer Science 5757. p. 682. doi:10.1007/978-3-642-04128-0_61. ISBN 978-3-642-04127-3. edit
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. edit