Linear probing

<h2 id="operations">Operations</h2>
Linear probing is a component of <a href="/facts/Open_addressing/SBoALfHH">open addressing</a> schemes for using a <a href="/facts/Hash_table/Ht4ptDPF">hash table</a> to solve the <a href="/facts/Associative_array/IFGd2xcP">dictionary problem</a>. In the dictionary problem, a data structure should maintain a collection of key–value pairs subject to operations that insert or delete pairs from the collection or that search for the value associated with a given key.
In open addressing solutions to this problem, the data structure is an <a href="/facts/Array_data_structure/BKGvF8AM">array</a> T (the hash table) whose cells T[i] (when nonempty) each store a single key–value pair. A <a href="/facts/Hash_function/rk6MlCt3">hash function</a> is used to map each key into the cell of T where that key should be stored, typically scrambling the keys so that keys with similar values are not placed near each other in the table. A <a href="/facts/Hash_collision/QwAesPFG">hash collision</a> occurs when the hash function maps a key into a cell that is already occupied by a different key. Linear probing is a strategy for resolving collisions, by placing the new key into the closest following empty cell.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a><a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h3>Search</h3>
To search for a given key x, the cells of T are examined, beginning with the cell at index h(x) (where h is the hash function) and continuing to the adjacent cells h(x) + 1, h(x) + 2, ..., until finding either an empty cell or a cell whose stored key is x.
If a cell containing the key is found, the search returns the value from that cell. Otherwise, if an empty cell is found, the key cannot be in the table, because it would have been placed in that cell in preference to any later cell that has not yet been searched. In this case, the search returns as its result that the key is not present in the dictionary.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<h3>Insertion</h3>
To insert a key–value pair (x,v) into the table (possibly replacing any existing pair with the same key), the insertion algorithm follows the same sequence of cells that would be followed for a search, until finding either an empty cell or a cell whose stored key is x.
The new key–value pair is then placed into that cell.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>
If the insertion would cause the <a href="/facts/Load_factor_(computer_science)/Ht4ptDPF">load factor</a> of the table (its fraction of occupied cells) to grow above some preset threshold, the whole table may be replaced by a new table, larger by a constant factor, with a new hash function, as in a <a href="/facts/Dynamic_array/EtocbTWK">dynamic array</a>. Setting this threshold close to zero and using a high growth rate for the table size leads to faster hash table operations but greater memory usage than threshold values close to one and low growth rates. A common choice would be to double the table size when the load factor would exceed 1/2, causing the load factor to stay between 1/4 and 1/2.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>

<h3>Deletion</h3>

It is also possible to remove a key–value pair from the dictionary. However, it is not sufficient to do so by simply emptying its cell. This would affect searches for other keys that have a hash value earlier than the emptied cell, but that are stored in a position later than the emptied cell. The emptied cell would cause those searches to incorrectly report that the key is not present.
Instead, when a cell i is emptied, it is necessary to search forward through the following cells of the table until finding either another empty cell or a key that can be moved to cell i (that is, a key whose hash value is equal to or earlier than i). When an empty cell is found, then emptying cell i is safe and the deletion process terminates. But, when the search finds a key that can be moved to cell i, it performs this move. This has the effect of speeding up later searches for the moved key, but it also empties out another cell, later in the same block of occupied cells. The search for a movable key continues for the new emptied cell, in the same way, until it terminates by reaching a cell that was already empty. In this process of moving keys to earlier cells, each key is examined only once. Therefore, the time to complete the whole process is proportional to the length of the block of occupied cells containing the deleted key, matching the running time of the other hash table operations.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
Alternatively, it is possible to use a <a href="/facts/Lazy_deletion/t3J5ul8e">lazy deletion</a> strategy in which a key–value pair is removed by replacing the value by a special <a href="/facts/Sentinel_value/Ma1rxg1q">flag value</a> indicating a deleted key. However, these flag values will contribute to the load factor of the hash table. With this strategy, it may become necessary to clean the flag values out of the array and rehash all the remaining key–value pairs once too large a fraction of the array becomes occupied by deleted keys.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a><a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

<h2 id="properties">Properties</h2>
Linear probing provides good <a href="/facts/Locality_of_reference/fYFKDv5q">locality of reference</a>, which causes it to require few uncached memory accesses per operation. Because of this, for low to moderate load factors, it can provide very high performance. However, compared to some other open addressing strategies, its performance degrades more quickly at high load factors because of <a href="/facts/Primary_clustering/kw2R0ovW">primary clustering</a>, a tendency for one collision to cause more nearby collisions.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> Additionally, achieving good performance with this method requires a higher-quality hash function than for some other collision resolution schemes.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> When used with low-quality hash functions that fail to eliminate nonuniformities in the input distribution, linear probing can be slower than other open-addressing strategies such as <a href="/facts/Double_hashing/6T3g22hk">double hashing</a>, which probes a sequence of cells whose separation is determined by a second hash function, or <a href="/facts/Quadratic_probing/cXGFSdN1">quadratic probing</a>, where the size of each step varies depending on its position within the probe sequence.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>

<h2 id="analysis">Analysis</h2>
Using linear probing, dictionary operations can be implemented in constant <a href="/facts/Expected_time/6TqLIMMz">expected time</a>. In other words, insert, remove and search operations can be implemented in <a href="/facts/Big_O_notation/weFFjSWg">O(1)</a>, as long as the <a href="/facts/Load_factor_(computer_science)/Ht4ptDPF">load factor</a> of the hash table is a constant strictly less than one.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a>
In more detail, the time for any particular operation (a search, insertion, or deletion) is proportional to the length of the contiguous block of occupied cells at which the operation starts. If all starting cells are equally likely, in a hash table with N cells, then a maximal block of k occupied cells will have probability k/N of containing the starting location of a search, and will take time O(k) whenever it is the starting location. Therefore, the expected time for an operation can be calculated as the product of these two terms, O(k2/N), summed over all of the maximal blocks of contiguous cells in the table. A similar sum of squared block lengths gives the expected time bound for a random hash function (rather than for a random starting location into a specific state of the hash table), by summing over all the blocks that could exist (rather than the ones that actually exist in a given state of the table), and multiplying the term for each potential block by the probability that the block is actually occupied. That is,
defining Block(i,k) to be the event that there is a maximal contiguous block of occupied cells of length k beginning at index i, the expected time per operation is

E
        [
        T
        ]
        =
        O
        (
        1
        )
        +
        
          ∑
          
            i
            =
            1
          
          
            N
          
        
        
          ∑
          
            k
            =
            1
          
          
            n
          
        
        O
        (
        
          k
          
            2
          
        
        
          /
        
        N
        )
        Pr
        ⁡
        [
        Block
        ⁡
        (
        i
        ,
        k
        )
        ]
        .
      
    
    {\displaystyle E[T]=O(1)+\sum _{i=1}^{N}\sum _{k=1}^{n}O(k^{2}/N)\operatorname {Pr} [\operatorname {Block} (i,k)].}

This formula can be simplified by replacing Block(i,k) by a simpler necessary condition Full(k), the event that
at least k elements have hash values that lie within a block of cells of length k. After this replacement, the value within the sum no longer depends on i, and the 1/N factor cancels the N terms of the outer summation. These simplifications lead to the bound

E
        [
        T
        ]
        ≤
        O
        (
        1
        )
        +
        
          ∑
          
            k
            =
            1
          
          
            n
          
        
        O
        (
        
          k
          
            2
          
        
        )
        Pr
        ⁡
        [
        Full
        ⁡
        (
        k
        )
        ]
        .
      
    
    {\displaystyle E[T]\leq O(1)+\sum _{k=1}^{n}O(k^{2})\operatorname {Pr} [\operatorname {Full} (k)].}

But by the multiplicative form of the <a href="/facts/Chernoff_bound/RLC6VlRU">Chernoff bound</a>, when the load factor is bounded away from one, the probability that a block of length k contains at least k hashed values is exponentially small as a function of k,
causing this sum to be bounded by a constant independent of n.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a> It is also possible to perform the same analysis using <a href="/facts/Stirling%27s_approximation/GfxV3BUH">Stirling's approximation</a> instead of the Chernoff bound to estimate the probability that a block contains exactly k hashed values.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a><a class="footnote-ref" id="fnref:19" href="#fn:19">19</a>
In terms of the load factor α, the expected time to perform a successful search on a random key is O(1 + 1/(1 − α)), and the expected time to perform an unsuccessful search (or the insertion of a new key) is O(1 + 1/(1 − α)2).<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a>
For constant load factors, with high probability, the longest probe sequence (among the probe sequences for all keys stored in the table) has logarithmic length.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a>

<h2 id="primary-clustering">Primary Clustering</h2>
Main article: <a href="/facts/Primary_clustering/kw2R0ovW">Primary clustering</a>
Linear probing hash tables suffer from a problem known as <a href="/facts/Primary_clustering/kw2R0ovW">primary clustering</a>, in which elements to group together into long contiguous runs.<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a><a class="footnote-ref" id="fnref:23" href="#fn:23">23</a> In terms of the load factor α, the expected length of the run containing a given element is 
 
 
 
 Θ
 (
 1
 +
 1
 
 /
 
 (
 1
 −
 α
 
 )
 
 2
 
 
 )
 
 
 {\displaystyle \Theta (1+1/(1-\alpha )^{2})}
 
.<a class="footnote-ref" id="fnref:24" href="#fn:24">24</a> This is why insertions take time 
 
 
 
 Θ
 (
 1
 +
 1
 
 /
 
 (
 1
 −
 α
 
 )
 
 2
 
 
 )
 
 
 {\displaystyle \Theta (1+1/(1-\alpha )^{2})}
 
, as opposed to the running time of 
 
 
 
 Θ
 (
 1
 +
 1
 
 /
 
 (
 1
 −
 α
 )
 )
 
 
 {\displaystyle \Theta (1+1/(1-\alpha ))}
 
 achieved by other <a href="/facts/Open_addressing/SBoALfHH">open-addressed</a> hash tables such as uniform probing and <a href="/facts/Double_hashing/6T3g22hk">double hashing</a>.<a class="footnote-ref" id="fnref:25" href="#fn:25">25</a> Primary clustering also affects unsuccessful searches, since like insertions, they must travel to the end of a run.<a class="footnote-ref" id="fnref:26" href="#fn:26">26</a> Some variations of linear probing are able to achieve better bounds for unsuccessful searches and insertions, by using techniques that reduce primary clustering.<a class="footnote-ref" id="fnref:27" href="#fn:27">27</a>

<h2 id="choice-of-hash-function">Choice of hash function</h2>
Because linear probing is especially sensitive to unevenly distributed hash values,<a class="footnote-ref" id="fnref:28" href="#fn:28">28</a> it is important to combine it with a high-quality hash function that does not produce such irregularities.
The analysis above assumes that each key's hash is a random number independent of the hashes of all the other keys. This assumption is unrealistic for most applications of hashing.
However, random or <a href="/facts/Pseudorandom/kfs1wfhY">pseudorandom</a> hash values may be used when hashing objects by their identity rather than by their value. For instance, this is done using linear probing by the IdentityHashMap class of the <a href="/facts/Java_collections_framework/fKaKJtIA">Java collections framework</a>.<a class="footnote-ref" id="fnref:29" href="#fn:29">29</a>
The hash value that this class associates with each object, its identityHashCode, is guaranteed to remain fixed for the lifetime of an object but is otherwise arbitrary.<a class="footnote-ref" id="fnref:30" href="#fn:30">30</a> Because the identityHashCode is constructed only once per object, and is not required to be related to the object's address or value, its construction may involve slower computations such as the call to a random or <a href="/facts/Pseudorandom_number_generator/sIrCxIBq">pseudorandom number generator</a>. For instance, Java 8 uses an <a href="/facts/Xorshift/N6cr5Tfw">Xorshift</a> pseudorandom number generator to construct these values.<a class="footnote-ref" id="fnref:31" href="#fn:31">31</a>
For most applications of hashing, it is necessary to compute the hash function for each value every time that it is hashed, rather than once when its object is created. In such applications, random or pseudorandom numbers cannot be used as hash values, because then different objects with the same value would have different hashes. And <a href="/facts/Cryptographic_hash_function/cuxkgbST">cryptographic hash functions</a> (which are designed to be computationally indistinguishable from truly random functions) are usually too slow to be used in hash tables.<a class="footnote-ref" id="fnref:32" href="#fn:32">32</a> Instead, other methods for constructing hash functions have been devised. These methods compute the hash function quickly, and can be proven to work well with linear probing. In particular, linear probing has been analyzed from the framework of <a href="/facts/K-independent_hashing/xRDnzsPa">k-independent hashing</a>, a class of hash functions that are initialized from a small random seed and that are equally likely to map any k-tuple of distinct keys to any k-tuple of indexes. The parameter k can be thought of as a measure of hash function quality: the larger k is, the more time it will take to compute the hash function but it will behave more similarly to completely random functions.
For linear probing, 5-independence is enough to guarantee constant expected time per operation,<a class="footnote-ref" id="fnref:33" href="#fn:33">33</a>
while some 4-independent hash functions perform badly, taking up to logarithmic time per operation.<a class="footnote-ref" id="fnref:34" href="#fn:34">34</a>
Another method of constructing hash functions with both high quality and practical speed is <a href="/facts/Tabulation_hashing/XIK2xu0D">tabulation hashing</a>. In this method, the hash value for a key is computed by using each byte of the key as an index into a table of random numbers (with a different table for each byte position). The numbers from those table cells are then combined by a bitwise <a href="/facts/Exclusive_or/FHyr7hGQ">exclusive or</a> operation. Hash functions constructed this way are only 3-independent. Nevertheless, linear probing using these hash functions takes constant expected time per operation.<a class="footnote-ref" id="fnref:35" href="#fn:35">35</a><a class="footnote-ref" id="fnref:36" href="#fn:36">36</a> Both tabulation hashing and standard methods for generating 5-independent hash functions are limited to keys that have a fixed number of bits. To handle <a href="/facts/String_(computer_science)/4ChJu5WS">strings</a> or other types of variable-length keys, it is possible to <a href="/facts/Function_composition_(computer_science)/HMADGqKA">compose</a> a simpler <a href="/facts/Universal_hashing/NICffew4">universal hashing</a> technique that maps the keys to intermediate values and a higher quality (5-independent or tabulation) hash function that maps the intermediate values to hash table indices.<a class="footnote-ref" id="fnref:37" href="#fn:37">37</a><a class="footnote-ref" id="fnref:38" href="#fn:38">38</a>
In an experimental comparison, Richter et al. found that the Multiply-Shift family of hash functions (defined as 
 
 
 
 
 h
 
 z
 
 
 (
 x
 )
 =
 (
 x
 ⋅
 z
 
 
 mod
 
 2
 
 
 
 w
 
 
 )
 ÷
 
 2
 
 w
 −
 d
 
 
 
 
 {\displaystyle h_{z}(x)=(x\cdot z{\bmod {2}}^{w})\div 2^{w-d}}
 
) was "the fastest hash function when integrated with all hashing schemes, i.e., producing the highest throughputs and also of good quality" whereas tabulation hashing produced "the lowest throughput".<a class="footnote-ref" id="fnref:39" href="#fn:39">39</a>
They point out that each table look-up require several cycles, being more expensive than simple arithmetic operations. They also found <a href="/facts/MurmurHash/87wWyb3F">MurmurHash</a> to be superior than tabulation hashing: "By studying the results provided by Mult and Murmur, we think that the trade-off for by tabulation (...) is less attractive in practice".

<h2 id="history">History</h2>
The idea of an <a href="/facts/Associative_array/IFGd2xcP">associative array</a> that allows data to be accessed by its value rather than by its address dates back to the mid-1940s in the work of <a href="/facts/Konrad_Zuse/yrvbaEg3">Konrad Zuse</a> and <a href="/facts/Vannevar_Bush/F12rLyGQ">Vannevar Bush</a>,<a class="footnote-ref" id="fnref:40" href="#fn:40">40</a> but hash tables were not described until 1953, in an IBM memorandum by <a href="/facts/Hans_Peter_Luhn/j5zx9csm">Hans Peter Luhn</a>. Luhn used a different collision resolution method, chaining, rather than linear probing.<a class="footnote-ref" id="fnref:41" href="#fn:41">41</a>
<a href="/facts/Donald_Knuth/GozNzDM6">Knuth</a> (1963) summarizes the early history of linear probing. It was the first open addressing method, and was originally synonymous with open addressing. According to Knuth, it was first used by <a href="/facts/Gene_Amdahl/u83Qhvdw">Gene Amdahl</a>, <a href="/facts/Elaine_M._McGraw/VPGWDX8Y">Elaine M. McGraw</a> (née Boehme), and <a href="/facts/Arthur_Samuel_(computer_scientist)/hjG9AfX2">Arthur Samuel</a> in 1954, in an <a href="/facts/Assembly_language/7XuV0cla">assembler</a> program for the <a href="/facts/IBM_701/6ngzwkFp">IBM 701</a> computer.<a class="footnote-ref" id="fnref:42" href="#fn:42">42</a> The first published description of linear probing is by Peterson (1957),<a class="footnote-ref" id="fnref:43" href="#fn:43">43</a> who also credits Samuel, Amdahl, and Boehme but adds that "the system is so natural, that it very likely may have been conceived independently by others either before or since that time".<a class="footnote-ref" id="fnref:44" href="#fn:44">44</a> Another early publication of this method was by Soviet researcher <a href="/facts/Andrey_Ershov/z2B4LyoI">Andrey Ershov</a>, in 1958.<a class="footnote-ref" id="fnref:45" href="#fn:45">45</a>
The first theoretical analysis of linear probing, showing that it takes constant expected time per operation with random hash functions, was given by Knuth.<a class="footnote-ref" id="fnref:46" href="#fn:46">46</a> <a href="/facts/Robert_Sedgewick_(computer_scientist)/f1lY2MFL">Sedgewick</a> calls Knuth's work "a landmark in the analysis of algorithms".<a class="footnote-ref" id="fnref:47" href="#fn:47">47</a> Significant later developments include a more detailed analysis of the <a href="/facts/Probability_distribution/EpsKKVRu">probability distribution</a> of the running time,<a class="footnote-ref" id="fnref:48" href="#fn:48">48</a><a class="footnote-ref" id="fnref:49" href="#fn:49">49</a> and the proof that linear probing runs in constant time per operation with practically usable hash functions rather than with the idealized random functions assumed by earlier analysis.<a class="footnote-ref" id="fnref:50" href="#fn:50">50</a><a class="footnote-ref" id="fnref:51" href="#fn:51">51</a>

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

<ol>
<li id="fn:1">Thorup, Mikkel; Zhang, Yin (2012), "Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation", SIAM Journal on Computing, 41 (2): 293–331, doi:10.1137/100800774, MR 2914329 <a href="/wiki/Mikkel_Thorup" target="_blank">/wiki/Mikkel_Thorup</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Richter, Stefan; Alvarez, Victor; Dittrich, Jens (2015), "A seven-dimensional analysis of hashing methods and its implications on query processing" (PDF), Proceedings of the VLDB Endowment, 9 (3): 293–331, doi:10.14778/2850583.2850585 <a href="http://www.vldb.org/pvldb/vol9/p96-richter.pdf" target="_blank">http://www.vldb.org/pvldb/vol9/p96-richter.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Goodrich, Michael T.; Tamassia, Roberto (2015), "Section 6.3.3: Linear Probing", Algorithm Design and Applications, Wiley, pp. 200–203 <a href="/wiki/Michael_T._Goodrich" target="_blank">/wiki/Michael_T._Goodrich</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Morin, Pat (February 22, 2014), "Section 5.2: LinearHashTable: Linear Probing", Open Data Structures (in pseudocode) (0.1Gβ ed.), pp. 108–116, retrieved 2016-01-15 <a href="/wiki/Pat_Morin" target="_blank">/wiki/Pat_Morin</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Goodrich, Michael T.; Tamassia, Roberto (2015), "Section 6.3.3: Linear Probing", Algorithm Design and Applications, Wiley, pp. 200–203 <a href="/wiki/Michael_T._Goodrich" target="_blank">/wiki/Michael_T._Goodrich</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Morin, Pat (February 22, 2014), "Section 5.2: LinearHashTable: Linear Probing", Open Data Structures (in pseudocode) (0.1Gβ ed.), pp. 108–116, retrieved 2016-01-15 <a href="/wiki/Pat_Morin" target="_blank">/wiki/Pat_Morin</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Goodrich, Michael T.; Tamassia, Roberto (2015), "Section 6.3.3: Linear Probing", Algorithm Design and Applications, Wiley, pp. 200–203 <a href="/wiki/Michael_T._Goodrich" target="_blank">/wiki/Michael_T._Goodrich</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Morin, Pat (February 22, 2014), "Section 5.2: LinearHashTable: Linear Probing", Open Data Structures (in pseudocode) (0.1Gβ ed.), pp. 108–116, retrieved 2016-01-15 <a href="/wiki/Pat_Morin" target="_blank">/wiki/Pat_Morin</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Sedgewick, Robert; Wayne, Kevin (2011), Algorithms (4th ed.), Addison-Wesley Professional, p. 471, ISBN 9780321573513. Sedgewick and Wayne also halve the table size when a deletion would cause the load factor to become too low, causing them to use a wider range [1/8,1/2] in the possible values of the load factor. <a href="9780321573513" target="_blank">9780321573513</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Goodrich, Michael T.; Tamassia, Roberto (2015), "Section 6.3.3: Linear Probing", Algorithm Design and Applications, Wiley, pp. 200–203 <a href="/wiki/Michael_T._Goodrich" target="_blank">/wiki/Michael_T._Goodrich</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Goodrich, Michael T.; Tamassia, Roberto (2015), "Section 6.3.3: Linear Probing", Algorithm Design and Applications, Wiley, pp. 200–203 <a href="/wiki/Michael_T._Goodrich" target="_blank">/wiki/Michael_T._Goodrich</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Morin, Pat (February 22, 2014), "Section 5.2: LinearHashTable: Linear Probing", Open Data Structures (in pseudocode) (0.1Gβ ed.), pp. 108–116, retrieved 2016-01-15 <a href="/wiki/Pat_Morin" target="_blank">/wiki/Pat_Morin</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Goodrich, Michael T.; Tamassia, Roberto (2015), "Section 6.3.3: Linear Probing", Algorithm Design and Applications, Wiley, pp. 200–203 <a href="/wiki/Michael_T._Goodrich" target="_blank">/wiki/Michael_T._Goodrich</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Pătraşcu, Mihai; Thorup, Mikkel (2010), "On the k-independence required by linear probing and minwise independence" (PDF), Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6–10, 2010, Proceedings, Part I, Lecture Notes in Computer Science, vol. 6198, Springer, pp. 715–726, arXiv:1302.5127, doi:10.1007/978-3-642-14165-2_60 <a href="/wiki/Mihai_P%C4%83tra%C8%99cu_(computer_scientist)" target="_blank">/wiki/Mihai_P%C4%83tra%C8%99cu_(computer_scientist)</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Heileman, Gregory L.; Luo, Wenbin (2005), "How caching affects hashing" (PDF), Seventh Workshop on Algorithm Engineering and Experiments (ALENEX 2005), pp. 141–154 <a href="http://www.siam.org/meetings/alenex05/papers/13gheileman.pdf" target="_blank">http://www.siam.org/meetings/alenex05/papers/13gheileman.pdf</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Knuth, Donald (1963), Notes on "Open" Addressing, archived from the original on 2016-03-03 <a href="/wiki/Donald_Knuth" target="_blank">/wiki/Donald_Knuth</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Goodrich, Michael T.; Tamassia, Roberto (2015), "Section 6.3.3: Linear Probing", Algorithm Design and Applications, Wiley, pp. 200–203 <a href="/wiki/Michael_T._Goodrich" target="_blank">/wiki/Michael_T._Goodrich</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Morin, Pat (February 22, 2014), "Section 5.2: LinearHashTable: Linear Probing", Open Data Structures (in pseudocode) (0.1Gβ ed.), pp. 108–116, retrieved 2016-01-15 <a href="/wiki/Pat_Morin" target="_blank">/wiki/Pat_Morin</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Eppstein, David (October 13, 2011), "Linear probing made easy", 0xDE <a href="/wiki/David_Eppstein" target="_blank">/wiki/David_Eppstein</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Sedgewick, Robert (2003), "Section 14.3: Linear Probing", Algorithms in Java, Parts 1–4: Fundamentals, Data Structures, Sorting, Searching (3rd ed.), Addison Wesley, pp. 615–620, ISBN 9780321623973 <a href="9780321623973" target="_blank">9780321623973</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Pittel, B. (1987), "Linear probing: the probable largest search time grows logarithmically with the number of records", Journal of Algorithms, 8 (2): 236–249, doi:10.1016/0196-6774(87)90040-X, MR 0890874 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Cormen, Thomas H.; Leiserson, Charles Eric; Rivest, Ronald Linn; Stein, Clifford (2009). Introduction to algorithms (3rd ed.). Cambridge, Massachusetts London, England: MIT Press. ISBN 978-0-262-53305-8. <a href="978-0-262-53305-8" target="_blank">978-0-262-53305-8</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Sedgewick, Robert (2003), "Section 14.3: Linear Probing", Algorithms in Java, Parts 1–4: Fundamentals, Data Structures, Sorting, Searching (3rd ed.), Addison Wesley, pp. 615–620, ISBN 9780321623973 <a href="9780321623973" target="_blank">9780321623973</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Sedgewick, Robert (2003), "Section 14.3: Linear Probing", Algorithms in Java, Parts 1–4: Fundamentals, Data Structures, Sorting, Searching (3rd ed.), Addison Wesley, pp. 615–620, ISBN 9780321623973 <a href="9780321623973" target="_blank">9780321623973</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">Sedgewick, Robert (2003), "Section 14.3: Linear Probing", Algorithms in Java, Parts 1–4: Fundamentals, Data Structures, Sorting, Searching (3rd ed.), Addison Wesley, pp. 615–620, ISBN 9780321623973 <a href="9780321623973" target="_blank">9780321623973</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">Sedgewick, Robert (2003), "Section 14.3: Linear Probing", Algorithms in Java, Parts 1–4: Fundamentals, Data Structures, Sorting, Searching (3rd ed.), Addison Wesley, pp. 615–620, ISBN 9780321623973 <a href="9780321623973" target="_blank">9780321623973</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
<li id="fn:27">Bender, Michael A.; Kuszmaul, Bradley C.; Kuszmaul, William (2022). "Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering". 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE. pp. 1171–1182. doi:10.1109/focs52979.2021.00115. ISBN 978-1-6654-2055-6. S2CID 260502788. <a href="978-1-6654-2055-6" target="_blank">978-1-6654-2055-6</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></li>
<li id="fn:28">Heileman, Gregory L.; Luo, Wenbin (2005), "How caching affects hashing" (PDF), Seventh Workshop on Algorithm Engineering and Experiments (ALENEX 2005), pp. 141–154 <a href="http://www.siam.org/meetings/alenex05/papers/13gheileman.pdf" target="_blank">http://www.siam.org/meetings/alenex05/papers/13gheileman.pdf</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></li>
<li id="fn:29">"IdentityHashMap", Java SE 7 Documentation, Oracle, retrieved 2016-01-15 <a href="https://docs.oracle.com/javase/7/docs/api/java/util/IdentityHashMap.html" target="_blank">https://docs.oracle.com/javase/7/docs/api/java/util/IdentityHashMap.html</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></li>
<li id="fn:30">Friesen, Jeff (2012), Beginning Java 7, Expert's voice in Java, Apress, p. 376, ISBN 9781430239109 <a href="9781430239109" target="_blank">9781430239109</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></li>
<li id="fn:31">Kabutz, Heinz M. (September 9, 2014), "Identity Crisis", The Java Specialists' Newsletter, 222 <a href="http://www.javaspecialists.eu/archive/Issue222.html" target="_blank">http://www.javaspecialists.eu/archive/Issue222.html</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></li>
<li id="fn:32">Weiss, Mark Allen (2014), "Chapter 3: Data Structures", in Gonzalez, Teofilo; Diaz-Herrera, Jorge; Tucker, Allen (eds.), Computing Handbook, vol. 1 (3rd ed.), CRC Press, p. 3-11, ISBN 9781439898536. <a href="9781439898536" target="_blank">9781439898536</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></li>
<li id="fn:33">Pagh, Anna; Pagh, Rasmus; Ružić, Milan (2009), "Linear probing with constant independence", SIAM Journal on Computing, 39 (3): 1107–1120, arXiv:cs/0612055, doi:10.1137/070702278, MR 2538852 <a href="/wiki/Rasmus_Pagh" target="_blank">/wiki/Rasmus_Pagh</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></li>
<li id="fn:34">Pătraşcu, Mihai; Thorup, Mikkel (2010), "On the k-independence required by linear probing and minwise independence" (PDF), Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6–10, 2010, Proceedings, Part I, Lecture Notes in Computer Science, vol. 6198, Springer, pp. 715–726, arXiv:1302.5127, doi:10.1007/978-3-642-14165-2_60 <a href="/wiki/Mihai_P%C4%83tra%C8%99cu_(computer_scientist)" target="_blank">/wiki/Mihai_P%C4%83tra%C8%99cu_(computer_scientist)</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></li>
<li id="fn:35">Morin, Pat (February 22, 2014), "Section 5.2: LinearHashTable: Linear Probing", Open Data Structures (in pseudocode) (0.1Gβ ed.), pp. 108–116, retrieved 2016-01-15 <a href="/wiki/Pat_Morin" target="_blank">/wiki/Pat_Morin</a> <a href="#fnref:35" class="footnote-back-ref">↩</a></li>
<li id="fn:36">Pătraşcu, Mihai; Thorup, Mikkel (2011), "The power of simple tabulation hashing", Proceedings of the 43rd annual ACM Symposium on Theory of Computing (STOC '11), pp. 1–10, arXiv:1011.5200, doi:10.1145/1993636.1993638, S2CID 195776653 <a href="/wiki/Mihai_P%C4%83tra%C8%99cu_(computer_scientist)" target="_blank">/wiki/Mihai_P%C4%83tra%C8%99cu_(computer_scientist)</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></li>
<li id="fn:37">Thorup, Mikkel; Zhang, Yin (2012), "Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation", SIAM Journal on Computing, 41 (2): 293–331, doi:10.1137/100800774, MR 2914329 <a href="/wiki/Mikkel_Thorup" target="_blank">/wiki/Mikkel_Thorup</a> <a href="#fnref:37" class="footnote-back-ref">↩</a></li>
<li id="fn:38">Thorup, Mikkel (2009), "String hashing for linear probing", Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA: SIAM, pp. 655–664, CiteSeerX 10.1.1.215.4253, doi:10.1137/1.9781611973068.72, MR 2809270 <a href="/wiki/Mikkel_Thorup" target="_blank">/wiki/Mikkel_Thorup</a> <a href="#fnref:38" class="footnote-back-ref">↩</a></li>
<li id="fn:39">Richter, Stefan; Alvarez, Victor; Dittrich, Jens (2015), "A seven-dimensional analysis of hashing methods and its implications on query processing" (PDF), Proceedings of the VLDB Endowment, 9 (3): 293–331, doi:10.14778/2850583.2850585 <a href="http://www.vldb.org/pvldb/vol9/p96-richter.pdf" target="_blank">http://www.vldb.org/pvldb/vol9/p96-richter.pdf</a> <a href="#fnref:39" class="footnote-back-ref">↩</a></li>
<li id="fn:40">Parhami, Behrooz (2006), Introduction to Parallel Processing: Algorithms and Architectures, Series in Computer Science, Springer, 4.1 Development of early models, p. 67, ISBN 9780306469640 <a href="9780306469640" target="_blank">9780306469640</a> <a href="#fnref:40" class="footnote-back-ref">↩</a></li>
<li id="fn:41">Morin, Pat (2004), "Hash tables", in Mehta, Dinesh P.; Sahni, Sartaj (eds.), Handbook of Data Structures and Applications, Chapman & Hall / CRC, p. 9-15, ISBN 9781420035179. <a href="9781420035179" target="_blank">9781420035179</a> <a href="#fnref:41" class="footnote-back-ref">↩</a></li>
<li id="fn:42">Knuth, Donald (1963), Notes on "Open" Addressing, archived from the original on 2016-03-03 <a href="/wiki/Donald_Knuth" target="_blank">/wiki/Donald_Knuth</a> <a href="#fnref:42" class="footnote-back-ref">↩</a></li>
<li id="fn:43">Knuth, Donald (1963), Notes on "Open" Addressing, archived from the original on 2016-03-03 <a href="/wiki/Donald_Knuth" target="_blank">/wiki/Donald_Knuth</a> <a href="#fnref:43" class="footnote-back-ref">↩</a></li>
<li id="fn:44">Peterson, W. W. (April 1957), "Addressing for random-access storage", IBM Journal of Research and Development, 1 (2), Riverton, NJ, USA: IBM Corp.: 130–146, doi:10.1147/rd.12.0130 <a href="/wiki/W._Wesley_Peterson" target="_blank">/wiki/W._Wesley_Peterson</a> <a href="#fnref:44" class="footnote-back-ref">↩</a></li>
<li id="fn:45">Ershov, A. P. (1958), "On Programming of Arithmetic Operations", Communications of the ACM, 1 (8): 3–6, doi:10.1145/368892.368907, S2CID 15986378. Translated from Doklady AN USSR 118 (3): 427–430, 1958, by Morris D. Friedman. Linear probing is described as algorithm A2. <a href="/wiki/Andrey_Ershov" target="_blank">/wiki/Andrey_Ershov</a> <a href="#fnref:45" class="footnote-back-ref">↩</a></li>
<li id="fn:46">Knuth, Donald (1963), Notes on "Open" Addressing, archived from the original on 2016-03-03 <a href="/wiki/Donald_Knuth" target="_blank">/wiki/Donald_Knuth</a> <a href="#fnref:46" class="footnote-back-ref">↩</a></li>
<li id="fn:47">Sedgewick, Robert (2003), "Section 14.3: Linear Probing", Algorithms in Java, Parts 1–4: Fundamentals, Data Structures, Sorting, Searching (3rd ed.), Addison Wesley, pp. 615–620, ISBN 9780321623973 <a href="9780321623973" target="_blank">9780321623973</a> <a href="#fnref:47" class="footnote-back-ref">↩</a></li>
<li id="fn:48">Flajolet, P.; Poblete, P.; Viola, A. (1998), "On the analysis of linear probing hashing" (PDF), Algorithmica, 22 (4): 490–515, doi:10.1007/PL00009236, MR 1701625, S2CID 5436036 <a href="/wiki/Philippe_Flajolet" target="_blank">/wiki/Philippe_Flajolet</a> <a href="#fnref:48" class="footnote-back-ref">↩</a></li>
<li id="fn:49">Knuth, D. E. (1998), "Linear probing and graphs", Algorithmica, 22 (4): 561–568, arXiv:cs/9801103, doi:10.1007/PL00009240, MR 1701629, S2CID 12254909 <a href="/wiki/Donald_Knuth" target="_blank">/wiki/Donald_Knuth</a> <a href="#fnref:49" class="footnote-back-ref">↩</a></li>
<li id="fn:50">Pagh, Anna; Pagh, Rasmus; Ružić, Milan (2009), "Linear probing with constant independence", SIAM Journal on Computing, 39 (3): 1107–1120, arXiv:cs/0612055, doi:10.1137/070702278, MR 2538852 <a href="/wiki/Rasmus_Pagh" target="_blank">/wiki/Rasmus_Pagh</a> <a href="#fnref:50" class="footnote-back-ref">↩</a></li>
<li id="fn:51">Pătraşcu, Mihai; Thorup, Mikkel (2011), "The power of simple tabulation hashing", Proceedings of the 43rd annual ACM Symposium on Theory of Computing (STOC '11), pp. 1–10, arXiv:1011.5200, doi:10.1145/1993636.1993638, S2CID 195776653 <a href="/wiki/Mihai_P%C4%83tra%C8%99cu_(computer_scientist)" target="_blank">/wiki/Mihai_P%C4%83tra%C8%99cu_(computer_scientist)</a> <a href="#fnref:51" class="footnote-back-ref">↩</a></li>
</ol>

Linear probing open-in-new

Linear probing