Minimal perfect hash functions using double hashing
US8271500B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Sep 11, 2007 |
| Grant date | Sep 18, 2012 |
| Priority date | — |
| Expiry date | Jan 13, 2030 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L2209/043
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.