Perfect hash function

Perfect hash functions are hash functions which guarantee O(1) operations complexity when used in a hash table. In other words, a hash table that uses a perfect hash function guarantees that retrieving any value will take no more than some constant time, regardless of the table's size. This is opposed to a general hash function, which may, in some conditions, require a number of look-ups that is proportional to the table's size - O(n) operations.

A specific perfect hash function may achieve this operation complexity constraint by guaranteeing that for a certain list of keys (see hash table), no two keys get the same hash value. A more general way of putting this: if C is a some constant number, then no more than C keys may generate the same hash value, using this function.

Coming up with a perfect hash function for a specific data set takes in the order of O(n) operations (i.e. a number of operations that is proportional to the data-set's size);

Using a perfect hash function is best at situations where there is a large dataset which is not updated frequently, and many look-ups into it. This is because updates may require re-calculation of the perfect hash.

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

See also

• hash table
• hash function