Quadratic search for hash tables of sizes P n

It has previously been claimed [1 and 2] that the quadratic hash table search method of Maurer cannot usefully be applied to tables of size 2n. This is not so; the method can in fact be applied to tables of size pn for any prime p. It is shown below that rather simple conditions on the coefficients suffice to guarantee that all table locations will be examined once and only once. Specifically, if the equation is k + bi2 + ai mod pn (*) where k is the initial hash address and 0 ≤ i < pn, then, if p divides b but not a, the range of values is all the least positive residues of pn. To prove that all values are covered, we consider some fixed value, say k + bi20 + ai0 mod pn and ask, what conditions must be true if the congruence equation k + bi2 + ai ≡ k + bi02 + ai0 mod pn is to have solutions i, 0 ≤ i < pn, other than i0?

View this article in the ACM Digital Library.