From owner-freebsd-chat@FreeBSD.ORG Sun Mar 7 12:02:56 2004 Return-Path: Delivered-To: freebsd-chat@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 75AA516A4CE for ; Sun, 7 Mar 2004 12:02:56 -0800 (PST) Received: from priv-edtnes14-hme0.telusplanet.net (outbound03.telus.net [199.185.220.222]) by mx1.FreeBSD.org (Postfix) with ESMTP id 2A55243D2D for ; Sun, 7 Mar 2004 12:02:56 -0800 (PST) (envelope-from cpressey@catseye.mine.nu) Received: from catseye.biscuit.boo ([154.5.85.228]) by priv-edtnes14-hme0.telusplanet.netSMTP <20040307200255.EVEH21205.priv-edtnes14-hme0.telusplanet.net@catseye.biscuit.boo>; Sun, 7 Mar 2004 13:02:55 -0700 Date: Sun, 7 Mar 2004 12:07:58 -0800 From: Chris Pressey To: Narvi Message-Id: <20040307120758.13f24851.cpressey@catseye.mine.nu> In-Reply-To: <20040307210125.Y68396@haldjas.folklore.ee> References: <20040306005744.T38020@haldjas.folklore.ee> <20040306013914.D38020@haldjas.folklore.ee> <6.0.1.1.1.20040306214526.08c5ed70@imap.sfu.ca> <20040306141742.4f41ba27.cpressey@catseye.mine.nu> <20040306155513.6a75e264.cpressey@catseye.mine.nu> <20040307110427.67a4394e.cpressey@catseye.mine.nu> <20040307210125.Y68396@haldjas.folklore.ee> Organization: Cat's Eye Technologies X-Mailer: Sylpheed version 0.9.9 (GTK+ 1.2.10; i386-portbld-freebsd4.9) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit cc: freebsd-chat@freebsd.org Subject: Re: FreeBSD Most wanted X-BeenThere: freebsd-chat@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Non technical items related to the community List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 07 Mar 2004 20:02:56 -0000 On Sun, 7 Mar 2004 21:31:56 +0200 (EET) Narvi wrote: > > On Sun, 7 Mar 2004, Chris Pressey wrote: > > > On Sun, 7 Mar 2004 20:46:32 +0200 (EET) > > Narvi wrote: > > > > > > > > On Sat, 6 Mar 2004, Chris Pressey wrote: > > > > > > > > > > > And, yeah. A hash table is really nothing by itself. It's just > > > > a way of taking a long list (or other structure) and splitting > > > > it up into N smaller structures. If your lists are never that > > > > long in the first place, there's no point. > > > > > > > > > > URKH! No it doesn't. Or rather, it should - > > > > I don't know what you are referring to here. > > > > The *traditional* hash table is one that uses linear probing, that is, > it converts a list to a nice cache friendly array and provides you > with a hint where you should start looking. The hash table > constructions that uses a list (aka a chain) to handle conflicts is a > derivative that has some nice features (esp if you want to delete > values) and some drawbacks. > > There are many different hashing schemes and the research into more > hasn't stopped (nor is likely to stop anytime soon). > > > > there are almost no good > > > reasons to use a naive chaining hash table. > > > > I did say list *(or other structure)*. > > This makes it only marginaly less incorrect. I don't think that this invalidates my (/Colin's) point, which I'll restate for clarity: The goal of computing a hash value is to reduce the search space. (Surely this hasn't really changed, even in the most new-fangled variation on the hash table theme?) And if the search space is already small, the reduction will be insignificant compared to the time taken to compute the hash value. -Chris