Interview Cake 
Quick reference
| Average | Worst Case | |
|---|---|---|
| space | O(n) | O(n) |
| insert | O(1) | O(n) |
| lookup | O(1) | O(n) |
| delete | O(1) | O(n) |
A hash table (also called a hash map) is a data structure that stores key-value pairs. It runs each key through a hashing function to figure out where in an underlying array to store it, so it can look up, insert, and delete values by key in O(1) time on average.
Strengths:
- Fast lookups. Lookups take time on average.
- Flexible keys. Most data types can be used for keys, as long as they're hashable.
Weaknesses:
- Slow worst-case lookups. Lookups take time in the worst case.
- Unordered. Keys aren't stored in a special order. If you're looking for the smallest key, the largest key, or all the keys in a range, you'll need to look through every key to find it.
- Single-directional lookups. While you can look up the value for a given key in time, looking up the keys for a given value requires looping through the whole dataset— time.
- Not cache-friendly. Many hash table implementations use linked lists, which don't put data next to each other in memory.
In JavaScript
In JavaScript, hash tables are called objects.
What about JavaScript maps? Objects are way more common, but maps might be helpful if your keys aren't strings or you need to iterate over your data. One thing to know: maps aren't fully supported by all modern browsers yet.
Hash maps are built on arrays
Arrays are pretty similar to hash maps already. Arrays let you quickly look up the value for a given "key" . . . except the keys are called "indices," and we don't get to pick them—they're always sequential integers (0, 1, 2, 3, etc).
Think of a hash map as a "hack" on top of an array to let us use flexible keys instead of being stuck with sequential integer "indices."
All we need is a function to convert a key into an array index (an integer). That function is called a hashing function.
To look up the value for a given key, we just run the key through our hashing function to get the index to go to in our underlying array to grab the value.
How does that hashing function work? There are a few different approaches, and they can get pretty complicated. But here's a simple proof of concept:
Grab the number value for each character and add those up.
The result is 429. But what if we only have 30 slots in our array? We'll use a common trick for forcing a number into a specific range: the modulus operator (%). Modding our sum by 30 ensures we get a whole number that's less than 30 (and at least 0):
The hashing functions used in modern systems get pretty complicated—the one we used here is a simplified example.
Hash collisions
What if two keys hash to the same index in our array? In our example above, look at "lies" and "foes":
They both sum up to 429! So of course they'll have the same answer when we mod by 30:
This is called a hash collision. There are a few different strategies for dealing with them.
Here's a common one: instead of storing the actual values in our array, let's have each array slot hold a pointer to a linked list holding the values for all the keys that hash to that index:
Notice that we included the keys as well as the values in each linked list node. Otherwise we wouldn't know which key was for which value!
There are other ways to deal with hash collisions. This is just one of them.
When hash table operations cost time
Hash collisions
If all our keys caused hash collisions, we'd be at risk of having to walk through all of our values for a single lookup (in the example above, we'd have one big linked list). This is unlikely, but it could happen. That's the worst case.
Dynamic array resizing
Suppose we keep adding more items to our hash map. As the number of keys and values in our hash map exceeds the number of indices in the underlying array, hash collisions become inevitable.
To mitigate this, we could expand our underlying array whenever things start to get crowded. That requires allocating a larger array and rehashing all of our existing keys to figure out their new position— time.
Sets
A set is like a hash map except it only stores keys, without values.
Sets often come up when we're tracking groups of items—nodes we've visited in a graph, characters we've seen in a string, or colors used by neighboring nodes. Usually, we're interested in whether something is in a set or not.
Sets are usually implemented very similarly to hash maps—using hashing to index into an array—but they don't have to worry about storing values alongside keys.
Hash Map vs. Hash Table vs. Hash Set
These three names get mixed up a lot. Here's how they relate:
- Hash table and hash map are two names for the same data structure: key-value pairs stored in an array, with a hashing function to find each key's spot. Which name you hear mostly depends on the language you're using.
- A hash set uses the same hashing trick, but it stores only keys, with no values attached. Use one when all you care about is whether something is there.
| Hash table / hash map | Hash set | |
|---|---|---|
| Stores | Key-value pairs | Just keys |
| Answers | "What's the value for this key?" | "Is this item in the set?" |
| Duplicates | Keys are unique (values can repeat) | Items are unique |
| Insert, lookup, delete | O(1) on average, O(n) worst case | O(1) on average, O(n) worst case |
Hash Table/Hashing interview questions to practice
Each one walks you through a real coding interview problem one hint at a time.
- Word Cloud Data » You're building a word cloud. Write a function to figure out how many times each word appears so we know how big to make each word in the cloud.
- Find Duplicate Files » Your friend copied a bunch of your files and put them in random places around your hard drive. Write a function to undo the damage.
Your first 3 questions are free. Just sign in, no credit card. More Hash Table/Hashing questions
See also:
Interview coming up?
Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.
No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.
No spam. One-click unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!
