From owner-freebsd-chat@FreeBSD.ORG Sun Mar 7 11:32:31 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 CD92416A4CE for ; Sun, 7 Mar 2004 11:32:31 -0800 (PST) Received: from haldjas.folklore.ee (Haldjas.folklore.ee [193.40.6.121]) by mx1.FreeBSD.org (Postfix) with ESMTP id 29C2643D1D for ; Sun, 7 Mar 2004 11:32:31 -0800 (PST) (envelope-from narvi@haldjas.folklore.ee) Received: from haldjas.folklore.ee (localhost [127.0.0.1]) by haldjas.folklore.ee (8.12.10/8.12.10) with ESMTP id i27JVuUA070100; Sun, 7 Mar 2004 21:31:56 +0200 (EET) (envelope-from narvi@haldjas.folklore.ee) Received: from localhost (narvi@localhost)i27JVuQS070097; Sun, 7 Mar 2004 21:31:56 +0200 (EET) (envelope-from narvi@haldjas.folklore.ee) Date: Sun, 7 Mar 2004 21:31:56 +0200 (EET) From: Narvi To: Chris Pressey In-Reply-To: <20040307110427.67a4394e.cpressey@catseye.mine.nu> Message-ID: <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> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Spam-Status: No, hits=0.0 required=8.0 tests=none autolearn=no version=2.63 X-Spam-Checker-Version: SpamAssassin 2.63 (2004-01-11) on haldjas.folklore.ee 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 19:32:31 -0000 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. > > -Chris >