Tomes of Delphi:
Algorithms and Data Structures

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.