[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: Mon, 29 Nov 2010 11:12:21 -0500 (EST)

> The prime number hash always looks good for most simple sequences. > It looks extremely bad for other choices like {p, 2p, 3p, 4p, ...}. Indeed. > But for semi-random input, the simple prime hash can be a very bad > hash function. What's "semi-random" here? For random input, that is, input uncorrelated with anything else, all hash functions are equally good, so the simplest/fastest is best. But input is almost never truly random. (In this case, for example, it is heavily weighted towards numbers near zero.) Without any real data on what UID distribution looks like in practice, we're all speculating in a vacuum here. > If the keys are controlled by a third party, it is very easy to > degrade the performance to a linear list. Sure, but that's not a useful remark. It's equally true of (n*K)>>32, or for that matter any other easily invertible hash function. If the bucket count is small enough to make guessing feasible for the attacker, it's true of any hash function cheap enough to be useful as a hash function. /~\ 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:*David Holland

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

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

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