# Performance of Linear and Spiral Hashing Algorithms
## 6 Imperfect Hash Functions  
Hash-based schemes assume close-to-perfect hash functions. This means that each hash should appear with equal probability. For example, we can use a no-longer-secure but fast hash function such as MD5 or any of the hashes currently considered secure. In \"real life\", this might not be the case. For example, MongoDB, a NoSQL document database, has IDs that look like hashes but consist of three parts, including a date-time stamp and a counter. A programmer could easily assume that the MongoDB ID is a perfect hash, but this is not true. The result could be an increase in the number of buckets with many more records than expected. Key-based operations accessing these records would take quite a bit more time than expected. Figure 13: \(p\)-values for the null hypothesis of equal lookup times using the Whitney–Mann U-test. Because LH and SH calculate addresses from a hash in very different ways, they react to less-than-perfect hash functions in different ways. For example, time stamps and counts used as keys change the lower bits, which would allow LH to function well, whereas SH would not. SH separates records into different buckets based on high-order bits. Even if we took the reciprocal of the counts or time stamps, we would place records in only a small number of buckets. However, if we reversed the bit string of the count and cast it as the fraction of a floating-point number, we would obtain an equally good fit for SH. We give an example in Figure 14, where we reuse the sizes from our previous example and have 854 buckets. We inserted keys ranging from 1 to 8540 into the data structure and recorded the number of records in the bucket. For LH, we just used the count, whereas for SH, we used the procedure described above. As we can see, the number of records per bucket is almost ideal. So, in this one case, an imperfect hash function yields an almost perfect distribution. To generate a biased hash function for SH, we take a random number, translate it to a double-precision floating-point number, raise this number to the power of \(\alpha\), and then translate it back to an unsigned integer. If we perform the same procedure for LH, the altered hash functions work just as well as the unaltered hash function. This is because, in SH addressing, the leading bits are more important, whereas in LH addressing, the trailing bits are more important. We therefore reverse the bit string for LH. We show the results of the altered hash function in Figure 15 for \(\alpha=2\), \(3/2\), \(1\), \(2/3\), and \(1/2\). We simulated the hash scheme for 200 buckets and an average of 1000 records per bucket (for a total of 200,000 records). The y-axis shows the number of records per bucket in multiples of 1000, i.e., the relative frequency. For LH, we see a much greater frequency for Bucket 0 and \(\alpha>1\) and increased variance for LH when \(\alpha<1.0\). For SH, the top frequency is much larger when \(\alpha>1\). The larger spread of frequency means that some split or lookup operations will have unusually long latencies as they hit exceedingly large buckets. Our experimental setup can only measure average latencies, which are barely affected. We report our experiment in Table 1, using the same setup as for the performance numbers. We provide the total time in milliseconds for inserting 1,000,000 records into a data structure already containing 1,000,000 records, or for looking up 1,000,000 random keys in a data structure of 1,000,000 records. For each situation, we used 100 measurements, as before. The resulting timings barely changed and were often not different between the unbiased hash (\(\alpha=1\)) and the biased hashes. In Table 1, we provide the p-values, indicating whether the results are statistically significantly different from the unbiased hash case. This is frequently not the case, but other than observing that the more disturbed hashes (\(\alpha=0.5\) or \(\alpha=2\)) tend to show more variation, we are unable to draw any firm conclusions.