Meetup #112: Robin Hood Hashing

Robin Hood hashing was introduced by Pedro Celis in his thesis in 1986

The idea is that entries are moved around based on how far they are from their initial buckets — the initial bucket being the bucket to which an entry is hashed. Robin Hood hashing takes buckets from entries that are closer to their initial buckets compared to the entries that need to be inserted.

In that way, it takes from the riches and gives to the poor, which is where the name “Robin Hood hashing” originates.

Whitepaper to read (pages 12-18): https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf

Optional:

• good summary article: http://codecapsule.com/2013/11/11/robin-hood-hashing/
  
• simple rationale article:https://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/
  

Lifeguard: Konrad `ktoso` Malawski