3 ms·
If you have a reasonable hash function, why is power-of-two and bitmasking bad? If you're uniformly distributed over a range N you'll be uniformly distributed
by gct 8y ago
If you have a reasonable hash function, why is power-of-two and bitmasking bad? If you're uniformly distributed over a range N you'll be uniformly distributed over N/2
- jamiek88 8y agoIt isn’t. You are correct. This is useful to support the underlying hash function but at that point you might as well just improve that and take the power of two, bitmask approach.
- vidarh 8y agoI think that boils down the problem nicely: if you're using a hash table or writing your own for a specialised use-case, you should pick a good hash function. But if you're writing a general purpose hashtable implementation you have to deal with the fact that a lot of users won't use a good hash while some will, so you need to find a tradeoff between using their hash as-is and mixing it up to improve on the bad ones. The latter need to come almost free, however, or you'll ruin performance for those who actually do their homework.