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

‡ FIM, Johannes Kepler University of Linz, Linz, Austria

Corresponding author: Joerg Muehlbacher ( muehlbacher@fim.uni-linz.ac.at ) Citation:
Muehlbacher JR (2004) Full Hash Table Search using Primitive Roots of the Prime Residue Group Z/p. JUCS - Journal of Universal Computer Science 10(9): 1239-1249. https://doi.org/10.3217/jucs-010-09-1239 |

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