Method and apparatus for finding a perfect hash function and making minimal hash table for a given set of keys

摘要

A representation used in a computer system to represent a set of data items that correspond to and are accessible by means of a set of keys. The representation includes an array of the data items and a bit string associated with the array. Each key is mapped onto a bit of the bit string by means of a hash function that is perfect for the set of keys. The mapped bit is set. The data item corresponding to the key has a position in the array that corresponds to the position of the bit for the key in the bit string. Methods for reading and writing the representation are disclosed as well as a technique based on the mod operation and a set of co-prime numbers for finding a perfect hash function for a given set of keys.