Re: FreeBSD Most wanted

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
_______________________________________________
freebsd-chat@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-chat
To unsubscribe, send any mail to "freebsd-chat-unsubscribe@freebsd.org"