ld "bug" (quadratic hashing)

[Bruce Parker]

Ld claims that quadratic rehash searches only half the
address space.  This was observed by Maurer ("An Improved
Hash Code for Scatter Storage", CACM 11:1 (January 1968),
35-38).  As a result, 'ld' doubles the symbol table size,
leaving half the entries empty.

However, two years later, Radke showed how to overcome this
difficulty by letting the table size be a prime of the form
4j + 3 for some integer j.  As well ld's probe sequence needs
to be modified to use alternate signs:

	h(K),  h(K) + 1, h(K) - 1, h(K) + 4, h(K) - 4, ...

or more generally
		       2	   2
	h(K),  h(K) + i ,  h(K) - i

where 1 <= i <= ( M - 1 ) / 2, where M is the hash table size.
For more details, see "The use of quadratic residue search",
CACM 13:2 (February 1970), 103-105.

Of course, the only benefit of this would be to halve the
symbol table size, so it's not clear that anyone should care
about this.  However, it seems sad that most folks who've
taken a decent data structures course in the past 16 years
would know better than to implement quadratic hashing this
way.

Bruce Parker
Computer Science Department		(814) 863-0024
107 Whitmore Lab			parker at psuvax1.UUCP
The Pennsylvania State University	parker at penn-state.CSNET
University Park, Pennsylvania 16802	parker at psuvax1.BITNET