[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**:**der Mouse <mouse%Rodents-Montreal.ORG@localhost>**- Date: Sun, 28 Nov 2010 20:12:34 -0500 (EST)

> If you have issues with a power of 2 hash table size, you do not have > a good hash function in first place. Almost by definition. > With a good hash function, using a non power of 2 size just tends to > be slower. Indeed - other things being equal. Which they often aren't. I think the point of a prime table size is that with a hash key that's an integral type, as here, then you can often use a prime table size and get decent reults from the identity hash function - or, to think of it another way, use value%size as your hash function and use the identity mapping from hash values to table buckets. A prime hash table size gives about as good hashing under this sort of scheme as anything, for most key distributions. Yes, reduction modulo a prime is generally a substantially slower operation than masking off all but the last N bits. However, if it's faster than the hash function you were going to use before doing the masking, which is not infrequently the case, it's an overall win. /~\ The ASCII Mouse \ / Ribbon Campaign X Against HTML mouse%rodents-montreal.org@localhost / \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B

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

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