FreeBSD Most wanted

[Chris Pressey]

On Sat, 06 Mar 2004 22:31:14 +0000
Colin Percival <colin.percival at wadham.ox.ac.uk> wrote:

> At 22:17 06/03/2004, Chris Pressey wrote:
> >Colin Percival <colin.percival at wadham.ox.ac.uk> wrote:
> > > Nobody
> > > quite understands why hash tables are not a perfect data structure
> > > until they've tried to implement one in assembly language.  (And,
> > > after performing such a task, few people will use hash tables
> > > without asking themselves, at least for a moment, if there might
> > > be a cheaper solution to the problem at hand.)
> >
> >Not sure what you mean here... surely it's no easier to implement
> >(say) an AVL tree or a red-black tree in assembly?
> 
>    Perhaps not, but it's much easier to implement an unsorted list.
>    :-)
> 
>    I've often seen people using hash tables to keep track of very
> small numbers of objects, where a simple sequential scan will be much
> faster than a hash table lookup; I also see people using hash tables
> for data where the keys rarely, if ever, change.

Ah, yes, that's a good point.  Modern high-level languages do tend to
just give you these things on the strictly black-box ADT level, like
dictionaries... and with all the guts abstracted away, programmers do
tend to let themselves get a bit carried away.  It Does What I Want,
it Must Be What I Need.

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.

> >In fact, I'd think a hash function would often be a good candidate
> >for hand-coded assembly - if you want to play "Beat the Compiler" :)
> 
>    Quite likely, yes[0].  But the act of writing usually makes people
> realize just how much work the processor does every time a
> hashlookup() call is made.  The amount of work the programmer does
> isn't really important.  (You're not planning on assembly-coding a
> hash table more than once, are you?)

If I am, rest assured it's only for my own entertainment.

>    Of course, part of the problem is that most undergraduate courses
> still teach the myth that random access memory is, err, random access.

:-)

-Chris