ToDADS errata: Chapter 7: Hashing and Hash Tables

published: Tue, 17-Jun-2003   |   updated: Sat, 20-Aug-2016

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 (zip file) that demonstrates which items are visited (and, hence, which aren't) for this particular situation. It turns out that items 2, 6, 7, 8, and 10 are never visited.

(OK. Confession time. The book was wrong, and my first attempt at clearing up the error was also wrong since I was adding the next square in the seqeuence to the current index, instead of to the original hash. The app is now fixed. Sigh.)

Thanks to myself. Squared.