A Note on the Efficiency of Hashing Functions

Hashing functions are considered which store data "randomly" in a fixed size hash table with no auxiliary storage. It is known that if k out of the N locations have been previously filled randomly, then the expected number of locations which must be looked at until an empty one is found is 1 qk/(N --k -b 1). It is shown that there exist nonrandom hashing functions which are more efficient for certain values of k and N. However, it is shown that the 1 + k/(N -k + 1) figure is a "lower bound" on hashing performance in the following sense. If h is any hashing function such that the expected number of trials to insert the (k -b 1)st item into a table of size N is C(k, N), and if for some k, C(k, N) 1 -b k/(N --k 4-1). Finally, it is shown that randomness is a sufficient but not necessary condition for attainment of the 1 4k/(N --k -4-1) performance for all k, and a necessary and sufficient condition is given.