Co-prime hashing
US10725990B2 · kind B2 · utility
Assignee
Inventor
Key dates
| Filing date | Dec 1, 2015 |
| Grant date | Jul 28, 2020 |
| Priority date | — |
| Expiry date | Aug 14, 2038 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/9014
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A hashing system can use a set of multiple numbers that are co-prime to the size of a hash table to select a probe offset when collisions occur. Selecting a probe offset that is co-prime to the hash table size ensures that each hash table slot is available for any insert operation. Utilizing different co-prime numbers for different keys helps avoid clustering of items inserted into the hash table. When a collision occurs, the hashing system can compute a next index to check by selecting a probe offset that is located at a computed index on a list of numbers that are each co-prime to the number of slots in the hash table. The hashing system can compute the index into the list of numbers by applying a hash function to the data item and calculating a modulus of the result with respect to a count of the co-prime numbers list.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.