FreeBSD Most wanted
Chris Pressey
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.
-Chris
More information about the freebsd-chat
mailing list