Robin Hood Hash Displacement
Move crowded keys aside by comparing their probe distances.
By Riano · Published · Updated · Report a correction
Robin Hood Hash Displacement
Robin Hood hashing is a variation of open addressing with linear probing that aims to reduce the maximum search time by distributing displacement more fairly among elements.
Worked Example
Let's examine how the "Clusters" keys array
[0, 1, 2, 7, 14]are inserted sequentially into a hash table of capacity 7. The hash function is
h(k) = k mod 7.
- Insert 0: hash is 0. Bucket 0 is empty. Inserted at bucket 0 with displacement 0.
- Insert 1: hash is 1. Bucket 1 is empty. Inserted at bucket 1 with displacement 0.
- Insert 2: hash is 2. Bucket 2 is empty. Inserted at bucket 2 with displacement 0.
- Insert 7: hash is 0. Bucket 0 is occupied by 0 (displacement 0). The new key's current displacement is 0. Since 0 is not STRICTLY greater than 0, it does not displace 0. It probes to bucket 1. Bucket 1 is occupied by 1 (displacement 0). New key's displacement is 1. Since 1 > 0, it displaces 1! Key 7 now occupies bucket 1. The displaced key 1 (with displacement 0 now becoming 1) probes to bucket 2. Bucket 2 is occupied by 2 (displacement 0). Displaced key 1 has displacement 1, which is > 0, so it displaces 2! Key 1 now occupies bucket 2. The displaced key 2 (with displacement 0 now becoming 1) probes to bucket 3. Bucket 3 is empty, so it settles there.
- Insert 14: hash is 0. Bucket 0 is occupied by 0 (displacement 0). New key's displacement is 0, so it probes to bucket 1. Bucket 1 is occupied by 7 (displacement 1). New key's displacement is 1, so it probes to bucket 2. Bucket 2 is occupied by 1 (displacement 1). New key's displacement is 2, which is > 1! It displaces 1. Key 14 now occupies bucket 2. The displaced key 1 (with displacement 1 now becoming 2) probes to bucket 3. Bucket 3 is occupied by 2 (displacement 1). Displaced key 1 has displacement 2, which is > 1! It displaces 2. Key 1 now occupies bucket 3. The displaced key 2 (with displacement 1 now becoming 2) probes to bucket 4. Bucket 4 is empty, so it settles there.
The final table contents physically in order are: 0, 7, 14, 1, 2, _, _. Displacements are: 0, 1, 2, 2, 2, _, _.
Experiment
You can interact with the Robin Hood Hash Displacement module.
- Set Keys to
Wrap. - Set Capacity to
7. - Set Query key to
-1.
Observe the physical array layout mapping. The negative key -1 evaluates to ((-1 mod 7) + 7) mod 7 = 6.
Limitations
This visualization operates on small capacities (up to 7 buckets) for instructional clarity. Real world implementations scale dynamically using load factors. The algorithm visualised here uses a fixed capacity, meaning it will reject keys when the table is full rather than dynamically allocating memory to expand and rehash the elements. The standard approach requires resizing the table well before it reaches 100% capacity to maintain O(1) expected time complexity. Furthermore, this implementation does not handle deletion which would typically require tombstone markers or backward-shifting elements (which Robin Hood Hashing uniquely supports well) to maintain probe chains.
References
For more information, please check the formal references:
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Robin Hood Hash Displacement module.
Try Robin Hood Hash Displacement on Riano →