Comment by Sesse__
4 months ago
FWIW, I found that when doing Robin Hood, SSE is just a loss, since you usually find the element so soon. (If you are dominated by non-matching lookups, you can consider putting a Bloom filter in front.)
4 months ago
FWIW, I found that when doing Robin Hood, SSE is just a loss, since you usually find the element so soon. (If you are dominated by non-matching lookups, you can consider putting a Bloom filter in front.)
With linear probing RH, a failed lookup can stop as early as a successful one, as long as you also store the hash (useful for fast insertion): stop looking when you'd insert the key you're looking for before the current entry.
I think the point of the SSE stuff was to avoid branching (apart from the very exceptional case where you would be more than 15 slots away