Re: radix tree implementation for quota ?

[der Mouse <mouse%Rodents-Montreal.ORG@localhost>]

> 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