Meta Platforms, Inc.
Co-prime hashing

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.