HNNewShowAskJobs
Built with Tanstack Start
Experimenting with Robin Hood Hashing(twdev.blog)
13 points by signa11 5 days ago | 4 comments
  • rurban3 hours ago

    Don't compare apples to oranges. unordered_map is so slow because it has to guarantee pointer stability, doing seperate chaining, whilst the open addressing hashtables doing probing and moving do not. They are at least 2x faster.

    Compare to linear probing, quadratic probing, double hashing, cuckoo, or swiss tables.

  • xxs2 hours ago

    Aside already mentioned comparison to unordered_map, there appears to have a bug, on line 61: "p = (p + 1) & LenV". It should be mod (%) like the rest of the code.

    Morealso mod is slow in general and it should be replaced by bitwise and (&) and power of 2 sized map, then using LenV-1.

  • vander_elst3 hours ago

    I understood what's going on in this article only after reading the paper. It's might be good to define things s bit better in the article or say that the paper is a prerequisite for reading the article

    • avadodin28 minutes ago |parent

      The paper itself is an overview that doesn't discuss the cache-friendly optimizations in the original 1986 PhD thesis so it feels like a hash table all the way down.