Full Hash Table Search using Primitive Roots of the Prime Residue Group Z/p
| dc.creator | Muehlbacher,Joerg | |
| dc.date | 2004 | |
| dc.date.accessioned | 2024-02-06T12:53:11Z | |
| dc.date.available | 2024-02-06T12:53:11Z | |
| dc.description | 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. | |
| dc.format | text/html | |
| dc.identifier | https://doi.org/10.3217/jucs-010-09-1239 | |
| dc.identifier | https://lib.jucs.org/article/28295/ | |
| dc.identifier.uri | https://openrepository.mephi.ru/handle/123456789/8621 | |
| dc.language | en | |
| dc.publisher | Journal of Universal Computer Science | |
| dc.relation | info:eu-repo/semantics/altIdentifier/eissn/0948-6968 | |
| dc.relation | info:eu-repo/semantics/altIdentifier/pissn/0948-695X | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | J.UCS License | |
| dc.source | JUCS - Journal of Universal Computer Science 10(9): 1239-1249 | |
| dc.subject | hash tables | |
| dc.subject | full table scatter storage techniques | |
| dc.subject | collision strategy | |
| dc.subject | cyclic group mod p | |
| dc.subject | primitive roots of the prime residue group mod p | |
| dc.title | Full Hash Table Search using Primitive Roots of the Prime Residue Group Z/p | |
| dc.type | Research Article |