# Perfect hash function

(Redirected from Perfect Hashing)

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]