FRESH

Hacker News

Experimenting with Robin Hood Hashing

23 points by signa11

by rurban

1 subcomments

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.

by xxs

0 subcomment

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.

by vander_elst

1 subcomments

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

by optimalsolver

0 subcomment

Shoutout to unordered_dense, a drop-in replacement for C++ unordered_map that uses this:
https://github.com/martinus/unordered_dense