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 ...
Get A Common-Sense Guide to Data Structures and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
