My favourite small hash table
2 days ago
- #data-structures
- #hash-table
- #optimization
- The article discusses a specific hash table design using Robin Hood open-addressing with linear probing and power-of-two table size.
- Keys are 32-bit integers, and values are also 32-bit integers, allowing key/value pairs to be stored as 64-bit integers.
- The hash table structure includes slots (an array of 64-bit integers), a mask (table size minus one), and a count of non-empty slots.
- Lookup involves checking the natural position of the key and probing linearly if there are collisions, using a score function to determine termination.
- Insertion checks for existing keys and handles collisions by reinserting keys if necessary, with table expansion at a 75% load factor.
- Removal of keys involves shifting slots left until an empty slot or a slot with a score of zero is found, avoiding the need for tombstones.
- Iteration is straightforward, filtering out empty slots while traversing the array.
- The design can be extended for non-randomly distributed keys using an invertible hash function and for larger key/value pairs with separate storage.
- The article notes limitations, such as not being suitable for concurrent lock-free scenarios or when specific hardware instructions are required.