[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: Tue, 30 Nov 2010 16:48:03 +0100

On Tue, Nov 30, 2010 at 03:37:28PM +0000, Sad Clouds wrote: > Well, if hash table is heavily used for looking up keys, you can reduce > the number of collisions even further. The trick is to use different > hash functions, which are very fast to compute: This is just one (bad) version of implementing collision handling. This does *not* reduce the number of collissions, it just may help to spread them better over the table. If you want to have a proper algorithm for collision avoidance, look at Cuckoo Hashing. It ensures that every look up has to check at most two different keys. That requires the availability of universal hash functions again, so we are back at the original topic. Joerg

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

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

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

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

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

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