tech-kern archive

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

Re: radix tree implementation for quota ?

On Mon, Nov 29, 2010 at 11:12:21AM -0500, der Mouse wrote:
> > 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.

Only if you keep K fixed. If you follow the "rehash with different K on
high number of collissions" scheme, it is resilient to such attacks.


Home | Main Index | Thread Index | Old Index