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

Perfect Hash Function

See also