[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
Re: radix tree implementation for quota ?
> If you have issues with a power of 2 hash table size, you do not have
> a good hash function in first place.
Almost by definition.
> With a good hash function, using a non power of 2 size just tends to
> be slower.
Indeed - other things being equal. Which they often aren't.
I think the point of a prime table size is that with a hash key that's
an integral type, as here, then you can often use a prime table size
and get decent reults from the identity hash function - or, to think of
it another way, use value%size as your hash function and use the
identity mapping from hash values to table buckets. A prime hash table
size gives about as good hashing under this sort of scheme as anything,
for most key distributions.
Yes, reduction modulo a prime is generally a substantially slower
operation than masking off all but the last N bits. However, if it's
faster than the hash function you were going to use before doing the
masking, which is not infrequently the case, it's an overall win.
/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML mouse%rodents-montreal.org@localhost
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B
Main Index |
Thread Index |