Finding minimal perfect hash functions

Reviewer: Herman Peter Hoplin

This paper gives a heuristic for finding minimal perfect hash functions without extensive searching. The authors report that good results have been obtained for dictionaries of up to 181 words and, by using the same techniques, this can be extended for sets of up to 667 words. According to the paper, a minimal perfect hashing function can be defined as a one-to-one in mapping from a set of keys K to n consecutive integers. The paper presents a method for quickly finding hash functions for sets of up to 180 words. The authors point out that the same techniques can be applied to larger sets to find perfect hash functions. The content of the paper alludes to the practical limits of perfect hash functions when it comes to address computation of larger files. One approach to addressing records is a hashing scheme, which involves a mathematical operation where the result can be used as the address (i.e., the division/remainder method). The problem comes when the generated address is not unique, which, in turn, causes collisions and leads to resulting addresses referred to as synonyms. These conflicts then have to be resolved. But even then, they should be minimized to maintain the integrity of the hashing scheme. This phenomenon results from the use of a relatively black address, such as the use of the last five digits in a social security number where there are duplicates in larger populations. Ths short paper is useful for readers who are concerned with hash functions, hashing schemes, and the use of the technique as addresses or file retrieval methods. The paper has both a research and a practitioner value, in that the technique could be more useful if simple optimal methods could be devised and applied to larger files such as databases. For academic purposes, it likewise exposes a challenge toward finding minimal perfect functions that, if simple, would have broad practical applications. The paper whets the appetite of professionals and users, and is a worthwhile consideration for extending the value of hashing to the field.