A Common-Sense Guide to Data Structures and Algorithms

Practical Examples

Hash tables have many practical use cases, but here we’re going to focus on using them to increase algorithm speed.

In Chapter 1, ​Why Data Structures Matter​, we learned about array-based sets—arrays that ensure that no duplicate values exist. There we found that every time a new value is inserted into the set, we need to run a linear search (if the set is unordered) to make sure that the value we’re inserting isn’t already in the set.

If we’re dealing with a large set in which we’re making lots of insertions, this can get unwieldy very quickly, since every insertion runs at O(N), which isn’t very fast.

In many cases, we can use a hash table to serve as a set.

When we use an array as a set, we simply place each piece of data ...