# Two-Way Linear Probing Revisited
## 3 The Proposal
### Hashing with Blocking
If both blocks are full and the probe sequences completely search them without finding the key, then the right neighbors of these blocks (cyclically speaking) are searched sequentially in the same way mentioned above, and so on. We will refer to this algorithm as LocallyLinear\((n,m)\) for inserting \(m\) keys into \(n\) cells. **Two-Way Pre-Linear Probing: DecideFirst Algorithm**  
In the previous two-way linear probing algorithms, each input key initiates linear probe sequences that reach two terminal cells, and then the algorithms decide in which terminal cell the key should be inserted. The following algorithm, however, allows each key to choose two initial hashing cells, and then decides, according to some strategy, which initial cell should start a linear probe sequence to find a terminal cell to harbor the key. Therefore, technically, the insertion process of any key uses only one linear probe sequence, but we still use two sequences for any search. Formally, we describe the algorithm as follows. Let \(\alpha\in(0,1)\) be the load factor. Partition the hash table into blocks of size \(\beta_{2}(n)\), where \(\beta_{2}(n)\) is an integer to be defined later. Each key \(x\) still chooses, independently and uniformly at random, two initial hashing cells, say \(I_{x}\) and \(J_{x}\), and hence, two blocks which we denote by \(\lambda(I_{x})\) and \(\lambda(J_{x})\). For convenience, we say that the key \(x\) has _handed_ in block \(i\), if the linear probe sequence used to insert the key \(x\) has started (from the initial hashing cell available for \(x\)) in block \(i\). Define the weight of a block to be the number of keys that have landed in it. We save with each block its weight and keep it updated whenever a key lands in it. Now, upon the arrival of key \(x\), the algorithm allows \(x\) to land into the block among \(\lambda(I_{x})\) and \(\lambda(J_{x})\) of smaller weight, breaking ties randomly. Whence, it starts probing linearly from the initial cell contained in the block until it finds a terminal cell into which the key \(x\) is placed. If, for example, both \(I_{x}\) and \(J_{x}\) belong to the same block, then \(x\) lands in \(\lambda(I_{x})\), and the linear sequence starts from an arbitrarily chosen cell among \(I_{x}\) and \(J_{x}\). We will write \(\textsc{DecideFirst}(n,m)\) to refer to this algorithm for inserting \(m\) keys into \(n\) cells. In short, the strategy of \(\textsc{DecideFirst}(n,m)\) as illustrated in Figure 3 is: land in the block of smaller weight, walk linearly, and insert into the first empty cell reached. **Two-Way Post-Linear Probing: WalkFirst Algorithm**  
We introduce yet another hashing algorithm that achieves \(\Theta(\log\log n)\) worst-case search time, in probability, and shows better performance in experiments than DecideFirst algorithm as demonstrated in the simulation results presented in Section 6. Suppose that the load factor \(\alpha\in(0,1/2)\), and that the hash table is divided into blocks of size  
\[\beta_{3}(n):=\left\lceil\,\frac{\log_{2}\log n+8}{1-\delta}\,\right\rceil,\]  
where \(\delta\in(2\alpha,1)\) is an arbitrary constant. Define the load of a block to be the number of keys (or occupied cells) it contains. Suppose that we save with each block its load and keep it updated whenever a key is inserted into one of its cells. Recall that each key \(x\) has two initial hashing cells. From these initial cells, the algorithm probes linearly and cyclically until it finds two empty cells \(U_{x}\) and \(V_{x}\), which we call terminal cells. Let \(\lambda(U_{x})\) and \(\lambda(V_{x})\) be the blocks that contain these cells. The algorithm, then, inserts the key \(x\) into the terminal cell (among \(U_{x}\) and \(V_{x}\)) that belongs to the least loaded block among \(\lambda(U_{x})\) and \(\lambda(V_{x})\), breaking ties randomly. We refer to this algorithm of open addressing hashing for inserting \(m\) keys into \(n\) cells as \(\textsc{WalkFirst}(n,m)\) (Figure 4).