Re: A few questions on PCL

[Danny Bobrow <Bobrow.pa@Xerox.COM>]

    Knuth has a fairly detailed chapter on hashing in Vol. 3 of The
    Art of Computer Programming.  The bottom line is that double
    hashing is preferable to using any kind of fixed offset or mirror
    location, etc. (Use one hash function for the initial probe, then
    another that
     produces a psuedo-random increment for successive probes
     which is relatively prime to the size of the table.)
We chose the mirror lookup position to minimize the time to find the
secondary hash location (+1 would have done that as well).  The linear
lookup after the two direct probes starts from a fixed end of the table.
The mirror position ensures that the two probe positions are at opposite
ends of the table.  

    A further modification reorders the hash table after
    unsuccessful probes in manner reminiscent of balancing n-ary trees.
    Knuth calls this "Brent's variation of Algorithm D".

Our algorithm is like Brent's variation in that it reorders the hash table
to make repeated uses of the same probe faster.    

   See the charts on pages 524 and 539.

We expect that our algorithm will be much like Brent's in behavior; with a
policy of growing the tables when they get relatively full, we hop to keep
successful lookup time close to optimal, minimizing raw instructions to do
a successful cache lookup, and maximizing the chance of a successful hit on
the first two probes.