Path: utzoo!attcan!uunet!lll-winken!lll-tis!ames!mailrus!purdue!decwrl!megatest!djones
From: djones@megatest.UUCP (Dave Jones)
Newsgroups: comp.lang.c
Subject: Re: hash algorithm
Message-ID: <732@goofy.megatest.UUCP>
Date: 22 Aug 88 22:26:07 GMT
References: <813@polari.UUCP>
Organization: Megatest Corporation, San Jose, Ca
Lines: 29

I recently posted an original hash-table routine here. It is the result 
of a great deal of research and experimentation.  I never expected anyone 
to say, "Thanks," and sure enough, no one has. That's okay.

This note is just to indicate that I do not intend to respond to postings
discussing the relative values of hashing methods, although I would
be happy to see other algorithms, especially compilable C code.
It's a fascinating subject, which has been the topic of extensive research
over the years, but I just don't have the time or inclination right
now.

When I did the comparisons between various methods, I did not save the 
statistics, and I have no interest in repeating them.  Nor would they 
necessarily be applicable to all machines, if I still had them.  The
constraints that I was under were roughly these:

   0. Multiple hash-table "objects" was essential.

   1. Multiplication by a variable was slow.

   2. Division by a variable was about four times as slow as 
      multiplication by a variable.

   3. Multiplication by constant 3 was implemented by the compiler as
      a shift and add and was therefore fast.

   4. Malloc() was too slow to consider.

   5. The machine was, and was likely to remain forever, a two's
      complement machine.