# Performance of Linear and Spiral Hashing Algorithms
## 7 Conclusions and Future Work  
Performance-based judgments need to be revised whenever the underlying technology changes. A reassessment of Spiral Hashing and Linear Hashing was overdue, and we  
\begin{table}
\begin{tabular}{r r r r|r r r r} \hline \hline \multicolumn{7}{c}{Spiral Hashing Inserts} \\ \hline \(\alpha\) & Threads & Time & \(p\)-value & \(\alpha\) & Threads & Time & \(p\)-value \\
0.5 & 5 & 0.886 & 0.978 & 0.5 & 20 & 1.845 & 0.781 \\
0.667 & 5 & 0.864 & 0.022 & 0.667 & 20 & 1.839 & 0.781 \\
1 & 5 & 0.876 & 1.000 & 1 & 20 & 1.872 & 1.000 \\
1.5 & 5 & 0.865 & 0.049 & 1.5 & 20 & 1.877 & 0.973 \\
2 & 5 & 0.858 & 0.005 & 2 & 20 & 1.839 & 0.333 \\ \hline \multicolumn{7}{c}{Linear Hashing Insert} \\ \hline
0.5 & 5 & 0.774 & 0.054 & 0.5 & 20 & 1.703 & 0.335 \\
0.667 & 5 & 0.774 & 0.026 & 0.667 & 20 & 1.676 & 0.023 \\
1 & 5 & 0.789 & 1.000 & 1 & 20 & 1.741 & 1.000 \\
1.5 & 5 & 0.769 & 0.011 & 1.5 & 20 & 1.687 & 0.071 \\
2 & 5 & 0.772 & 0.094 & 2 & 20 & 1.836 & 0.020 \\ \hline \multicolumn{7}{c}{Spiral Hashing Lookup} \\ \hline
0.5 & 5 & 0.417 & \(<\)10\({}^{-11}\) & 0.5 & 20 & 0.322 & 0.016 \\
0.667 & 5 & 0.413 & \(<\)10\({}^{-4}\) & 0.667 & 20 & 0.430 & \(<\)10\({}^{-28}\) \\
1 & 5 & 0.415 & 1.000 & 1 & 20 & 0.323 & 1.000 \\
1.5 & 5 & 0.424 & \(<\)10\undertook it in this article. Our experimental setup is essentially the same as that of [PERSON]'s. There are only three main differences: storing data in memory versus storing data on a hard disk, better generation of random keys, and the efficient implementation of C++ vectors. Therefore, our results reflect the differences in computer architecture and organization. Over the years, access times to memory and storage have changed by only a small factor, whereas the speed of computation, especially floating-point computations, has increased by a very large factor. As a result, Spiral Hashing now provides a viable alternative to Linear Hashing even as an in-memory structure. While the addressing mechanism of Spiral Hashing has not changed, its speed now comes close to that of the less complicated addressing mechanism of Linear Hashing. As Spiral Hashing has better fringe behavior and better tail latencies for key-based operations, the only reason to stick with Linear Hashing for an in-memory data structure is the existence of an established code base. If the buckets are stored in pages in storage, the better fringe behavior should be even more attractive. In Spiral Hashing, the biggest bucket is often the next bucket to be split. This behavior avoids page overflows, which are usually handled by adding overflow pages. The same observation applies to distributed systems. A distributed version of Spiral Hashing needs to solve the problem of distributing file information to clients that have an outdated view of the file state \(s\). If we can keep the empty buckets \(1,\ldots,s-1\) around, a misdirected request will access an empty bucket and can obtain a better file state from there. Unlike LH*, the information that can be gathered from the fact of misdirection only shows that \(s\) has changed, but gives no clues about its true value. This is an avenue of interesting research that we plan to undertake next. Our implementation used locks. Lock-free implementations of Linear Hashing exist [15; 16]. [PERSON]'s implementation realizes that an in-memory LH hash file is essentially a single, linked list, with buckets forming sub-lists. The list is ordered by the keys in reverse order. Thus, we can simply adjust a lock-free linked-list implementation. A bucket split results from the insertion of a new pointer to the leading record in the bucket, dividing the previous sub-list corresponding to the bucket. A similar observation holds for SH. An implementation is left to future work. Conceptualization: A.D.R.K. and T.S., methodology: A.D.R.K. and T.S., software (performance): A.D.R.K., software (fringe analysis): T.S., analysis: A.D.R.K. and T.S., writing: T.S. All authors have read and agreed to the published version of the manuscript.