From: Daniel James (daniel_at_[hidden])
Date: 2005-03-19 08:23:28
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.