# Performance of Linear and Spiral Hashing Algorithms
## 3 Fringe Analysis
On the left, we used random numbers, and on the right, we used parts of the SHA1 hash of the first 8000 words in a list of English words. Figure 6: Number of records rehashed during a split in LH. Theoretical result for Linear Hashing when buckets are split based on the ratio of records to buckets. We also conducted a related experiment. We added \(n\) records to an initially empty LH file. Our parameter \(n\) varied from 800 to 33,000. We used a target bucket capacity of 10, causing the level of the LH file to change from 6 to 11. We then added 1000 additional records and calculated the number of records whose addresses were recalculated during a split. We used two different types of split triggers. The more popular version calculates the average number of records per bucket from the total number of records and the number of buckets and triggers a split whenever this value exceeds the target bucket capacity. Alternatively, a split is triggered whenever the bucket where the record is placed reaches capacity. In this more aggressive version, splits are more frequent and buckets tend to contain fewer records. Recall that the bucket triggering a split is usually not the one that is split. We repeated the process of loading \(n\) records into the data structure and then inserting 1000 new records while counting the number of records accessed during a split. The initial \(n\) records were the same. We report our results in Figure 8. Using the normal split trigger, LH shows a saw-tooth pattern oscillating between 1 and 2 times the number of records touched per insert. However, the more aggressive trigger shows a somewhat more chaotic behavior with different peak locations and higher variability. Figure 7: Number of records rehashed during a split in LH. Experimental results for random keys when splits are triggered by an overflowing bucket. Spiral Hashing's selling point is its avoidance of this fringe behavior. The probability of a record belonging to Bucket \(i\) is \(\log_{2}(1+1/i)\). The size of the bucket that is split is always rather close to 1.44 times the average. Thus, instead of a cyclic fringe behavior, SH shows near-constant movement, independent of the number of records, but it is still subject to random fluctuations. In Figure 8, we can see that the use of the normal and the more aggressive triggers results in similar, near-constant behavior. However, the more aggressive trigger results in greater variability. Spiral Hashing assigns a record to Bucket \(i\) with probability \(p_{i}=\log_{2}(1+1/i)\) for \(i\) between \(s\) and \(2s-1\). The lowest-numbered bucket has the largest expected number of records and is always the next one to be split. However, it is often not the bucket with the actual largest number of buckets. The number of records in a bucket follows a binomial distribution, allowing us to calculate the exact probability that one bucket contains more records than another. There does not, however, seem to be a simple, closed formula for this probability. Instead of using the Central Limit Theorem and approximating with the normal distribution, we used the Las Vegas method to determine the probability that the next bucket to be split actually has the largest number of records, as we would prefer. However, this was not the case, as our results in Figure 9 show. As the nominal bucket capacity increases and the number of buckets remains small, the probability that Bucket \(s\) has the most records increases, but for larger structures, that probability diminishes quickly. Figure 8: Number of records rehashed when adding 1000 records to a Linear Hashing and Spiral Hashing file with \(n\) records, \(n\in[2^{10}-200,2^{15}+200]\).