Hash Maps
On this page
The first idea for many problems is a loop inside a loop: for every element, search the rest for something. That's O(n²), and with 10⁵ elements it is too slow. A hash map fixes this by remembering what you have already seen, so "search the rest" becomes a single O(1) lookup. It is the most common way to turn a nested loop into one pass.
How it works
Key → hash → bucket

A hash map keeps an array of buckets. To store a key, it runs the key through a hash function, which turns it into a number, and uses that number (modulo the array size) to pick a bucket. Looking a key up repeats the same steps, so it goes straight to the right bucket instead of scanning everything.
Two different keys can land in the same bucket. This is a collision, and there are two common fixes:
- Chaining: each bucket holds a small list, and colliding keys share it. Java's
HashMapworks this way. - Open addressing: on a collision, probe the next free slot in the array. Python's
dictworks this way.
Resizing keeps it fast

When the map gets too full (the load factor, keys divided by buckets, passes a threshold, often around 0.75), it allocates a bigger array and moves every key. That single resize is slow, but it happens rarely enough that inserts stay O(1) on average. This is called amortized constant time.
A hash set is the same structure with keys only and no values. Use it when you only need "have I seen this?".
Operations and costs
| Operation | Average | Worst case |
|---|---|---|
| Insert or update | O(1) | O(n) |
| Look up a key | O(1) | O(n) |
| Delete a key | O(1) | O(n) |
| Iterate over all entries | O(n) | O(n) |
The worst case happens when many keys collide into one bucket. With a decent hash function it is rare, and in interviews you can state "O(1) average" and move on. The real cost is memory: O(n) extra space for n keys.
When to reach for it
Listen for these questions inside the problem:
- "Have I seen this before?" Duplicates, first unique character, cycle detection by remembering visited states.
- "How many of each?" Counting frequencies, anagram checks, top-K by frequency.
- "Is the partner I need already here?" Complement lookups, as in Two Sum.
- "Group these by something." Grouping anagrams by their sorted letters, grouping events by user.
- "Remember an index or a position." Longest substring without repeats stores the last index of each character; subarray sums store the first index of each running total.
Example
Pattern 1: complement lookup
Given a list of numbers and a target, return the indices of two numbers that add up to the target. The brute force checks every pair, which is O(n²). With a hash map, walk the list once, and for each number ask whether its complement (target − x) was already seen.

def two_sum(nums, target):
seen = {} # value -> index
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
return []
int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>(); // value -> index
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (seen.containsKey(need)) {
return new int[] { seen.get(need), i };
}
seen.put(nums[i], i);
}
return new int[0];
}
vector<int> twoSum(const vector<int>& nums, int target) {
unordered_map<int, int> seen; // value -> index
for (int i = 0; i < (int)nums.size(); i++) {
int need = target - nums[i];
auto it = seen.find(need);
if (it != seen.end()) return {it->second, i};
seen[nums[i]] = i;
}
return {};
}
func twoSum(nums []int, target int) []int {
seen := make(map[int]int) // value -> index
for i, x := range nums {
if j, ok := seen[target-x]; ok {
return []int{j, i}
}
seen[x] = i
}
return nil
}
Time: O(n), one pass. Space: O(n) for the map.
Note the order: check for the complement before storing the current number. That way a number never pairs with itself, and [3, 3] with target 6 still works.
Pattern 2: counting
Check whether two strings are anagrams: count each character in the first string, subtract counts for the second, and every count must end at zero.
from collections import Counter
def is_anagram(s, t):
return len(s) == len(t) and Counter(s) == Counter(t)
boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
Map<Character, Integer> count = new HashMap<>();
for (char c : s.toCharArray()) count.merge(c, 1, Integer::sum);
for (char c : t.toCharArray()) {
if (count.merge(c, -1, Integer::sum) < 0) return false;
}
return true;
}
bool isAnagram(const string& s, const string& t) {
if (s.size() != t.size()) return false;
unordered_map<char, int> count;
for (char c : s) count[c]++;
for (char c : t) {
if (--count[c] < 0) return false;
}
return true;
}
func isAnagram(s, t string) bool {
if len(s) != len(t) {
return false
}
count := make(map[rune]int)
for _, c := range s {
count[c]++
}
for _, c := range t {
count[c]--
if count[c] < 0 {
return false
}
}
return true
}
Time: O(n). Space: O(k), where k is the number of distinct characters. If the input is only lowercase letters, a fixed array of 26 counters does the same job with less overhead, and it's a nice follow-up to mention.
Common mistakes
- Using mutable keys. A Python list can't be a key; use a tuple. In Java, changing an object after it is used as a key breaks lookups.
- Assuming order. Python's
dictkeeps insertion order, but Java'sHashMap, C++'sunordered_mapand Go'smapdo not. Use a sorted map or sort the keys when order matters. - Custom objects as keys. In Java you must override both
equalsandhashCode; in C++ you must supply a hash. - Storing before checking. In complement problems, storing the current element first lets it pair with itself.
- Forgetting memory. O(1) time costs O(n) space. If the interviewer asks for O(1) space, think sorting plus two pointers instead.
Say this in the interview
- "The brute force is O(n²) because for each element I search the rest. If I store what I've seen in a hash map, each lookup is O(1) on average, so the whole thing is O(n) time and O(n) space."
- "Worst-case lookups are O(n) if everything collides, but with a standard library hash map that's not a practical concern."
- "Since the keys are only lowercase letters, an array of 26 counts would work too and avoids hashing."
Used in
- Coding: Two Sum, Valid Anagram, Group Anagrams, Longest Substring Without Repeating Characters, Subarray Sum Equals K, LRU Cache (hash map plus a linked list), Top K Frequent Elements
- Pattern: Hash Maps and Prefix Sums
- System design: the same idea scales up into caches, rate limiters and consistent hashing (see the System Design track's Cache and Consistent Hashing articles).