Re: radix tree implementation for quota ?

[Sad Clouds <cryintothebluesky%googlemail.com@localhost>]

On Mon, 29 Nov 2010 01:26:18 +0100
Joerg Sonnenberger <joerg%britannica.bec.de@localhost> wrote:

> On Sun, Nov 28, 2010 at 11:37:12PM +0000, Sad Clouds wrote:
> > I've had some issues with a hash table that was power of 2 in size, and
> > most of the keys were multiples of 4, or 8 integers, for example.
> > However making hash table size a prime number and using a good hash
> > function, results in very good key distribution. This works especially
> > well when hashing simple intergers, e.g. file descriptors, etc.
> 
> If you have issues with a power of 2 hash table size, you do not have a
> good hash function in first place. A simple multiplicative hash function
> like ((uint64_t)X * random32) >> 32 % size is known to provide good
> results for most choices of random32. The suggestion to use a prime
> number goes back to using primitive hash functions that don't properly
> avoid funnels. With a good hash function, using a non power of 2 size
> just tends to be slower.
> 
> Joerg

Joerg I was specifically talking about particular sequences of numbers that 
result in high collision rates, not random numbers. For example, if you take 
the following:

4, 8, 12, 16, 20 ...

Every integer is a multiple of 4. Can you give me a full example of a hash 
function for power of 2 hash table, that will perform as well as a simple:

interger % prime