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

**To**:**Sad Clouds <cryintothebluesky%googlemail.com@localhost>****Subject**:**Re: radix tree implementation for quota ?****From**:**David Laight <david%l8s.co.uk@localhost>**- Date: Mon, 29 Nov 2010 09:57:18 +0000

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

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