[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
A few questions on PCL
- To: kanderso@WILMA.BBN.COM
- Subject: A few questions on PCL
- From: Jim McDonald <email@example.com>
- Date: Wed, 14 Dec 88 09:12:30 PST
- Cc: firstname.lastname@example.org, commonloops.pa@Xerox.COM
- In-reply-to: kanderso@WILMA.BBN.COM's message of Tue, 13 Dec 88 21:41:18 -0500 <881213-185130-8705@Xerox>
- Redistributed: commonloops.pa
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.)
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".
See the charts on pages 524 and 539.