DSA · Lesson 4 of 20 · 4 min
Objects and Hash Maps in JavaScript
This is your default tool for optimizing loops. Knowing when and how to use it signals you can write efficient code.
How to turn O(N²) into O(N)
Many interview problems involve checking for items between two collections. A naive approach uses nested loops, resulting in O(N*M) time complexity. If you see yourself writing a nested loop just to find or count things, stop. You can almost always do better with a hash map.
The strategy is to trade memory for time. You make one pass over a collection to build a hash map, which gives you near-instant O(1) lookups. Then you make a single pass over the second collection, using the map to find what you need. This reduces the overall time complexity to O(N + M).
This is called the "frequency counter" pattern, but it's used for more than just counting. You can store counts, indices, or just a true value to indicate presence.
/**
* Counts the frequency of each character in a string.
* This is a classic "frequency counter" implementation.
* @param {string} str The input string.
* @returns {Record<string, number>} An object where keys are characters and values are their counts.
*/
function getCharFrequencies(str) {
const charCounts = {};
for (const char of str) {
// If char is not a key, `charCounts[char]` is undefined.
// The `|| 0` sets it to 0, then we add 1.
// If it exists, we just increment it.
charCounts[char] = (charCounts[char] || 0) + 1;
}
return charCounts;
}
const sentence = "hello world";
const frequencies = getCharFrequencies(sentence);
// frequencies is { h: 1, e: 1, l: 3, o: 2, ' ': 1, w: 1, r: 1, d: 1 }
This single loop builds a map in O(N) time. Any subsequent lookup, like frequencies['l'], is O(1).
How a hash map gives you O(1) lookups
You don't need to implement a hash map from scratch in an interview, but you must know why it's fast.
A hash map uses an array under the hood. When you add a key-value pair, a hashing function converts the key into a hash code. This code is then mapped to an index in the array. The value is stored at that index.
Retrieval is the same process: the key is hashed to find the index, and the value is read directly. This is why it's O(1) on average.
The trap: An interviewer might ask what happens when two different keys hash to the same index. This is a "collision." The common solution is to store a list of key-value pairs at that index. In the worst case, all keys collide, and lookup becomes O(N) because you have to search the list. For typical string keys in JavaScript, this is not a practical concern, but you should know the concept.
When to use Map instead of a plain {}
For most hash map use cases in interviews, a plain object ({}) is fine. But you need to know when a Map is the correct tool. An interviewer will expect you to know the difference.
There are three main reasons to reach for Map:
- Non-string keys. A plain object coerces all keys into strings.
obj[1]andobj['1']are the same. If you need to use objects, arrays, or functions as keys, you must use aMap. A common frontend scenario is mapping DOM nodes to metadata. - Guaranteed insertion order. A
Mapiterates over its elements in the order they were inserted. While modern JS engines preserve insertion order for non-numeric string keys in plain objects, it's a specification detail you shouldn't rely on if order is critical.Mapguarantees it. - Cleaner API and no prototype conflicts.
Maphas a.sizeproperty,.has(),.get(), and.set()methods. To get the size of an object, you have to callObject.keys(obj).length. AMapis also a pure dictionary, whereas a plain object inherits fromObject.prototype, meaning keys like "toString" could cause unexpected behavior.
For a pure data dictionary with string keys, you can also use
Object.create(null). This creates an object with no prototype, avoiding any potential key collisions with built-in methods. But if you're considering that,Mapis often the cleaner choice.
Recognizing hash map problems
Your brain should jump to "hash map" when you see problems involving:
- Counting frequencies. The most obvious one. Used in [/problems/valid-anagram](Valid Anagram) and [/problems/ransom-note](Ransom Note).
- Finding duplicates or unique elements. Store items in a map as you iterate; if you see one that's already there, you've found a duplicate.
- Finding a pair that meets a condition. The classic [/problems/two-sum](Two Sum) problem is solved by storing numbers and their indices in a map. For each element
x, you can instantly check iftarget - xexists in the map. - Caching or memoization. Storing the results of expensive function calls to avoid re-computation. The function arguments are the key, and the result is the value.
Try it
Write a function that solves [/problems/first-unique-character-in-a-string](First Unique Character in a String). Use a hash map to store character counts. Your solution should use two separate, non-nested loops: one to build the frequency map, and a second to find the first character with a count of 1. This reinforces the O(N) approach.
Next: We'll cover Linked Lists: Building Blocks, a structure that's less common in frontend code but crucial for understanding other data structures.
Lock it in — apply this lesson under interview conditions.