Using optimal Golomb rulers for minimizing collisions in closed hashing

Document type: Conference Papers
Peer reviewed: Yes
Author(s): Lars Lundberg, Håkan Lennerstad, Kamilla Klonowska, Göran Gustafsson
Title: Using optimal Golomb rulers for minimizing collisions in closed hashing
Conference name: 9th Asian Computing Science Conference
Year: 2004
Volume: 3321
Pagination: 157-168
ISBN: 3-540-24087-X
City: Chiang Mai, THAILAND
ISI number: 000226160400011
Organization: Blekinge Institute of Technology
Department: School of Engineering - Dept. Mathematics and Science, School of Engineering - Dept. of Systems and Software Engineering (Sektionen för teknik – avd. för matematik och naturvetenskap, Sektionen för teknik – avd. för programvarusystem)
School of Engineering S- 371 79 Karlskrona, School of Engineering S- 372 25 Ronneby
+46 455 38 50 00
Language: English
Abstract: We give conditions for hash table probing which minimize the expected number of collisions. A probing algorithm is determined by a sequence of numbers denoting jumps for an item during multiple collisions. In linear probing, this sequence consists of only ones - for each collision we jump to the next location. To minimize the collisions, it turns out that one should use the Golomb ruler conditions: consecutive partial sums of the jump sequence should be distinct. The commonly used quadratic probing scheme fulfils the Golomb condition for some cases. We define a new probing scheme - Golomb probing that fulfills the Golomb conditions for a much larger set of cases. Simulations show that Golomb probing is always better than quadratic and linear and in some cases the collisions can be reduced with 25% compared to quadratic and with more than 50% compared to linear.
Subject: Software Engineering\General