# Two-Way Linear Probing Revisited
## 3 The Proposal
### Hashing with Blocking  
The hash table is partitioned into equal-sized disjoint blocks of cells. Whenever a key has two terminal cells, the algorithm considers the information provided by the blocks, e.g., the number of keys it harbors, to make a decision. Thus, the blocking technique enables the algorithm to avoid some of the bad decisions the previous algorithms make. This leads to a more controlled allocation process, and hence, to a more even distribution of the keys. We use the blocking technique to design two two-way linear probing algorithms, and an algorithm that uses linear probing locally within each block. The algorithms are characterized by the way the keys pick their blocks to land in. The worst-case performance of these algorithms is analyzed in Section 5 and proven to be \(O(\log\log n)\), w.h.p. Note also that (for insertion operations only) the algorithms require a counter with each block, but the extra space consumed by these counters is asymptotically negligible. In fact, we will see that the extra space is \(O(n/\log\log n)\) in a model in which integers take \(O(1)\) space, and at worst \(O(n\log\log\log n/\log\log n)=o(n)\) units of memory, w.h.p., in a bit model. Figure 1: An illustration of algorithm ShortSeq\((n,m)\) in terms of balls (keys) and bins (cells). Each ball is inserted into the empty bin found by the shorter sequence. Figure 2: Algorithm SmallCluster\((n,m)\) inserts each key into the empty cell adjacent to the smaller cluster, breaking ties randomly. The size of the clusters is determined by probing linearly in both directions. Since the block size for each of the following algorithms is different, we assume throughout and without loss of generality that, whenever we use a block of size \(\beta\), then \(n/\beta\) is an integer. Recall that the cells are numbered \(0,\ldots,n-1\), and hence, for \(i\in\left[\! [n/\beta]\!\right]\), the \(i\)-th block consists of the cells \((i-1)\beta,\ldots,i\beta-1\). In other words, the cell \(k\in\{0,\ldots,n-1\}\) belongs to block number \(\lambda(k):=\lfloor k/\beta\rfloor+1\). **Two-Way Locally Linear Probing: LocallyLinear Algorithm**  
As a simple example of the blocking technique, we present the following algorithm, which is a trivial application of the two-way chaining scheme [10]. The algorithm does not satisfy the definition of two-way linear probing as we explained earlier, because the linear probes are performed within each block and not along the hash table. That is, whenever the linear probe sequence reaches the right boundary of a block, it continues probing starting from the left boundary of the same block. The algorithm partitions the hash table into disjoint blocks each of size \(\beta_{1}(n)\), where \(\beta_{1}(n)\) is an integer to be defined later. We save with each block its load, that is, the number of keys it contains, and keep it updated whenever a key is inserted in the block. For each key, we choose two initial hashing cells, and hence two blocks, independently and uniformly at random, with replacement. From the initial cell that belongs to the least loaded block, breaking ties randomly, we probe linearly and cyclically _within the block_ until we find an empty cell where we insert the key. If the load of the block is \(\beta_{1}\), i.e., it is full, then we check its right neighbor block and so on, until we find a block that is not completely full. We insert the key into the first empty cell there. Notice that only one probe sequence is used to insert any key. The search operation, however, uses two probe sequences as follows. First, we compute the two initial hashing cells. We start probing linearly and cyclically _within_ the two (possibly identical) blocks that contain these initial cells. If both probe sequences reach empty cells, or if one of them reaches an empty cell and the other one finishes the block without finding the key, we declare the search to be unsuccessful.