From owner-freebsd-hackers@FreeBSD.ORG Sun Dec 30 23:27:26 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 57D9616A417; Sun, 30 Dec 2007 23:27:26 +0000 (UTC) (envelope-from aryeh.friedman@gmail.com) Received: from mta5.srv.hcvlny.cv.net (mta5.srv.hcvlny.cv.net [167.206.4.200]) by mx1.freebsd.org (Postfix) with ESMTP id 2D9FD13C457; Sun, 30 Dec 2007 23:27:25 +0000 (UTC) (envelope-from aryeh.friedman@gmail.com) Received: from flosoft.no-ip.biz (ool-435559b8.dyn.optonline.net [67.85.89.184]) by mta5.srv.hcvlny.cv.net (Sun Java System Messaging Server 6.2-8.04 (built Feb 28 2007)) with ESMTP id <0JTV00M73YH90LE0@mta5.srv.hcvlny.cv.net>; Sun, 30 Dec 2007 18:27:10 -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 lBUNR8PJ042312; Sun, 30 Dec 2007 18:27:09 -0500 Date: Sun, 30 Dec 2007 18:27:08 -0500 From: "Aryeh M. Friedman" In-reply-to: <86r6h5zpr3.fsf@ds4.des.no> To: =?UTF-8?B?RGFnLUVybGluZyBTbcO4cmdyYXY=?= Message-id: <4778294C.3030905@gmail.com> MIME-version: 1.0 Content-type: text/plain; charset=UTF-8 Content-transfer-encoding: 8BIT 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> <86r6h5zpr3.fsf@ds4.des.no> User-Agent: Thunderbird 2.0.0.9 (X11/20071228) Cc: freebsd-hackers@freebsd.org, Ivan Voras 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: Sun, 30 Dec 2007 23:27:26 -0000 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Dag-Erling Smørgrav wrote: > "Aryeh M. Friedman" writes: >> 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) > > Not an "old wives' tale", but rather an easy way to implement a > hash algorithm that is good enough for most simple uses: metric > modulo table size, where metric is a number derived from the item > in such a manner as to give a good spread. Sorry for taking a while to reply.... but the above only applies if your using a very primitive hash like Knuth's multiplication one.... every modern hash I know of should have 2^k buckets actually for some k<2^32 [in almost all cases <2^16 except for algorithms like the one I mentioned I am working on which sets k=n where n=the bit count of the key]. - -- 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 iD8DBQFHeClMzIOMjAek4JIRAlA+AKCVC0oOblPhF7QZARtkfUmdGX4hVACfcyPd qhtFfOt2lOaxcmCDt6/wXsE= =jztY -----END PGP SIGNATURE-----