[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: A few questions on PCL
- To: Jim McDonald <email@example.com>
- Subject: Re: A few questions on PCL
- From: Danny Bobrow <Bobrow.pa@Xerox.COM>
- Date: 14 Dec 88 13:44 PST
- Cc: kanderso@WILMA.BBN.COM, firstname.lastname@example.org, commonloops.pa@Xerox.COM
- In-reply-to: Jim McDonald <email@example.com>'s message of Wed, 14 Dec 88 09:12:30 PST
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
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.