Performance in Practice of String Hashing Functions
M. V. Ramakrishna, Justin Zobel · 1997
String hashing is a fundamental operation, used in countless applications where fast access to distinct strings is required. In this paper we describe a class of string hashing functions and explore its performance. In particular, using experiments with both small sets of keys and a large key set from a text database, we show that it is possible to achieve performance close to that theoretically predicted for hashing functions. We also consider criteria for choosing a hashing function and use them to compare our class of functions to other methods for string hashing. These results show that our class of hashing functions is reliable and efficient, and is therefore an appropriate choice for general-purpose hashing. 1 Introduction String hashing is the process of reducing a string to a pseudo-random number in a specified range. It is a fundamental operation, used widely in applications where speed is critical. On a small scale, a hash table is often the basic data structure in applicat...