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, due to hash collisions.
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).