What is a hash map?

Think of the contacts on your phone. You never remember that a friend is contact number 47 — you search by their name and get their number. A hash map works the same way. It stores pairs: a key (what you look things up by) and a value (what you get back), and it can find any key in about one step, whether it holds ten entries or ten million.

Other names for the same idea: hash table, dictionary (Python's dict), map (Map in JavaScript, HashMap in Java, unordered_map in C++), or associative array. They all mean: keys in, values out, fast.

Array or hash map?

An array finds things by position: give it an index and it returns that slot instantly. But ask an array "where is kiwi?" and it has no choice but to check slot after slot — O(n). A hash map turns the key itself into a slot number (the next lesson shows how), so it jumps straight to the answer — O(1) on average.