An ordered minimal perfect hashing scheme based upon Euler's theorem (Q1060014): Difference between revisions

A hashing function is a function h on a key set \(K=\{k_ 1,k_ 1,...,k_ n\}\) into the set \(\{\) 1,2,3,...,m\(\}\) of locations. A hashing function can hence be considered as a mapping of a given set of records into a set of addresses. If no collisions occur and the mapping is into unique addresses a single probe is sufficient to retrieve each record. Such a transformation is called a perfect hashing function. If the cardinality of the set of records is equal to the cardinality of the address space a perfect hashing function is called a minimal perfect hashing function. As such hashing functions avoid collisions of keys and do not waste memory locations their study is of considerable importance. The author proposes a hashing scheme based upon Fermat's number and Euler's theorem. This hashing function stores the records in order. Furthermore it is shown that the proposed hashing scheme is a minimal perfect hashing scheme.