Essential Algorithms, 2nd Edition

CHAPTER 8Hash Tables

The preceding chapter explained binary search, an 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.

Chapter 7 also explained interpolation search, which uses a mathematical calculation to predict where the target item will be. That algorithm has time and is so much faster than binary search that it almost seems like magic.

The reason why 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, pigeonhole sort, and bucketsort algorithms described in Chapter 6 do that too.

Hash tables also use the data's structure to locate values 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.

NOTE

Python's version of a hash table is a dictionary.

In C#, you can use the HashTable class to store weakly typed objects with keys. The Dictionary ...