# Performance of Linear and Spiral Hashing Algorithms
## 2 Background
### Difference between In-Memory and In-Storage Hash Tables  
In the years since the conception of Linear, Spiral, and Extendible Hashing, computer organization has undergone much development. These hashing schemes had to use storage and then Hard Disk Drives (HDDs) because the main memory was too precious and too limited. A hard disk stored data in blocks (then 512 B) and access to a block took maybe 15-30 ms. Nowadays, memory is cheaper and much more extensive. In addition, storage only pretends to be writable to random blocks. HDD technology uses shingled recording that does not allow in-place updates. With the help of internal caching and a log-structured organization of tracks into bands, an HDD provides an interface that seems to allow in-place updates of blocks [8]. The main alternative to magnetic storage technology is Solid State Drives (SSDs). The hard-drive industry has prioritized storage capacity over speed. Similarly, SSDs are increasingly made up of multi-bit cells that have an even more limited number of write-erase cycles than single-bit cells. An SSD stores data in pages that have to be written all at once, as is also the case for the blocks in an HDD. An SSD organizes a certain number of pages into an erase block. An overwrite of a page is only possible after a previous erasure. The _endurance_, i.e., the number of write-erase cycles, is limited and depends on the technology used and, more importantly, the number of bits per cell. An in-storage hash table frequently writes to its bucket and hence to the blocks/pages containing the buckets. If the storage device is a shingled HDD, an updated block is appended to a log stored in a number of contiguous tracks. To avoid the accumulation of blocks with outdated data, the log is continually cleared by moving active data blocks to the tail of the log-skipping data blocks with outdated or deleted data. While this write amplification is an inconvenience, the consequences for an SSD are worse. To update a page stored in an SSD, the page needs to be erased. If the SSD has an internal flash translation layer, the newly written page still has the same page address. However, internally, the old page has been marked as deleted and will eventually be erased with all the other pages in the same erase block. As some of these pages might contain valid data, this data is copied to other pages in a different erase block. These copies constitute _write amplification_, where a  
Figure 4: Spiral Hashing example with \(b=5\) and \(b=6\). Figure 3: Address calculation in Spiral Hashing for key key and file state S.  
single page overwrite results in several pages being written. As SSD manufacturers push storage capacity at the cost of lowering endurance by using cells that store more than one bit, write amplification becomes a concern. To allow more efficient use of shingled HDDs and multi-bit SSDs, zoned namespaces were introduced to replace and supplement the Logical Block Address (LBA) interface [9; 10]. Zoning allows a user to address a moderate to a large number of zones, but writes to these zones are sequential. This interface addresses the limitations of both current HDD and SSD technologies. Unfortunately, hash tables are not well suited for this interface; they prefer a paged environment. We can draw a parallel to B-trees: they are no longer used in their traditional form but use techniques such as Log-Structured Merge (LSM) trees to minimize changes to stored data at the cost of parallel searches. We can conclude that in-storage hash tables are workable for HDDs without the zoned namespace interface, but they need additional modifications for SSDs and HDDs with the zoned namespace interface. In-memory hash tables can be used for a wide variety of purposes, such as enabling equi-joins in a database, caching URLs in a web browser, and, in short, anywhere associative arrays, dictionaries, or sets are needed. They, and not in-storage hash tables, are our main concern here.