Full Hash Table Search using Primitive Roots of the Prime Residue Group Z/p

Joerg R. Muehlbacher (FIM, Johannes Kepler University of Linz, Austria)

Abstract: After a brief introduction to hash-coding (scatter storage) and discussion of methods described in the literature, it is shown that for hash tables of length p > 2, prime, the primitive roots r of the cyclic group Z/p of prime residues mod p can be used for a simple collision strategy q(p,i) = rⁱ mod p for fi(k) = f0(k) + q(p,i) mod p. It is similar to the strategy which uses quadratic residues q(p,i) = i² mod p in avoiding secondary clustering, but reaches all table positions for probing. A table of n primes for typical table lengths and their primitive roots is added. In cases where r = 2^j is such a primitive root, the collision strategy can be implemented simply by repeated shifts to the left (by j places in all). To make the paper self-contained and easy to read, the relevant definitions and the theorems used from the Theory of Numbers are included in the paper.

Keywords: collision strategy, cyclic group mod p, full table scatter storage techniques, hash tables, primitive roots of the prime residue group mod p

Categories: E.2, G.4