Open addressing

<h2 id="example-pseudocode">Example pseudocode</h2>
The following <a href="/facts/Pseudocode/XgN19duK">pseudocode</a> is an implementation of an open addressing hash table with linear probing and single-slot stepping, a common approach that is effective if the hash function is good. Each of the lookup, set and remove functions use a common internal function find_slot to locate the array slot that either does or should contain a given key.

record pair { key, value, occupied flag (initially unset) }
var pair slot[0], slot[1], ..., slot[num_slots - 1]

function find_slot(key)
 i := hash(key) modulo num_slots
 // search until we either find the key, or find an empty slot.
 while (slot[i] is occupied) and (slot[i].key ≠ key)
 i := (i + 1) modulo num_slots
 return i

function lookup(key)
 i := find_slot(key)
 if slot[i] is occupied // key is in table
 return slot[i].value
 else // key is not in table
 return not found

function set(key, value)
 i := find_slot(key)
 if slot[i] is occupied // we found our key
 slot[i].value := value
 return
 if the table is almost full
 rebuild the table larger (note 1)
 i := find_slot(key)
 mark slot[i] as occupied
 slot[i].key := key
 slot[i].value := value

note 1
Rebuilding the table requires allocating a larger array and recursively using the set operation to insert all the elements of the old array into the new larger array. It is common to increase the array size <a href="/facts/Exponential_growth/m4yEqKJ7">exponentially</a>, for example by doubling the old array size.
function remove(key)
 i := find_slot(key)
 if slot[i] is unoccupied
 return // key is not in the table
 mark slot[i] as unoccupied
 j := i
 loop (note 2)
 j := (j + 1) modulo num_slots
 if slot[j] is unoccupied
 exit loop
 k := hash(slot[j].key) modulo num_slots
 // determine if k lies cyclically in (i,j]
 // i ≤ j: | i..k..j |
 // i > j: |.k..j i....| or |....j i..k.|
 if i ≤ j
 if (i < k) and (k ≤ j)
 continue loop
 else
 if (k ≤ j) or (i < k)
 continue loop
 mark slot[i] as occupied
 slot[i].key := slot[j].key
 slot[i].value := slot[j].value
 mark slot[j] as unoccupied
 i := j

note 2
For all records in a cluster, there must be no vacant slots between their natural hash position and their current position (else lookups will terminate before finding the record). At this point in the pseudocode, i is a vacant slot that might be invalidating this property for subsequent records in the cluster. j is such a subsequent record. k is the raw hash where the record at j would naturally land in the hash table if there were no collisions. This test is asking if the record at j is invalidly positioned with respect to the required properties of a cluster now that i is vacant.
Another technique for removal is simply to mark the slot as deleted. However this eventually requires rebuilding the table simply to remove deleted records. The methods above provide O(1) updating and removal of existing records, with occasional rebuilding if the high-water mark of the table size grows.
The O(1) remove method above is only possible in linearly probed hash tables with single-slot stepping. In the case where many records are to be deleted in one operation, marking the slots for deletion and later rebuilding may be more efficient.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Lazy_deletion/t3J5ul8e">Lazy deletion</a> – a method of deleting from a hash table using open addressing.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Tenenbaum, Aaron M.; Langsam, Yedidyah; Augenstein, Moshe J. (1990), Data Structures Using C, Prentice Hall, pp. 456–461, pp. 472, ISBN 0-13-199746-7 <a href="0-13-199746-7" target="_blank">0-13-199746-7</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Poblete; Viola; Munro.
"The Analysis of a Hashing Scheme by the Diagonal Poisson Transform".
p. 95 of
Jan van Leeuwen (Ed.)
"Algorithms - ESA '94".
1994. <a href="https://books.google.com/books?id=2aCoW8m40AwC" target="_blank">https://books.google.com/books?id=2aCoW8m40AwC</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Steve Heller.
"Efficient C/C++ Programming: Smaller, Faster, Better"
2014.
p. 33. <a href="https://books.google.com/books?id=gaajBQAAQBAJ" target="_blank">https://books.google.com/books?id=gaajBQAAQBAJ</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Patricio V. Poblete, Alfredo Viola.
"Robin Hood Hashing really has constant average search cost and variance in full tables".
2016. <a href="https://arxiv.org/abs/1605.04031" target="_blank">https://arxiv.org/abs/1605.04031</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Paul E. Black, "Last-Come First-Served Hashing", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 September 2015. <a href="https://xlinux.nist.gov/dads/HTML/LastComeFirstServedHashing.html" target="_blank">https://xlinux.nist.gov/dads/HTML/LastComeFirstServedHashing.html</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Paul E. Black, "Robin Hood hashing", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 September 2015. <a href="https://www.nist.gov/dads/HTML/robinHoodHashing.html" target="_blank">https://www.nist.gov/dads/HTML/robinHoodHashing.html</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

Open addressing open-in-new

Open addressing