A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Hash Tables for Speed

While hash tables are a perfect fit for paired data, they can also be used to make your code faster—even if your data doesn’t exist as pairs. And this is where things really get exciting.

Here’s a simple array:

array = [61, 30, 91, 11, 54, 38, 72]

If you want to search for a number in this array, how many steps would it take?

Because the array is unordered, you would have to perform a linear search, which would take N steps. You learned this all the way back at the beginning of the book.

However, what would happen if we ran some code that would convert these numbers into a hash table that looked like this?

hash_table = {61 => true, 30 => true, 91 => true,
11 => true, 54 => true, 38 => true, 72 => true} ...