In computer science, a perfect hash function h for a set S is a hash function that maps distinct elements in S to a set of m integers, with no collisions. In mathematical terms, it is an injective function. Perfect hash functions may be used to implement a lookup table with constant worst-case access time. A perfect hash function can, as any hash function, be used to implement hash tables, with the advantage that no collision resolution has to be implemented. In addition, if the keys are not in the data and if it is known that queried keys will be valid, then the keys do not need to be stored in the lookup table, saving space. Disadvantages of perfect hash functions are that S needs to be known for the construction of the perfect hash function. Non-dynamic perfect hash functions need to be re-constructed if S changes. For frequently changing S dynamic perfect hash functions may be used at the cost of additional space. The space requirement to store the perfect hash function is in O(n) where n is the number of keys in the structure. The important performance parameters for perfect hash functions are the evaluation time, which should be constant, the construction time, and the representation size.
Application 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 lookup table indexed by the output of the function. One can then test whether a key is present in S, or look up a value associated with that key, by looking for it at its cell of the table. Each such lookup takes constant time in the worst case. With perfect hashing, the associated data can be read or written with a single access to the table.
Performance of perfect hash functions The important performance parameters for perfect hashing are the representation size, the evaluation time, the construction time, and additionally the range requirement m n {\displaystyle {\frac {m}{n}}} (average number of buckets per key in the hash table). The evaluation time can be as fast as O(1), which is optimal. The construction time needs to be at least O(n), because each element in S needs to be considered, and S contains n elements. This lower bound can be achieved in practice. The lower bound for the representation size depends on m and n. Let m = (1+ε) n and h a perfect hash function. A good approximation for the lower bound is log e − ε log 1 + ε ε {\displaystyle \log e-\varepsilon \log {\frac {1+\varepsilon }{\varepsilon }}} Bits per element. For minimal perfect hashing, ε = 0, the lower bound is log e ≈ 1.44 bits per element.
Construction 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. The original construction of Fredman, Komlós & Szemerédi (1984) uses a two-level scheme to map a set S of n elements to a range of O(n) indices, and then map each index to a range of hash values. The first level of their construction chooses a large prime p (larger than the size of the universe from which S is drawn), and a parameter k, and maps each element x of S to the index
g ( x ) = ( k x mod p ) mod n . {\displaystyle g(x)=(kx{\bmod {p}}){\bmod {n}}.}
… excerpt ends here. Continue reading the full article.
