parker@psuvax1.UUCP (Bruce Parker) (03/19/86)
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@psuvax1.UUCP The Pennsylvania State University parker@penn-state.CSNET University Park, Pennsylvania 16802 parker@psuvax1.BITNET