Grokking Algorithms, Second Edition

5 Hash tables

In this chapter

• You learn about hash tables, one of the most useful data structures. Hash tables have many uses; thischapter covers the common use cases.
• You learn about the internals of hash tables: implementation, collisions, and hash functions. These properties will help you understand how to analyze a hash table’s performance.

Suppose you work at a grocery store. When a customer buys produce, you have to look up the price in a book. If the book is unalphabetized, it can take you a long time to look through every single line for apple. You’d be doing simple search from chapter 1, where you have to look at every line. Do you remember how long that would take? O(n) time. If the book is alphabetized, you could run binary search ...