[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
Re: radix tree implementation for quota ?
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 I was specifically talking about particular sequences of numbers that
result in high collision rates, not random numbers. For example, if you take
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
Main Index |
Thread Index |