Peter Dimov wrote:
As for table sizes being a power of two being a source of speedup, this is obviously only true when hv % 2^n doesn't produce collisions. If the key set doesn't already have this property, the cost of fixing it (in the general case, where it is not known which bits vary, something like x ^ (x % p1 + x * p2) needs to be used) may cancel the speedup obtained by using a 2^n table size.
I agree. This wasn't clear in my last mail, but when I wrote:
A better approach to using a power of 2 might be to apply a further transformation to the hash value, which might take into account the current hash table size.
I meant that a power of 2 hash table should do this, and might be able to do it better since it knows how many bits are required.
On the other hand, it doesn't seem to cost us anything to apply x + (x
3) to our pointer hash function, so we might as well do it.
Okay, I'll do that.