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

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

muehlbacher@fim.uni-linz.ac.at

**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^{i}
mod p for f_{i}(k) = f_{0}(k) + q(p,i) mod p. It is similar to
the strategy which uses quadratic residues q(p,i) = i^{2} 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.

J.UCS -
Journal of Universal Computer Science, Vol.10 (2004), Issue 9