Re:I Wrote My Fastest Hashtable
by thomasahle on Monday February 27, 2017 @02:35PM
(#13747186)
I found the lecture notes that made this claim on internet archive https://web.archive.org/web/20031127062932/http://www.august...
It doesn't give any sources unfortunately.
IS it really that good?
If you end up having to probe a lot with linear probing, it is likely you have a bad hash function, which is the same reason you give against prime modulus (that they are a stopgap more than a solution).
Second, don't you end up having to jump all over the place, which means cache misses, that are way more expensive that a few probes on consecutive slots?