From owner-freebsd-hackers@FreeBSD.ORG  Sat Dec 29 21:12:20 2007
Return-Path: <owner-freebsd-hackers@FreeBSD.ORG>
Delivered-To: hackers@freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34])
	by hub.freebsd.org (Postfix) with ESMTP id 7BD1C16A417
	for <hackers@freebsd.org>; Sat, 29 Dec 2007 21:12:20 +0000 (UTC)
	(envelope-from eddy+public+spam@noc.everquick.net)
Received: from a.mx.ict1.everquick.net (a.mx.everquick.net [204.10.191.21])
	by mx1.freebsd.org (Postfix) with ESMTP id 1445213C442
	for <hackers@freebsd.org>; Sat, 29 Dec 2007 21:12:19 +0000 (UTC)
	(envelope-from eddy+public+spam@noc.everquick.net)
Received: from pop.ict1.everquick.net (localhost [127.0.0.1])
	by a.mx.ict1.everquick.net (8.12.10/8.12.10) with ESMTP id
	lBTKoFmp025452; Sat, 29 Dec 2007 20:50:15 GMT
X-Everquick-No-Abuse-1: Report any email abuse to <abuse@everquick.net> or
X-Everquick-No-Abuse-2: call +1 (785) 865-5885.  Please be sure to reference
X-Everquick-No-Abuse-3: the Message-Id and include GMT timestamps.
Received: from localhost (eddy@localhost)
	by pop.ict1.everquick.net (8.13.3/8.13.3/Submit) with ESMTP id
	lBTKoFjs025425; Sat, 29 Dec 2007 20:50:15 GMT
X-Authentication-Warning: pop.ict1.everquick.net: eddy owned process doing -bs
Date: Sat, 29 Dec 2007 20:50:14 +0000 (GMT)
From: "Edward B. DREGER" <eddy+public+spam@noc.everquick.net>
X-X-Sender: eddy@pop.ict1.everquick.net
To: Garrett Cooper <youshi10@u.washington.edu>
In-Reply-To: <7F9D2F63-B5E6-41DE-843A-8D673C2DC88E@u.washington.edu>
Message-ID: <Pine.LNX.4.62.0712292039410.21327@pop.ict1.everquick.net>
References: <5950EE0C-383D-4D6B-9991-A0DEABD2ADE4@u.washington.edu>
	<7F9D2F63-B5E6-41DE-843A-8D673C2DC88E@u.washington.edu>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Cc: 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
	<freebsd-hackers.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>, 
	<mailto:freebsd-hackers-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-hackers>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Help: <mailto:freebsd-hackers-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>,
	<mailto:freebsd-hackers-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Sat, 29 Dec 2007 21:12:20 -0000

GC> Date: Thu, 27 Dec 2007 16:34:32 -0800
GC> From: Garrett Cooper

GC> On Dec 27, 2007, at 4:30 PM, Garrett Cooper wrote:
GC>
GC> > Just wondering if anyone knew of a good BSD license compatible
GC> > key-based hash placement / retrieval algorithm that was available
GC> > anywhere.
GC>
GC> 1. It needs to be in C, not C++.

Although I'm not directly answering your question...


GC> 2. I meant hash table / bucket when I said "hash" in the subject.

...have you explored [order-preserving] minimal perfect hash functions?

perfect_hash = ( hash1[x] + hash2[x] ) % entry_count ;

The "trick" lies in computing hash1[] and hash2[].  A Google search for

	==> chm92 (hash|hashing) <==

will get you started.


Eddy
--
Everquick Internet - http://www.everquick.net/
A division of Brotsman & Dreger, Inc. - http://www.brotsman.com/
Bandwidth, consulting, e-commerce, hosting, and network building
Phone: +1 785 865 5885 Lawrence and [inter]national
Phone: +1 316 794 8922 Wichita
________________________________________________________________________
DO NOT send mail to the following addresses:
davidc@brics.com -*- jfconmaapaq@intc.net -*- sam@everquick.net
Sending mail to spambait addresses is a great way to get blocked.
Ditto for broken OOO autoresponders and foolish AV software backscatter.