The Joys of Hashing: Hash Table Programming with C

© Thomas Mailund 2019

Thomas MailundThe Joys of Hashinghttps://doi.org/10.1007/978-1-4842-4066-3_6

6. Heuristic Hash Functions

Thomas Mailund¹ 

(1)

Aarhus N, Denmark

 

The main topic of this book is implementing hash tables; it’s only secondarily about hash functions. This is why you have assumed a priori that you have uniformly distributed hash keys. In reality, this is unlikely to be the case; real data are rarely random samples from the space of possible data values. In this chapter, you will learn about commonly used heuristic hash functions. In the next chapter, you will see an approach to achieving stronger probabilistic guarantees.

To set the tone for this chapter, you will first consider two cases of data that are not randomly distributed. To ...