DSA TrainerFoundations · Unit 2
Hash Maps
You have a list of a million users and you need to find the one with a specific email. If all you have is an array, you check the first user, then the next, then the next, until you find a match or run out. On average you touch half the list. That is slow, and it gets slower as the list grows.
A hash map fixes exactly this. Instead of scanning, it lets you jump straight to the thing you are looking for, in roughly the same amount of time whether the map holds ten items or ten million. That one property, instant lookup by key, is why hash maps show up in more interview solutions than any other data structure.
The trick is that a hash map does not store things in a line you have to walk. It stores each value at an address computed from its key, so finding it later is a direct jump, not a search. This unit walks through how that works and, more importantly, how to recognize the kind of problem that is begging for one.
You’re not signed in. Your progress here won’t be saved.
The problem: searching a list is slow
Picture an array of names and you want to know if "Maria" is in it. With nothing but the array, you have one option: start at the front and compare each name until you find Maria or hit the end.
If Maria is near the end, or not there at all, you looked at every single element. Double the size of the list and you double the work. That is the linear scan, and it is the bottleneck a hash map is built to remove.
You have an unsorted array of n names and you check whether a given name is in it by comparing one at a time. In the worst case, how many names do you look at?