There is a very interesting hashing approach called Robin Hood Hashing. It is one of those ideas that is both simple and elegant. Hear me out…
In standard open-addressing hash tables, when a collision happens, you move forward to find an open slot. The problem is that some keys end up very close to their ideal slot, while others get placed far away.
This creates long probe sequences for unlucky keys, and this degrades lookup performance.
Robin Hood Hashing fixes this with a very small change in the insertion strategy. When inserting a new key, if it is farther from its ideal slot than the key it is displacing, it takes the spot, and the displaced key continues probing.
So, essentially, you are stealing from the ‘rich’ (keys sitting comfortably near home) and giving to the ‘poor’ (keys that have drifted far). Hence the name, Robin Hood.
The result is that the variance in probe length across all keys stays very low. No key gets left too far behind.
This algorithm can be found in Rust’s standard HashMap implementation, in several high-performance database indexes, and in memory systems where cache efficiency matters. It’s also popular in hash tables where you need consistent lookup time, not just a good average case.
It doesn’t change the worst case on paper, but in practice, it brings the distribution of keys closer to the ideal slot, and lookups are noticeably faster for dense tables.
It is pretty interesting that one small rule change at insert time has such a high impact on the overall performance of the hash table.
Hope this helps.