carrotsearch/hppc — pull request #3 by moonpolysoft (2014-04-20 03:14:50+00:00)
Title: Robin Hood Hashing

I implemented robin hood hashing using the existing open hash map and the algorithm discussed here: http://sebastiansylvan.com/2013/05/08/robin-hood-hashing-should-be-your-default-hash-table-implementation/.

Removes are still done via the shiftConflicingKeys method. As discussed here http://sebastiansylvan.com/2013/08/05/more-on-robin-hood-hashing-2/ doing tombstones leads to long probe lengths when there are many removes and inserts of the same key. This shows up pretty well in the test suite. The existing shift scheme seems to be correct so I simply reused that.

Would like to do some performance testing and some comparison of probe length variance between this and the open hash map implementation.