Editing Open addressing (section)

{{Short description|Hash collision resolution technique}}
[[Image:HASHTB12.svg|thumb|362px|right|Hash collision resolved by linear probing (interval=1).]]
'''Open addressing''', or '''closed hashing''', is a method of [[Hash table#Collision resolution|collision resolution in hash tables]].  With this method a hash collision is resolved by '''probing''', or searching through alternative locations in the array (the ''probe sequence'') until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table.<ref name="tenenbaum90">{{Citation | title=Data Structures Using C | first1=Aaron M. | last1=Tenenbaum | first2=Yedidyah | last2=Langsam | first3=Moshe J. | last3=Augenstein | publisher=Prentice Hall | year=1990 | isbn=0-13-199746-7 | pages=456–461, pp. 472}}</ref> Well-known probe sequences include:

; [[Linear probing]] : in which the interval between probes is fixed — often set to 1.
; [[Quadratic probing]] : in which the interval between probes increases linearly (hence, the indices are described by a quadratic function).
; [[Double hashing]] : in which the interval between probes is fixed for each record but is computed by another hash function.

The main trade offs between these methods are that linear probing has the best [[Locality of reference|cache performance]] but is most sensitive to [[Primary clustering|clustering]], while double hashing has poor cache performance but exhibits virtually no clustering; quadratic probing falls in between in both areas. Double hashing can also require more computation than other forms of probing.

Some open addressing methods, such as [[Hopscotch hashing]], [[hash table#Robin Hood hashing | Robin Hood hashing]], [[last-come-first-served hashing]] and [[cuckoo hashing]] move existing keys around in the array to make room for the new key. This gives better maximum search times than the methods based on probing.<ref>
Poblete; Viola; Munro.
"The Analysis of a Hashing Scheme by the Diagonal Poisson Transform".
p. 95 of
Jan van Leeuwen (Ed.)
[https://books.google.com/books?id=2aCoW8m40AwC "Algorithms - ESA '94"].
1994.
</ref><ref>
Steve Heller.
[https://books.google.com/books?id=gaajBQAAQBAJ "Efficient C/C++ Programming: Smaller, Faster, Better"]
2014.
p. 33.
</ref><ref>
Patricio V. Poblete, Alfredo Viola.
[https://arxiv.org/abs/1605.04031 "Robin Hood Hashing really has constant average search cost and variance in full tables"].
2016.
</ref><ref>
Paul E. Black, [https://xlinux.nist.gov/dads/HTML/LastComeFirstServedHashing.html "Last-Come First-Served Hashing"], in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 September 2015.
</ref><ref>
Paul E. Black, [https://www.nist.gov/dads/HTML/robinHoodHashing.html "Robin Hood hashing"], in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 September 2015.
</ref>

A critical influence on performance of an open addressing hash table is the ''load factor''; that is, the proportion of the slots in the array that are used. As the load factor increases towards 100%, the number of probes that may be required to find or insert a given key rises dramatically. Once the table becomes full, probing algorithms may even fail to terminate. Even with good hash functions, load factors are normally limited to 80%. A poor hash function can exhibit poor performance even at very low load factors by generating significant clustering, especially with the simplest linear addressing method. Generally typical load factors with most open addressing methods are 50%, while [[Hash_table#Separate_chaining|separate chaining]] typically can use up to 100%.