Closed Hashing (Open Addressing) Hash Map

This hash map implementation uses a closed hashing (open addressing) technique with linear probing for resolving any hash collisions. The exact algorithm it utilizes is called 'robin hood hashing.' More information about this can technique can be found in the links at the bottom.

Basic Idea Behind the Robin Hood Hashing Technique

1. Calculate the hash key value
2. Calculate the initial index of the entry to be inserted (using the hash key)

• If the index is empty, insert the entry
• Otherwise, start scanning linearly from the index found. Keep count and when
  you finally find a (close by) index to insert the entry into, store the count
  of the distance from the initial index/bucket. This is called the DIB.
• Note, the entry is always stored along with the DIB, even if it uses the first index found.

3. If we encounter an entry (at any point during step 2) which has a DIB less than
   the one of the entry to be inserted, swap them and continue.

To conclude, linear probing along with the storage of the DIB and algorithm that
ultimately ends up as Robin Hood Hashing works by improving the locality of
reference between all the entries resulting in a more stable average between them.

For more information about closed hashing (and robin hood hashing in particular)

• Robin Hood Hashing
• Robin Hood Hashing, Pedro Celis, 1986
• Distributional Analysis of Robin Hood Linear Probing Hashing with Buckets
• Numerical Experiments in Hashing, Part 1
• Numerical Experiments in Hashing, Part 2
• Robin Hood Hashing Should be Your Default Hash Table Implementation
• More On Robin Hood Hashing
• Robin Hood Hashing, Part 1
• Robin Hood Hashing (Backwards Shift Deletion), Part 2
• The Other Robin Hood Hashing