Chapter 8
Blazing Fast Lookup with Hash Tables

Imagine you’re writing a program that allows customers to order fast food from a restaurant, and you’re implementing a menu of foods with their respective prices. You could, technically, use an array:

This array contains several subarrays, and each subarray contains two elements. The first element is a string representing the food on the menu, and the second element represents the price of that food.

As you learned in Chapter 2, , if this array were unordered, searching for the price of a given food would take O(N) steps since the computer would have to perform a linear search. If it’s an ordered array, the computer could do a binary search, which would take O(log N).

While O(log N) isn’t bad, we can do better. In fact, we can do much better. By the end of this chapter, you’ll learn how to use a special data structure called a hash table, which can be used to look up data in just O(1) time. By knowing how hash tables work under the hood and the right places to use them, you can leverage their tremendous lookup speeds in many situations.