Chapter 10
Designing Great Hash Tables with Randomization

Hash tables are ubiquitous, and for good reason. I first introduced hash tables and demonstrated how they worked in Volume 1, Chapter 8. As I discussed there, hash tables are blazing fast, as they have O(1) search, insertion, and deletion. While this speed comes at the cost of not being able to keep its values in a sorted order, hash tables are nonetheless one of the most important data structures out there.

In this chapter, we’re going to revisit the inner workings of hash tables, especially regarding how hash functions work. In particular, we’re going to take a look at a sneaky, easily unnoticed vulnerability of hash tables and how we can use randomization to make things better.