[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

A few questions on PCL

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.