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:
 > Without any real data on what UID distribution looks like in practice,
 > we're all speculating in a vacuum here.

Just for shits and giggles I ran this on a real password file with
about 350 users that's had lots of churn since it was first
established. Using Joerg's hash with a table of size 512 gave 90
collisions; using x % 509 (the nearest available prime) gave 91.

For comparison I tried some of the (more expensive) hashes from db4
and got 111, 94, and 84.

None of the hash functions generated significant hotspots. It seems
like a nonissue.

(Of course, hashing 350 things isn't exactly a big challenge...)

David A. Holland

Home | Main Index | Thread Index | Old Index