What Are Hash Tables and Why Are They Amazing?
An explanation that doesn’t assume you’re a developer
Hash tables (commonly referred to as hash maps) are simply amazing. They exist in basically every language, just under different names. If you’re not formally educated in computer science, then you may not even realize that you’ve been using them all along.
Here are some implementations of hash tables from popular languages:
- Java HashMaps
- Python dictionaries
- JSON objects
- PHP associative arrays
Hash tables are not reserved just for programming. They’re all around us in the real world too. You can find hash tables in:
- IDs, such as social security numbers and driver’s licenses
- The Dewey Decimal System at your local library
- Phone numbers
To understand why hash tables are so amazing, we’re going to give a non-technical explanation about what they are and then explore the implications of using hash tables.
What Is Hashing?
Before we flesh out what a hash table is, let’s define hashing. According to HackerEarth, “Hashing is a technique that is used to uniquely identify a specific object from a group of similar objects.”
In other words, hashing is the process of creating a unique identifier. This is done through the use of a predefined function that, given the same input, will always produce the same output.
Have you ever downloaded an install file and seen a SHA1 or MD5 checksum next to the link? Those are hashes of the executable so you can be confident the file you are installing has not been tampered with.
What Is a Hash Table?
Now that we know a hash is nothing more than a predictably generated identifier, let’s pull back the curtain on what a hash table is.
A hash table is the product of a hash function that has two parts.
First, the result of the hash (also called a search key) functions as the identifier to a specific space that holds data. In the case of a library book’s Dewey number, that translates to a row and shelf. In the case of a programming language, that translates to an index in an array.
When hashing is being implemented, it is a near guarantee that two values will produce the same hash result. This event is called a collision, and the way they are resolved is the second part of a hash function’s definition.
There are a variety of different collision resolution techniques. They’re beyond the scope of this article, but the main takeaway is that the technique will impact how efficiently the hash table scales.
What Is the Impact of Hash Tables?
Now that we’ve gone over what hash tables are, we can explore how hash tables impact our code. A primary impact of hash tables is their constant time complexity of O(1), meaning that they scale very well when used in algorithms.
Searching over a data structure such as an array presents a linear time complexity of O(n). In other words, as the data structure increases in size, the search time increases in a linear fashion.
Simply put, using a hash table is faster than searching through an array.
In the Find the First Non-Repeating Character algorithm challenge, we use hash tables as an optimal solution compared to nested for loops, which is a reduction in complexity from O(n*n) to O(n).
Another impact of hash tables is that they are excellent for storing paired data. This was my first introduction to hash tables in the form of JavaScript Object Notation (JSON). To me, key-value pairs were an easy way of connecting two fields like { "First Name": "Jonathan" }.
Conclusion
Ultimately, hash tables are both convenient and efficient. They help make sense of data as named identifiers and speed things up on the back end. Being a data structure that inherently reduces time complexity, hash tables border on cheat code status.
I hope this article was helpful at explaining how hash tables work and why they are valuable. Keep practicing and leave your comments and feedback below!