# Two-Way Linear Probing Revisited
## 6 Simulation Results
\begin{table}
\begin{tabular}{c c c c c c c c c} \hline \multirow{2}{*}{\(n\)} & \multirow{2}{*}{\(\alpha\)} & \multicolumn{2}{c}{ClassicLinear} & \multicolumn{2}{c}{ShortSeq} & \multicolumn{2}{c}{SmallCluster} \\ \cline{3-10}  & & **Avg** & **Max** & **Avg** & **Max** & **Avg** & **Max** \\ \hline \multirow{2}{*}{\(2^{8}\)} & 0.4 & 2.02 & 8.32 & 1.76 & 6.05 & **1.76** & **5.90** \\  & 0.9 & 15.10 & 87.63 & 12.27 & 50.19 & **12.26** & **43.84** \\ \hline \multirow{2}{*}{\(2^{12}\)} & 0.4 & 2.03 & 14.95 & 1.75 & 9.48 & **1.75** & **9.05** \\  & 0.9 & 15.17 & 337.22 & 12.35 & 106.24 & **12.34** & **78.75** \\ \hline \multirow{2}{*}{\(2^{16}\)} & 0.4 & 2.02 & 22.54 & 1.75 & 12.76 & **1.75** & **12.08** \\  & 0.9 & 15.16 & 678.12 & 12.36 & 155.26 & **12.36** & **107.18** \\ \hline \multirow{2}{*}{\(2^{20}\)} & 0.4 & 2.02 & 29.92 & 1.75 & 16.05 & **1.75** & **15.22** \\  & 0.9 & 15.17 & 1091.03 & 12.35 & 203.16 & **12.35** & **136.19** \\ \hline \multirow{2}{*}{\(2^{22}\)} & 0.4 & 2.02 & 33.81 & 1.75 & 17.74 & **1.75** & **16.65** \\  & 0.9 & 15.17 & 1309.04 & 12.35 & 226.44 & **12.35** & **150.23** \\ \hline \end{tabular}
\end{table} 
Table 2: The average maximum cluster size and the average cluster size over 100 simulations of the algorithms. The best performances are drawn in boldface. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \multirow{2}{*}{\(n\)} & \multirow{2}{*}{\(\alpha\)} & \multicolumn{2}{c}{ClassicLinear} & \multicolumn{2}{c}{ShortSeq} & \multicolumn{2}{c}{SmallCluster} \\ \cline{3-10}  & & **Avg** & **Max** & **Avg** & **Max** & **Avg** & **Max** \\ \hline \multirow{2}{*}{\(2^{8}\)} & 0.4 & 1.33 & 5.75 & **1.28** & 4.57 & 1.28 & **4.69** & 1.50 & 9.96 \\  & 0.9 & 4.38 & 68.15 & **2.86** & 39.72 & 3.05 & **35.69** & 6.63 & 71.84 \\ \hline \multirow{2}{*}{\(2^{12}\)} & 0.4 & 1.33 & 10.66 & **1.28** & _7.35_ & 1.29 & **7.49** & 1.52 & 14.29 \\  & 0.9 & 5.39 & 275.91 & _2.90_ & _78.21_ & 3.07 & **66.03** & 6.91 & 118.34 \\ \hline \multirow{2}{*}{\(2^{16}\)} & 0.4 & 1.33 & 16.90 & **1.28** & _10.30_ & 1.29 & **10.14** & 1.52 & 18.05 \\  & 0.9 & 5.49 & 581.70 & _2.89_ & _120.32_ & 3.07 & **94.58** & 6.92 & 155.36 \\ \hline \multirow{2}{*}{\(2^{20}\)} & 0.4 & 1.33 & 23.64 & **1.28** & _13.24_ & 1.29 & **13.03** & 1.52 & 21.41 \\  & 0.9 & 5.50 & 956.02 & _2.89_ & _164.54_ & 3.07 & **122.65** & 6.92 & 189.22 \\ \hline \multirow{2}{*}{\(2^{22}\)} & 0.4 & 1.33 & 26.94 & **1.28** & _14.94_ & 1.29 & **14.44** & 1.52 & 23.33 \\ \cline{2-10}  & 0.9 & 5.50 & 1157.34 & _2.89_ & _188.02_ & 3.07 & **136.62** & 6.93 & 205.91 \\ \hline \end{tabular}
\end{table} 
Table 1: The average and the maximum successful search and insert times averaged over 10 iterations each consisting of 100 simulations of the algorithms. The best successful search time is shown in boldface and the best insert time is shown in italic. Comparing the simulation data from all tables, one can see that the best average performance is achieved by the algorithms LocallyLinear and ShortSeq. Notice that the ShortSeq algorithm achieves the best average successful search time when \(\alpha=0.9\). The best (average and maximum) insertion time is achieved by the LocallyLinear