# Performance of Linear and Spiral Hashing Algorithms
## 5 Experimental Results  
We tested the efficiency of the two data structures by varying two parameters: the number of threads and the bucket capacity, i.e., the average number of records per bucket. Figure 9: Probability that the lowest-numbered bucket under Spiral Hashing indeed has the largest number of records. Of course, the use of threads and locks generates quite a bit of overhead. If we were to perform other work within a thread, this overhead would be less visible. As it is, each thread only accesses the data structure, and lock contention is maximized. We loaded our data structure with 1,000,000 records. For the first experiment, we then inserted another 1,000,000 records consisting of a random unsigned integer as the key and a short string. These records were stored in a C++ standard library vector, and each thread was given an equal-sized region of this vector to insert into. This write-only workload led to many splits and contention in the file state. For the second experiment, we again preloaded the data structure with 1,000,000 records with random keys. We then filled a vector with 1,000,000 random keys. Each thread then performed lookup operations for regions of the same size in this vector. This operation does not acquire exclusive locks on the file state and the timing is much better. However, most of the time, the lookup operation accesses all records in a bucket. Each experiment was performed 100 times (in a new process). We varied the number of threads used and the nominal bucket capacity. We used the load factor (the ratio of the number of records to the number of buckets) as the split trigger. Thus, a hash table with 1,000,000 records and a bucket capacity of 3 has 333,334 buckets, and when it grows to 2,000,000 records, it has 666,666 buckets. We performed our experiments on a Mac Powerbook with an M2 Max processor and 64 GB of memory. The results on an earlier Mac Powerbook with an Intel processor exhibited the same behavior. In both cases, the OS assigned only one CPU to the process. Because we used random keys, each run of the program had a unique workload. This seemed to be the dominant factor in the variation of the execution time, as the violin plots in Figure 10 indicate. We can see that the distribution of the execution times has a long tail but otherwise resembles that of a normally distributed random variable. While the run times are not normally distributed, they justify the use of the mean in reporting our results. We depict these results in Figures 11 and 12. We also used the non-parametric Mann-Whitney U-test to ascertain the significance of the observed differences. Not surprisingly, they were highly significant, as Figure 13 shows. The values shown give the probability that the differences in the run times for LH and SH are accidental. Figure 10: Violin plot of the run times of LH and SH under inserts with 10 threads and a bucket capacity of 10. Figure 11: Run-time means for the insert experiment for various numbers of threads and bucket capacities. Figure 12: Run-time means for the lookup experiment. Our experiments show that Linear Hashing is faster than Spiral Hashing under a write load, whereas Spiral Hashing is usually faster under lookups. The different complexities of the addressing mechanisms do not seem to be relevant. Our experimental setup was very close to that of [PERSON]'s. One difference is that, for many decades, we have had libraries that generate good random numbers and hashes. [PERSON] used three small files: one of user names, one of an English dictionary, and one of call numbers that he converted to numeric keys with a simple conversion function. If we were to use a modern hash function on files of these types to obtain keys, then we would have keys indistinguishable from random numbers. He used a random number generator to select sets of keys for the measurement of lookup times. The second difference is that we used the C++ standard library for an efficient implementation of vectors, something that was not available to [PERSON].