[boost] Re: [review] hash functions

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.