# Two-Way Linear Probing Revisited
## 6 Simulation Results  
We simulate all linear probing algorithms we discussed in this article with the fcfs replacement strategy: the classical linear probing algorithm ClassicLinear, the locally linear algorithm LocallyLinear, and the two-way linear probing algorithms ShortSeq, SmallCluster, WalkFirst, and DecideFirst. For each value of \(n\in\left\{2^{8},2^{12},2^{16},2^{20},2^{22}\right\}\), and constant \(\alpha\in\left\{0.4,0.9\right\}\), we simulate each algorithm 1000 times divided into 10 iterations (experiments). Each iteration consists of 100 simulations of the same algorithm where we insert \(\left\lfloor\alpha n\right\rfloor\) keys into a hash table with \(n\) cells. In each simulation, we compute the average and the maximum successful search and insert times. For each iteration (100 simulations), we compute the average of the average values and and the average of the maximum values computed during the 100 simulations for the successful search and insert times. The overall results are finally averaged over the 10 iterations and recorded in the next tables. Similarly, the average maximum cluster size is computed for each algorithm as it can be used to bound the maximum unsuccessful search time, as mentioned earlier. Notice that in the case of the algorithms ClassicLinear and ShortSeq, the successful search time is the same as the insertion time. Tables 1 and 2 contain the simulation results of the algorithms ClassicLinear, ShortSeq, and SmallCluster. With the exception of the average insertion time of the SmallCluster algorithm, which is slightly bigger than the ClassicLinear algorithm, it is evident that the average and the worst-case performances of SmallCluster and ShortSeq are better than ClassicLinear. The SmallCluster algorithm seems to have the best worst-case performance among the three algorithms. This is not a total surprise to us, because the algorithm considers more information (relative to the other two) before it makes its decision of where to insert the keys. It is also clear that there is a nonlinear increase, as a function of \(n\), in the difference between the performances of these algorithms. This may suggest that the worst-case performances of algorithms ShortSeq and SmallCluster are roughly of the order of \(\log n\). The simulation data of algorithms LocallyLinear, WalkFirst, and DecideFirst are presented in Tables 3-5. These algorithms are simulated with blocks of size \(\big{\lfloor}\ (1-\alpha)^{-1}\log_{2}\log n\big{\rfloor}\). The purpose of this is to show that, practically, the additive and the multiplicative constants appearing in the definitions of the block sizes stated in Theorems 8-10 can be chosen to be small. The hash table is partitioned into equal-sized blocks, except possibly the last one. The average and the maximum values of the successful search time, inset time, and cluster size (averaged over 10 iterations each consisting of 100 simulations of the algorithms) are recorded in the tables below where the best performances are drawn in boldface. Results show that the LocallyLinear algorithm has the best performance, whereas WalkFirst appears to perform better than DecideFirst. Indeed, the sizes of the cluster produced by WalkFirst appears to be very close to that of LocallyLinear. This supports the conjecture that Theorem 10 is, in fact, true for any constant load factor \(\alpha\in(0,1)\), and the maximum unsuccessful search time of WalkFirst is at most \(4(1-\alpha)^{-1}\log_{2}\log n+O(1)\), w.h.p. The average maximum cluster size of DecideFirst seems to be close to the other ones when \(\alpha\) is small, but it almost doubles when \(\alpha\) is large. This may suggest that the multiplicative constant in the maximum unsuccessful search time established in Theorem 9 could be improved.