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

**To**:**tech-kern%netbsd.org@localhost****Subject**:**Re: radix tree implementation for quota ?****From**:**Joerg Sonnenberger <joerg%britannica.bec.de@localhost>**- Date: Mon, 29 Nov 2010 13:32:27 +0100

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

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

**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

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

- Prev by Date:
**Re: radix tree implementation for quota ?** - 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: