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>