Re: radix tree implementation for quota ?

[Joerg Sonnenberger <joerg%britannica.bec.de@localhost>]

On Mon, Nov 29, 2010 at 09:31:37AM +0000, Sad Clouds wrote:
> 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

I asked the Python Oracle for a 32bit number and got 3063404725. This
results in hash(x,n) = ((3063404725ULL * x) >> 32) % n as function.
For n=32 and 32 keys, I get 8 single collisions. For n=256 and 256 keys,
I get 39 single collisions. Depending on the choosen random number, the
collision rate will be higher or lower, but if it is too high, you can
always just pick a different one and rehash. Theory says that the result
is probalistically near a random distribution *independent* of the input.

Joerg