Using 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 Golomb Rulers for Minimizing Collisions in Closed Hashing
Conference name: ASIAN - 9th Asian Computer Science Conference
Year: 2004
Pagination: 157-168
ISBN: 978-3-540-24087-7
Publisher: Springer
City: Chiang Mai, Thailand
URI/DOI: 10.1007/b103476
Organization: Blekinge Institute of Technology
Department: School of Engineering - Dept. Mathematics and Science (Sektionen för teknik – avd. för matematik och naturvetenskap)
School of Engineering S- 371 79 Karlskrona
+46 455 38 50 00
http://www.tek.bth.se/
Authors e-mail: lars.lundberg@bth.se, kamilla.klonowska@bth.se, hakan.lennerstad@bth.se, goran.gustavsson@bth.se
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: Computer Science\Computersystems
Mathematics\Discrete Mathematics
Note: Lecture Notes in Computer Science, vol 3321/2004 http://springerlink.metapress.com/content/m1e8146xjqx4/
Edit