Authors: G. M. Sridevi, M. V. Ramakrishna, D. V. Ashoka
Keywords: H1 Universal Class of Hashing Functions, Radix transformation, Mid-Square method, Multiplicative Hashing, Division-remainder method.
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.
G. M. Sridevi
ORCID: https://orcid.org/ 0000-0003-3864-9983
Research Scholar - Visvesvaraya Technological University (VTU),
Dayananda Sagar Academy of Technology and Management,
Department of Information Science and Engineering,
Udayapura, Kanakapura Road, Bengaluru-560082, India.
E-mail:
M. V. Ramakrishna
ORCID: https://orcid.org/0000-0001-7058-7562
SJB Institute of Technology, Department of Information Science and Engineering,
BGS Health and Education City, Dr. Vishnuvardhan Road,
Bengaluru-560060, India.
E-mail:
D. V. Ashoka
ORCID: https://orcid.org/ 0000-0003-1326-2387
JSS Academy of Technical Education
Department of Information Science and Engineering,
Dr. Vishnuvardhan Road,
Bengaluru-560060, India.
E-mail:
DOI
https://doi.org/10.56415/csjm.v31.10
Fulltext
–
0.23 Mb