Comprehensive Performance Study of Hashing Functions

Abstract

Most literature on hashing functions speaks in terms of hashing functions being either ‘good’ or ‘bad’. In this paper, we demonstrate how a hashing function that gives good results for one key set, performs badly for another. We also demonstrate that, for a single key set, we can find hashing functions that hash the keys with varying performances ranging from perfect to worst distributions. We present a study on the effect of changing the prime number ‘$p$’ on the performance of a hashing function from $H_1$ Class of Universal Hashing Functions. This paper then explores a way to characterize hashing functions by studying their performance over all subsets of a chosen Universe. We compare the performance of some popular hashing functions based on the average search performance and the number of perfect and worst-case distributions over different key sets chosen from a Universe. The experimental results show that the division-remainder method provides the best distribution for most key sets of the Universe when compared to other hashing functions including functions from $H_1$ Class of Universal Hashing Functions.

Keywords

• $h_1$ universal class of hashing functions
• radix transformation
• mid-square method
• multiplicative hashing
• division-remainder method