Hash Maps
A hash function turns a key into a bucket index, so storing and finding a value both take constant time on average.
Loading visual…
Definition
A hash map stores key/value pairs by running each key through a hash function that produces a number, then using that number to pick a bucket, a slot in an underlying array, to store the entry. Because the bucket is computed directly from the key instead of found by scanning, both inserting and looking up a value take O(1) time on average, regardless of how many entries are already in the map. Two different keys can hash to the same bucket, which is called a collision. Rather than failing, a hash map handles this by chaining: the bucket holds a small list of entries instead of just one, and a lookup that lands in that bucket scans the short chain to find the matching key. As long as the hash function spreads keys out reasonably evenly, chains stay short and the average O(1) behavior holds; a bad hash function or an adversarial set of keys can degrade this toward O(n) in the worst case. JavaScript's `Map` and, with caveats, plain objects are both concrete implementations of this idea.
Examples
const ages = new Map();
ages.set("cat", 4);
ages.set("dog", 7);
ages.get("dog"); // 7
ages.has("fox"); // falseset hashes the key to pick a bucket and stores the value there; get hashes the same key to jump straight to that bucket instead of scanning every entry.
function countChars(str) {
const counts = new Map();
for (const ch of str) {
counts.set(ch, (counts.get(ch) || 0) + 1);
}
return counts;
}
countChars("banana"); // Map(3) { 'b' => 1, 'a' => 3, 'n' => 2 }Each character is a key whose bucket is checked and updated in one step, so the whole string is counted in a single O(n) pass.
function twoSum(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (seen.has(need)) return [seen.get(need), i];
seen.set(nums[i], i);
}
return [-1, -1];
}
twoSum([2, 7, 11, 15], 9); // [0, 1]Instead of requiring a sorted array like the two-pointer version, this checks for the needed complement in the map's bucket directly, working on any order of input.
Common mistakes
- Assuming O(1) lookup is guaranteed in the worst case; a poor hash function or heavy collisions can degrade it toward O(n).
- Using a plain object as a hash map and forgetting that most keys are coerced to strings, which can silently merge distinct numeric and string keys.
- Iterating a plain object with for...in and picking up inherited properties, instead of using Map, which only iterates its own entries.
Key takeaways
- A hash function converts a key into a bucket index, giving average O(1) insert, lookup, and delete.
- Collisions, two keys hashing to the same bucket, are normal and are handled by chaining multiple entries in one bucket.
- Map preserves insertion order and accepts any value as a key, while plain objects coerce most keys to strings.
Two different keys hash to the same bucket index. What does a hash map do?
Where you see this
- Deduplicating a list by tracking which values have already been seen.
- Caching (memoizing) expensive function results keyed by their arguments.
- Counting frequencies of words, characters, or events in a single pass.
- Building an index that looks up a record by id without scanning every record.