4 ms·
> They also use linear probing because it's generally much faster than double-hashing Optimal is probably to use linear probing for a few indices at a time (de
by _benedict 4y ago
> They also use linear probing because it's generally much faster than double-hashing
Optimal is probably to use linear probing for a few indices at a time (depending on size of hash table entries, say, 4 or 8), and double hashing to move to a new region if no empty elements can be found in that run.
- anonymoushn 4y agoIf you can choose to have a quality hash function, it's probably better to do that.
- _benedict 4y agoSure, but if you have a sufficiently high quality hash function this approach is equivalent to simple linear probing, as you will never need to probe more than the initial batch. So why not have this behaviour as a fallback?
- fanf2 4y agoA similar idea is to think of the linear probe segments as large buckets that can store multiple items. The difference is that the hash identifies the bucket rather than an individual slot, so you always scan the whole bucket rather than maybe landing in the middle of a segment.
- bruce343434 4y ago>probably based on what?
- _benedict 4y agoThe fact that this provides the benefits of both approaches, namely that it is (branch) predictable and amortises memory latency while obtaining the probabilistic benefits of double hashing.