# Performance of Linear and Spiral Hashing Algorithms
## 3 Fringe Analysis  
Fringe analysis [11] analyzes the behavior of a data structure under mass insertion. For instance, [PERSON], [PERSON], and [PERSON] showed that a steady stream of inserts into a B-tree can create \"waves of misery\", where restructuring in the B-tree can lead to surges in the amount of data moved [12]. In the case of LH and SH, unevenness in the size of buckets determines fringe behavior. This unevenness also affects the tail latencies of key-based operations. For a lookup, the hash structure visits, on average, half the records in a bucket for a successful lookup and all the records if no record with the given key exists. An insert does not need to visit any other record in the target bucket but can lead to a split, which requires visiting all the records in the bucket being split. Linear Hashing is attractive because of its conceptual and architectural simplicity. As we have seen, the average number of records per bucket varies between buckets that have already been split in an epoch (when the level is constant) and those that are yet to be split. Figure 5 provides an example with level 9 and split pointer 342, and a total of 8000 records. Buckets 0 to 341 on the left and Buckets 512 to 853 on the right have, on average, about half as many records as Buckets 342 to 511. On the left, these numbers were obtained using random numbers as stand-ins for the hash of keys, whereas on the right, we used the first 8000 words in alphabetical order from an English dictionary as keys. The word list was compiled by [PERSON] of the University of Michigan. We then calculated the SHA1 hash of these keys and used the first 16 hexadecimal digits, transformed into an integer, as the keys. Remarkably, and by sheer accident, in this example, the hash of the keys is slightly smoother than the hash using random numbers. The figure illustrates that with small bucket sizes, the variability in the number of keys is large; however overall, the maximum number of records in a bucket yet to split is about twice as large as the maximum number of records in a bucket that has already been split in the current epoch. Only at the end of the epoch, when the split pointer is zero, will all buckets have the same expected number of keys. In general, with level \(l\) and split pointer \(s\), the buckets numbered 0 to \(s-1\) and \(2^{l}\) to \(2^{l}+s-1\) have already split and have, on average, half as many records as the remaining buckets. We can analyze the fringe behavior of Linear Hashing analytically. We assume that the LH structure maintains a maximum ratio of records to buckets. If the number of records is \(r\) and \(B\) is this ratio, i.e., the average number of records per bucket, then the number of buckets is \(r/B\). The level of the LH file is then \(\lambda=\lfloor\log_{2}(r/B)\rfloor\). The expected number of records in an unsplit bucket is then \(\frac{r}{2^{\lambda}}\). With every \(B\) inserts, a split occurs, so on average  
\[\frac{r}{B\cdot 2^{\lambda}}\]  
records are rehashed. About half of them are moved to the new bucket. The average number of records rehashed follows a saw-tooth curve, increasing from \(1\) to \(2\), starting at \(B\) times a power of two and being reset at the next power of two. Figure 6 shows the results. We provide an example of an experiment with a bucket capacity of \(10\) in Figure 7. In this experiment, we created a list of insertion operations that trigger a split and captured the size of the bucket that needs to be split. Recall that the split operation recalculates the address for each of the keys of records in the bucket and moves about half to the new bucket. This is easily implemented by creating two containers, one each for the new and one for the old bucket. We then moved pointers to the records according to the calculated address into these containers, and at the end, inserted the new bucket into the data structure and replaced the old bucket with the newly created bucket. Figure 5: Theoretical and expected number of records per bucket in an LH file.