From owner-freebsd-hackers@FreeBSD.ORG  Sat Dec 29 21:35:25 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 2B61E16A417
	for <hackers@freebsd.org>; Sat, 29 Dec 2007 21:35:25 +0000 (UTC)
	(envelope-from peterjeremy@optushome.com.au)
Received: from mail18.syd.optusnet.com.au (mail18.syd.optusnet.com.au
	[211.29.132.199])
	by mx1.freebsd.org (Postfix) with ESMTP id B37CB13C46B
	for <hackers@freebsd.org>; Sat, 29 Dec 2007 21:35:24 +0000 (UTC)
	(envelope-from peterjeremy@optushome.com.au)
Received: from server.vk2pj.dyndns.org
	(c220-239-20-82.belrs4.nsw.optusnet.com.au [220.239.20.82])
	by mail18.syd.optusnet.com.au (8.13.1/8.13.1) with ESMTP id
	lBTLZMUu019922
	(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO);
	Sun, 30 Dec 2007 08:35:23 +1100
Received: from server.vk2pj.dyndns.org (localhost.vk2pj.dyndns.org [127.0.0.1])
	by server.vk2pj.dyndns.org (8.14.2/8.14.1) with ESMTP id lBTLZMis073533;
	Sun, 30 Dec 2007 08:35:22 +1100 (EST)
	(envelope-from peter@server.vk2pj.dyndns.org)
Received: (from peter@localhost)
	by server.vk2pj.dyndns.org (8.14.2/8.14.2/Submit) id lBTLZM5Q073532;
	Sun, 30 Dec 2007 08:35:22 +1100 (EST) (envelope-from peter)
Date: Sun, 30 Dec 2007 08:35:21 +1100
From: Peter Jeremy <peterjeremy@optushome.com.au>
To: "Edward B. DREGER" <eddy+public+spam@noc.everquick.net>
Message-ID: <20071229213521.GW40785@server.vk2pj.dyndns.org>
References: <5950EE0C-383D-4D6B-9991-A0DEABD2ADE4@u.washington.edu>
	<7F9D2F63-B5E6-41DE-843A-8D673C2DC88E@u.washington.edu>
	<Pine.LNX.4.62.0712292039410.21327@pop.ict1.everquick.net>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha1;
	protocol="application/pgp-signature"; boundary="ofZMSlrAVk9bLeVm"
Content-Disposition: inline
In-Reply-To: <Pine.LNX.4.62.0712292039410.21327@pop.ict1.everquick.net>
X-PGP-Key: http://members.optusnet.com.au/peterjeremy/pubkey.asc
User-Agent: Mutt/1.5.17 (2007-11-01)
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:35:25 -0000


--ofZMSlrAVk9bLeVm
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Sat, Dec 29, 2007 at 08:50:14PM +0000, Edward B. DREGER wrote:
>...have you explored [order-preserving] minimal perfect hash functions?
>
>perfect_hash =3D ( hash1[x] + hash2[x] ) % entry_count ;

This relies on pre-knowledge of all possible entries.  It's excellent for
(eg) keyword lookups in a compiler (and gcc uses gperf for that reason)
but no good where the input can be arbitrary.

--=20
Peter Jeremy
Please excuse any delays as the result of my ISP's inability to implement
an MTA that is either RFC2821-compliant or matches their claimed behaviour.

--ofZMSlrAVk9bLeVm
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.4 (FreeBSD)

iD8DBQFHdr2Z/opHv/APuIcRAixVAJ9FRodz7VA5lSTTb+thHdgUfaj8QgCgktV2
NbDvoyWtAx8XEuzpRIaq+bY=
=Xp6K
-----END PGP SIGNATURE-----

--ofZMSlrAVk9bLeVm--