FreeBSD Most wanted
cpressey at catseye.mine.nu
Sun Mar 7 12:02:56 PST 2004
On Sun, 7 Mar 2004 21:31:56 +0200 (EET)
Narvi <narvi at haldjas.folklore.ee> wrote:
> On Sun, 7 Mar 2004, Chris Pressey wrote:
> > On Sun, 7 Mar 2004 20:46:32 +0200 (EET)
> > Narvi <narvi at 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.
More information about the freebsd-chat