From owner-freebsd-hackers@FreeBSD.ORG Fri Dec 28 13:19:33 2007 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 826B116A469 for ; Fri, 28 Dec 2007 13:19:33 +0000 (UTC) (envelope-from aryeh.friedman@gmail.com) Received: from mta4.srv.hcvlny.cv.net (mta4.srv.hcvlny.cv.net [167.206.4.199]) by mx1.freebsd.org (Postfix) with ESMTP id 48B6513C469 for ; Fri, 28 Dec 2007 13:19:33 +0000 (UTC) (envelope-from aryeh.friedman@gmail.com) Received: from flosoft.no-ip.biz (ool-435559b8.dyn.optonline.net [67.85.89.184]) by mta4.srv.hcvlny.cv.net (Sun Java System Messaging Server 6.2-8.04 (built Feb 28 2007)) with ESMTP id <0JTR00JU5FMKFUT0@mta4.srv.hcvlny.cv.net>; Fri, 28 Dec 2007 07:49:32 -0500 (EST) Received: from flosoft.no-ip.biz (localhost [IPv6:::1]) by flosoft.no-ip.biz (8.14.2/8.14.2) with ESMTP id lBSCnVV2001284; Fri, 28 Dec 2007 07:49:31 -0500 Date: Fri, 28 Dec 2007 07:49:31 -0500 From: "Aryeh M. Friedman" In-reply-to: <4774EF27.90307@gmail.com> To: Ivan Voras Message-id: <4774F0DB.50503@gmail.com> MIME-version: 1.0 Content-type: text/plain; charset=UTF-8 Content-transfer-encoding: 7BIT X-Enigmail-Version: 0.95.5 References: <5950EE0C-383D-4D6B-9991-A0DEABD2ADE4@u.washington.edu> <20071228003716.GB48997@lor.one-eyed-alien.net> <4774EF27.90307@gmail.com> User-Agent: Thunderbird 2.0.0.9 (X11/20071217) Cc: freebsd-hackers@freebsd.org Subject: Re: BSD license compatible hash algorithm? X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 28 Dec 2007 13:19:33 -0000 -----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-----