Date: Fri, 28 Dec 2007 07:49:31 -0500 From: "Aryeh M. Friedman" <aryeh.friedman@gmail.com> To: Ivan Voras <ivoras@freebsd.org> Cc: freebsd-hackers@freebsd.org Subject: Re: BSD license compatible hash algorithm? Message-ID: <4774F0DB.50503@gmail.com> In-Reply-To: <4774EF27.90307@gmail.com> References: <5950EE0C-383D-4D6B-9991-A0DEABD2ADE4@u.washington.edu> <20071228003716.GB48997@lor.one-eyed-alien.net> <B8D4C3C6-B867-4550-9F17-4DC6930D10E2@u.washington.edu> <fl2qiv$qoh$1@ger.gmane.org> <4774EF27.90307@gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 > > All hashs have issues with pooling.... see > http://www.burtleburtle.net/bob/hash/index.html... btw it is a old > wives tale that the number of buckets should be prime (mostly based > on the very weak implementation Knuth offered) Forgot to mention this is a theortical not an implementation issue namely if the range of H is a proper subset of it's domain (which by definition all finite operations are when considering them over all integers) then there exists no bijective (i.e. one to one mapping) function between the two... thus even if the bucket count is equal to the number of elements to be hashed there will be collisions [roughly 1/3] unless you use something like gperf to find a perfect hash (this is impractical for all non-dictionary [i.e. static compile time content] applications) - -- Aryeh M. Friedman FloSoft Systems http://www.flosoft-systems.com Developer, not business, friendly -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.4 (FreeBSD) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHdPDbzIOMjAek4JIRAgE0AJ4y5b52d+8VajtSwugQjqEitlagxgCeMAn5 hY7RqL5Ije6MTusv7k3ORAI= =HJbs -----END PGP SIGNATURE-----
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?4774F0DB.50503>