# Two-Way Linear Probing Revisited
## 3 The Proposal  
We design linear probing algorithms that accomplish double logarithmic worst-case search time. Inspired by the two-way chaining algorithm [10] and its powerful performance, we promote the concept of open addressing hashing with two-way linear probing. The essence of the proposed concept is based on the idea of allowing each key to generate two independent linear probe sequences and making the algorithm decide, according to some strategy, at the end of which sequence the key should be inserted. Formally, each input key \(x\) chooses two cells independently and uniformly at random, with replacement. We call these cells the _initial hashing cells_ available for \(x\). From each initial hashing cell, we start a linear probe sequence (with fcFS policy) to find an empty cell where we stop. Thus, we end up with two unoccupied cells. We call these cells the _terminal hashing cells_. The question now is: into which terminal cell should we insert the key \(x\)? The insertion process of a two-way linear probing algorithm could follow one of the strategies we mentioned earlier: it may insert the key at the end of the shorter probe sequence, or into the terminal cell that is adjacent to the smaller cluster. Others may make an insertion decision even before linear probing starts. In any of these algorithms, the searching process for any key is basically the same: just start probing in both sequences alternately, until the key is found or the two empty cells at the end of the sequences are reached in the case of an unsuccessful search. Thus, the maximum unsuccessful search time is at most twice the size of the largest cluster plus two. We study the two-way linear probing algorithms stated above, and show that the hash table, asymptotically almost surely, contains a giant cluster of size \(\Omega(\log n)\). Indeed, we prove that a cluster of size \(\Omega(\log n)\) emerges, asymptotically almost surely, in any hash table of constant load factor that is constructed by a two-way linear probing algorithm that inserts any key upon arrival into the empty cell of its two initial cells whenever one of them is empty. We introduce two other two-way linear probing heuristics that lead to \(\Theta(\log\log n)\) maximum unsuccessful search times. The common idea of these heuristics is the marriage between the two-way linear probing concept and a technique we call _blocking_ where the hash table is partitioned into equal-sized blocks. These blocks are used by the algorithm to obtain some information about the keys allocation. The information is used to make better decisions about where the keys should be inserted, and hence, lead to a more even distribution of the keys. Two-way linear probing hashing has several advantages over the other proposed hashing methods mentioned above: it reduces the worst-case behavior of hashing, it requires only two hash functions, it is easy to parallelize, it is pointer-free and easy to implement, and unlike the hashing schemes proposed in [51; 58], it does not require any rearrangement of keys or rehashing. Its maximum cluster size is \(O(\log\log n)\), and its average-case performance can be at most twice the classical linear probing as shown in the simulation results. Furthermore, it is not necessary to employ perfectly random hash functions as it is known [6; 7; 8] that hash functions with a smaller degree of universality will be sufficient to implement linear probing schemes. See also [31; 32; 51; 53; 70; 76; 89] for other suggestions on practical hash functions. Throughout, we assume the following. We are given \(m\) keys--from a universe set of keys \(\mathcal{U}\)--to be hashed into a hash table of size \(n\) such that each cell contains at most one key. The process of hashing is sequential and on-line, that is, we never know anything about the future keys. The constant \(\alpha\in(0,1)\) is preserved in this article for the load factor of the hash table, that is, we assume that \(m=\lfloor\,\alpha n\,\rfloor\). The \(n\) cells of the hash table are numbered \(0,\ldots,n-1\).