MINIMAL PERFECT HASH FUNCTIONS USING DOUBLE HASHING

摘要

Technologies are described herein for constructing a minimal perfect hash function. According to embodiments, a hash table is constructed by double hashing each of the strings in a set of strings. A computed double hash value is utilized to identify an empty location in the hash table for each string. A signature for each string is stored in the empty location of the hash table identified for the string. In order to obtain a minimal perfect hash value for an input string, the input string is iteratively double hashed until a location is identified in the hash table that contains a signature corresponding to the input string. The minimal perfect hash value is an integer value identifying the location in the hash table that contains the signature corresponding to the input string.