Remix.run Logo
Experimenting with Robin Hood Hashing(twdev.blog)
13 points by signa11 5 days ago | 4 comments
rurban 3 hours ago | parent | next [-]

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.

xxs 2 hours ago | parent | prev | next [-]

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_elst 3 hours ago | parent | prev [-]

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

avadodin 28 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.