Re: radix tree implementation for quota ?

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

On Mon, Nov 29, 2010 at 01:12:47PM +0000, Sad Clouds wrote:
> I've tried many different hash functions and from my experiments,
> for hashing integers, it's very hard to beat 'number % prime'. There
> is no magic number that you need to derive for every different set of
> integers, it just works for all sorts of integers and gives very good
> results.

The prime number hash always looks good for most simple sequences. 
It looks extremely bad for other choices like {p, 2p, 3p, 4p, ...}.
I explained already why it works well for many cases. I am not saying
that you can't easily construct samples where it is the best possible
hash. The very nature of a hash function ensures that. But for
semi-random input, the simple prime hash can be a very bad hash
function. If the keys are controlled by a third party, it is very easy
to degrade the performance to a linear list.

Joerg