Patent Document ID: 8271500
Application ID: 11853635
Patent Status: 1

Claim One:
1. A method for obtaining a minimal perfect hash value for an input string using double hashing, the method comprising: constructing, utilizing a computer, a hash table by double hashing each string in a set of strings; identifying, utilizing the computer, a location in the hash table for each string using a hash value computed by a first universal hash function ; determining, utilizing the computer, if the location in the hash table for each string is empty; in response to determining that the location in the hash table identified by the hash value for a string is not empty, combining, utilizing the computer, the hash value identifying the location in the hash table with a new hash value computed by a second universal hash function to identify a new location in the hash table for potentially storing a signature for the string; in response to determining that the location in the hash table identified by the hash value is empty or in response to determining that the new location in the hash table identified by the new hash value is empty, computing, utilizing the computer, a signature for the string by a third universal hash function, and storing the signature for the string in the location or the new location of the hash table, respectively, based upon the determination; following construction of the hash table, determining, utilizing the computer, whether the hash table contains intersecting lookup paths for different strings that have identical signatures; in response to determining that the hash table contains intersecting lookup paths for different strings having identical signatures, selecting, utilizing the computer, a new first universal hash function, selecting a new second universal hash function, and constructing a new hash table by double hashing each string of the string in the set of strings using the new first universal hash function and the new second universal hash function; and obtaining the minimal perfect hash value for the input string by iteratively double hashing the input string until a location is identified in the hash table that contains the signature corresponding to the input string, the minimal perfect hash value comprising an integer identifying the location in the hash table that contains the signature corresponding to the input string.