Essential Algorithms: A Practical Approach to Computer Algorithms

CHAPTER 8

Hash Tables

The preceding chapter explained binary search, an O(log N) algorithm for locating an item in a sorted list. The algorithm repeatedly examines a test item in the middle of the part of the list where the target item must be. It compares the test item to the target item and then recursively examines the left or right half of the region, depending on whether the test item is greater than or less than the target item.

The preceding chapter also explained interpolation search, which uses a mathematical calculation to predict where the target item will be. That algorithm has O(log(log N)) time and is so much faster than binary search that it almost seems like magic.

The reason interpolation search is so much faster than binary search is that it uses the data's special structure to find values by calculation instead of by making comparisons. (The countingsort and bucketsort algorithms described in Chapter 6 do this too.)

Hash tables also use the data's structure to locate values very quickly. Instead of storing items in a sorted list, a hash table stores them in a way that lets you calculate an item's location in the table directly.

For a simple example of a hash table, suppose you have a small company with 20 employees, and you want to be able to look up an employee's information by searching for that person's employee ID. One way you could store the information is to allocate an array of 100 items and then store an employee with employee ID N in position N mod 100 ...