Amazon.com, Inc.
Optimizing hash table searching using bitmasks and linear probing

Abstract:

Within hash tables, bitmask(s) may be used to determine whether a given key is part of a collision chain or otherwise contained within the hash table. In some instances, using bitmask(s) may avoid linearly probing an entirety of the collision chain. For example, bitmask(s) may be used when searching low hit rate hash tables or hash tables where misses predominantly occur. Upon locating a collision chain within the hash table, or when probing the collision chain, the bitmask(s) may indicate whether subsequent keys within the collision chain correspond to the given key. The bitmask(s) may represent subsequent keys within the collision chain, and therefore, comparing the given key with the bitmask(s) may indicate similarities therebetween for use in determining whether to search a remainder of the collision chain.