# Performance of Linear and Spiral Hashing Algorithms
## 1 Introduction  
Key-value stores have become a mainstay of data organization for big data. For instance, Amazon DB is a pioneering NoSQL database built on this concept. A key-value store implements a map or dictionary and can be implemented in different ways. B-tree-like structures allow for range queries, whereas dynamic hash tables have simpler architectures and better asymptotic performance of \(O(1)\) for inserts, updates, and reads. For instance, Linear Hashing, the best-known version of dynamic hash tables, is used internally by both Amazon's DynamoDB and BerkeleyDB. These data structures were originally conceived to implement indices for database tables and continue to be used for this purpose. They were developed in a world of anemic CPU performance and slow and small storage systems, but they have been successfully used in the world of big data.  
In this article, we compare Linear Hashing (LH) with its competitor, Spiral Hashing, proposed at roughly the same time in the late 1980s. Both store key-value pairs in containers--so-called _buckets_. Originally, each bucket resided in a page or several pages of storage, i.e., in those days, exclusively on a magnetic hard drive. However, nowadays, in-memory implementations of LH are common. Hash-based structures can also be employed in distributed systems. The key, together with the current state of the file, is used to calculate the bucket to which the key-value pair belongs. A file usually accommodates an increase in the number of records by splitting a single bucket into two or more buckets. In this way, it maintains a bound on the expected number of records per bucket. It can also react to a decrease in the number of records by merging buckets.  
LH adjusts to growth in the number of records by splitting a predetermined bucket, following a constant ordering of buckets. Thus, the state of an LH file is determined entirely by the number of buckets, \(N\). The last \(\lfloor\log_{2}(N)\rfloor\) or \(\lfloor\log_{2}(N)\rfloor+1\) bits of the hash of a key determine where the record--the key-value pair--is located. The main criticism of LH is the cyclic worst-case performance for inserts and lookups. The ingenious addressing mechanism of _Spiral Storage_, or _Spiral Hashing_ (SH) as we prefer to call it, avoids this cyclic behavior. Like LH and other hash-based schemes, it stores key-value pairs in buckets. It uses a more complex address calculation to even out worst-case performance. In awell-received study [1], [PERSON] compared the performance of LH, SH, an unbalanced binary tree, and a scheme built on double hashing and came to the conclusion that LH always outperforms SH (and the other two schemes). This reflects the cost of the more complex addressing scheme in SH. However, the environment has changed considerably for both schemes. More data are stored in memory or in the new NVRAM technologies. Processor speeds have increased much faster than memory access times or storage access times. We decided to test whether [PERSON]'s verdict still stands. It does not!  
In the following, we first review the standard versions of LH and SH. We then perform a theoretical and experimental fringe analysis for bulk insertions into both data structures. Even if a large bulk of data is inserted, and thus a large number of splits occur, LH's performance remains cyclic. Then, we explain our implementations of LH and SH as main memory data structures. Next, we review the differences between in-memory LH and SH and the in-storage versions. The next section gives our experimental results. We then investigate the consequences of uneven hashes. We conclude that Spiral Hashing is a viable alternative to Linear Hashing with the potential to control tail latency resulting from key-based operations.