3 ms·
> So unless you're clever enough to detect the cases where you'd carefully regrow the hash table each time it's "too full" There's little smart about it, open
by masklinn 10y ago
> So unless you're clever enough to detect the cases where you'd carefully regrow the hash table each time it's "too full"
There's little smart about it, open addressing implementations decide on a filling threshold, keep track of the current fill factor and resize when it's exceeded.
The smart part is deciding on the maximum fill factor, which depend on the probing strategy and the worst case you allow.
- acqq 10y ago> which depend on the probing strategy Not only. Resizing can involve rehashing all of the existing entries (unless you lose memory by storing the full hash values all the time, then it still involves copying and reallocation). If without open addressing you can get by with much less resizing and with worse (but faster) hashing function (although modern languages often have to use non-trivial hashing functions to prevent some kinds of attacks), it's tricky to find under which circumstances open addressing is cheaper: again, microbenchmarks aren't the complete story, the real-world uses where users grow the hashes are: what are the typical sizes? The typical occurrences of regrows? The good solution behaves good for a typical case (where a lot of the hashes are probably quite small9 and for the typical "big" case where some hashes grow significantly.
- dietrichepp 10y agoIs that really true? Yes, you may need to rehash but the amount of resizing you do is still going to be similar for similar performance targets.