JUCS - Journal of Universal Computer Science 10(9): 1239-1249, doi: 10.3217/jucs-010-09-1239
Full Hash Table Search using Primitive Roots of the Prime Residue Group Z/p
expand article infoJoerg R. Muehlbacher
‡ FIM, Johannes Kepler University of Linz, Linz, Austria
Open Access
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) = ri 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) = i2 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 = 2j 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
hash tables, full table scatter storage techniques, collision strategy, cyclic group mod p, primitive roots of the prime residue group mod p