Date: Sun, 7 Mar 2004 21:31:56 +0200 (EET) From: Narvi <narvi@haldjas.folklore.ee> To: Chris Pressey <cpressey@catseye.mine.nu> Cc: freebsd-chat@freebsd.org Subject: Re: FreeBSD Most wanted Message-ID: <20040307210125.Y68396@haldjas.folklore.ee> In-Reply-To: <20040307110427.67a4394e.cpressey@catseye.mine.nu> 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>
next in thread | previous in thread | raw e-mail | index | archive | help
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. > > -Chris >
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040307210125.Y68396>