Re: radix tree implementation for quota ?

[der Mouse <mouse%Rodents-Montreal.ORG@localhost>]

> 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