Skip site navigation (1)Skip section navigation (2)
Date:      Sat, 26 Apr 1997 12:53:17 -0700 (MST)
From:      Terry Lambert <terry@lambert.org>
To:        bde@zeta.org.au (Bruce Evans)
Cc:        michaelh@cet.co.jp, msmith@atrad.adelaide.edu.au, hackers@hub.freebsd.org
Subject:   Re: namei & hash functions
Message-ID:  <199704261953.MAA07467@phaeton.artisoft.com>
In-Reply-To: <199704261753.DAA12300@godzilla.zeta.org.au> from "Bruce Evans" at Apr 27, 97 03:53:57 am

next in thread | previous in thread | raw e-mail | index | archive | help
> The mask version is the original 4.4Lite version.  The prime version is
> supposed to be a FreeBSD enhancement.  One would hope that whoever changed
> it did extensive tests :-).

I was going to say the same.

Knuth is very clear in "Sorting and Searching" that primacy helps to
disperse the bucket hits; however, once they are dispersed, it's not
a big deal what intelligence caused the dispersion, so long as you
don't get unbalanced hash chain lengths.  I don't know if the shift
by 5 version is really inferior; it depends on whether or not it
causes disproportionate hash chain length between buckets, doesn't it?

It would be nice if people would test these things, beyond cookbooking;
using a prime number-of-buckets is an obvious win; changing the hash
algorithm is not obvious without testing, and not even then if there
is any bias in the test data.


					Terry Lambert
					terry@lambert.org
---
Any opinions in this posting are my own and not those of my present
or previous employers.



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199704261953.MAA07467>