FreeBSD Most wanted

[Narvi]

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.

>
> -Chris
>