Re: radix tree implementation for quota ?

[David Laight <david%l8s.co.uk@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

What about the sequence prime, prime*2, prime*3 etc.
Unless you are going to search for a factor that works, no particular
value is any better than any other if you allow pathaogical data
to be selected.

Even searching for a factor may not help.
I looked at the distribution for the elf symbol table in libc.
The current 'first prime below the power of 2' was no different
from the '2^n-1' value - except that it is a lot slower to compute.

I would always look for a deterministic algorythm. Hashing to linked
lists is still o(n), with a hash table with 'h' entries it is just
'h' times faster, and then only if the linked lists are equal length.
Trying to get hash chains of length 1 or 2 requires a lot of knowledge
of the data in order to generate a suitable hash function.
And then calculating the hash might be more expensive than a few
comparisons.

        David

-- 
David Laight: david%l8s.co.uk@localhost