On: Robin Hood Hashing should be the default hash table implementation (2013)

[jzebedee]

I was comparing hash performance for a hobby project when I first discovered Robin Hood hashing. I ended up making a demo implementation of the backwards-shifting variant in C# [1] and found that it wasn't the best performer for the load case I needed. I still think it's an incredibly clever algorithm and I would love to find a project where I could use it again.

[1] https://github.com/jzebedee/rhbackshiftdict

[Bartweiss → jzebedee]

I'm curious - what was your deletion strategy?

The CodingCapsule links in the comments here suggest that tombstone deletion actually breaks the low-variance promise from the original paper, and only back shift deletion produces the theoretical performance.

[doomrobo → jzebedee]

Out of curiosity what did your load look like? What was the best performer?