# Two-Way Linear Probing Revisited
## 1 Introduction  
In classical open addressing hashing [1], \(m\) keys are hashed sequentially and on-line into a table of size \(n>m\), (that is, a one-dimensional array with \(n\) cells which we denote by the set \(\mathcal{T}=\{0,\ldots,n-1\}\)), where each cell can harbor at most one key. Each key \(x\) has only one infinite probe sequence \(f_{i}(x)\in\mathcal{T}\), for \(i\in\mathbb{N}\). During the insertion process, if a key is mapped to a cell that is already occupied by another key, a collision occurs, and another probe is required. The probing continues until an empty cell is reached where a key is placed. This method of hashing is pointer-free, unlike hashing with separate chaining where keys colliding in the same cell are hashed to a separate linked list or chain. For a discussion of different hashing schemes, see [2; 3; 4]. In classical linear probing, the probe sequence for each key \(x\) is defined by \(f_{i+1}(x)=f_{i}(x)+1\mod n\), for \(i\in[\![n]\!]:=\{1,\ldots,n\}\). Linear probing is known for its good practical performance, efficiency, and simplicity. It continues to be one of the best hash tables in practice due to its simplicity of implementation, absence of overhead for internally used pointers, cache efficiency, and locality of reference [5; 6; 7; 8]. On the other hand, the performance of linear probing seems to degrade with high load factors \(m/n\), due to a primary-clustering tendency of one collision to cause more nearby collisions. In particular, the length of the longest probe sequence needed to insert (or search for) a key in a hash table, with constant load factor, constructed by linear probing is proven [9] to be \(\Omega(\log n)\), in probability. The purpose of this paper is to design efficient open addressing hashing schemes that improve the worst-case performance of classical linear probing. Our study concentrates on schemes that use two linear probe sequences to find possible hashing cells for the keys. Each key chooses two initial cells independently and uniformly at random, withreplacement. From each initial cell, we probe linearly, and then cyclically whenever the last cell in the table is reached, to find two empty cells which we call terminal cells. The key then is inserted into one of these terminal cells according to a fixed strategy. We consider strategies that utilize the _greedy multiple-choice paradigm_[10; 11]. We show that some of the trivial insertion strategies with two-way linear probing have unexpected poor performance. For example, one of the trivial strategies we study inserts each key into the terminal cell found by the shorter probe sequence. Another simple strategy inserts each key into the terminal cell that is adjacent to the smaller cluster, where a cluster is an isolated set of consecutively occupied cells. Unfortunately, the performances of these two strategies are not ideal. We prove that, when any of these two strategies is used to construct a hash table with constant load factor, the maximum unsuccessful search time is \(\Omega(\log n)\), with high probability (w.h.p.). Indeed, we prove that, w.h.p., a giant cluster of size \(\Omega(\log n)\) emerges in a hash table of constant load factor, if it is constructed by a two-way linear probing insertion strategy that always inserts any key upon arrival into the empty cell of its two initial cells whenever one of them is empty. Consequently, we introduce two other strategies that overcome this problem. First, we partition the hash table into equal-sized blocks of size \(\beta\), assuming \(n/\beta\) is an integer. We consider the following strategies for inserting the keys:  
1. Each key is inserted into the terminal cell that belongs to the least crowded block, i.e., the block with the least number of keys. 2. For each block \(i\), we define its weight to be the number of keys inserted into terminal cells found by linear probe sequences whose starting locations belong to block \(i\).