4 ms·
Note this "small" detail: https://en.wikipedia.org/wiki/Hash_table#Open_addressing https://en.wikipedia.org/wiki/Hash_table#Open_addressing "A drawback of all
by acqq 10y ago
Note this "small" detail:
https://en.wikipedia.org/wiki/Hash_table#Open_addressing https://en.wikipedia.org/wiki/Hash_table#Open_addressing
"A drawback of all these open addressing schemes is that the number of stored entries cannot exceed the number of slots in the bucket array. In fact, even with good hash functions, their performance dramatically degrades when the load factor grows beyond 0.7 or so. For many applications, these restrictions mandate the use of dynamic resizing, with its attendant costs."
Even if this is marked as "Citation needed" in Wikipedia anybody who tries to measure can get the same results: open addressing is much worse when the hash table is fuller and not "relatively empty." It's also much less forgiving to the hashing algorithm used. 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 a reasonable chance that your open addressing implementation measured optimistically can get worse in real life uses.
Increasing data locality is a good thing, however.
I'd prefer carefully implemented chaining unless I could be made sure that the "unlucky case" scenarios of open addressing won't happen.
So collect the real life uses, then measure, then decide what's better. Don't trust pre-selected micro-benchmarks.
- 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.