[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

**To**:**Joerg Sonnenberger <joerg%britannica.bec.de@localhost>****Subject**:**Re: radix tree implementation for quota ?****From**:**Sad Clouds <cryintothebluesky%googlemail.com@localhost>**- Date: Mon, 29 Nov 2010 09:31:37 +0000

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

**Follow-Ups**:**Re: radix tree implementation for quota ?***From:*Joerg Sonnenberger

**Re: radix tree implementation for quota ?***From:*David Laight

**References**:**radix tree implementation for quota ?***From:*Manuel Bouyer

**Re: radix tree implementation for quota ?***From:*Sad Clouds

**Re: radix tree implementation for quota ?***From:*Manuel Bouyer

**Re: radix tree implementation for quota ?***From:*David Laight

**Re: radix tree implementation for quota ?***From:*Sad Clouds

**Re: radix tree implementation for quota ?***From:*Joerg Sonnenberger

- Prev by Date:
**Re: mpt Serious performance issues** - Next by Date:
**Re: radix tree implementation for quota ?** - Previous by Thread:
**Re: radix tree implementation for quota ?** - Next by Thread:
**Re: radix tree implementation for quota ?** - Indexes: