Date: Sun, 7 Mar 2004 12:07:58 -0800 From: Chris Pressey <cpressey@catseye.mine.nu> To: Narvi <narvi@haldjas.folklore.ee> Cc: freebsd-chat@freebsd.org Subject: Re: FreeBSD Most wanted Message-ID: <20040307120758.13f24851.cpressey@catseye.mine.nu> In-Reply-To: <20040307210125.Y68396@haldjas.folklore.ee> References: <Pine.LNX.4.43.0403011839470.3269-100000@pilchuck.reedmedia.net> <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>
next in thread | previous in thread | raw e-mail | index | archive | help
On Sun, 7 Mar 2004 21:31:56 +0200 (EET) Narvi <narvi@haldjas.folklore.ee> wrote: > > On Sun, 7 Mar 2004, Chris Pressey wrote: > > > On Sun, 7 Mar 2004 20:46:32 +0200 (EET) > > Narvi <narvi@haldjas.folklore.ee> 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040307120758.13f24851.cpressey>