Tomes of Delphi:
This page describes the errata for Chapter 7 of Tomes of Delphi: Algorithms and Data Structures (DADS).
Errata for Chapter 7: Hashing and Hash Tables
1. Page 231, Listing 7.2. The code for TDPJWHash will sometimes fail with a range-check error in Delphi 4, Delphi 5 and Delphi 6 and Kylix. The hex constant should be coerced to a longint:
... for i := 1 to length(aKey) do begin Hash := (Hash shl 4) + ord(aKey[i]); G := Hash and longint($F0000000); if (G <> 0) then Hash := (Hash xor (G shr 24)) xor G; end; ...
Thanks to Jim Bobo.
2. Page 246. The book mentions that the problem with quadratic probing can easily be seen with a hash table of size 11. I then blithely stated that the sequence of probes for an initial collision at item 0 would be
"0, 1, 5, 3, 8 before starting over at 0 again. We never visit slots 2, 4, 6, 7, and so on."
Absolute twaddle. I don't know why I didn't test that hypothesis properly <sigh>. I've now written a small program (dpr, pas, dfm) that demonstrates which items are visited (and, hence, which aren't) for this particular situation. It turns out that items 2, 4, 7, and 9 are never visited.
Thanks to myself.