Overview
A hash table turns a key into an array index with a hash function, giving average O(1) insert, delete and lookup. Whenever a brute-force solution asks "have I seen something like this before?" inside a loop, a hash map or set can usually remove that inner loop entirely.
Two keys can hash to the same slot (a collision). Real implementations handle this with chaining or open addressing and resize as they fill, which keeps the average cost constant. The worst case is still O(n), which matters in competitive programming where adversarial tests target std::unordered_map.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| Insert / lookup / delete | O(1) average, O(n) worst |
| Iterate all entries | O(n) |
| std::map / TreeMap operations | O(log n) |
Patterns to recognise
Complement lookup
Use it for: Find two items that combine to a target.
For each x, check whether target − x is already in the map, then insert x.
Seen set
Use it for: Duplicates, cycles in sequences (happy number), first unique element.
Insert as you go and stop the moment an item repeats.
Grouping
Use it for: Bucket items that share a property.
map[key].append(item) — then read the groups.
Code template
def two_sum(nums, target):
index_of = {}
for i, x in enumerate(nums):
if target - x in index_of:
return [index_of[target - x], i]
index_of[x] = i # insert after checking
return []
vector<int> twoSum(const vector<int>& nums, int target) {
unordered_map<int, int> indexOf;
for (int i = 0; i < (int)nums.size(); ++i) {
auto it = indexOf.find(target - nums[i]);
if (it != indexOf.end()) return {it->second, i};
indexOf[nums[i]] = i; // insert after checking
}
return {};
}
Common mistakes
- Inserting before checking lets an element pair with itself.
- Python lists are unhashable — convert to a tuple before using them as keys.
- In C++,
map[key]silently inserts a default value; usefindorcountto test membership. - Never mutate a map while iterating over it.
Quick check
Three questions on Hashing. Get all three right to earn +15 XP.
-
What is the average cost of looking up a key in a hash map?
The hash sends you straight to a bucket. Only heavy collisions degrade it toward O(n).
-
In Two Sum with a hash map, what do you look up for each number x?
If target - x was seen earlier, the two together make the target.
-
Which of these cannot be used directly as a hash map key in Python?
Keys must be hashable and therefore immutable. Convert the list to a tuple first.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Two SumLeetCode Easy +20
- Ransom NoteLeetCode Easy +20
- Isomorphic StringsLeetCode Easy +20
- Happy NumberLeetCode Easy +20
- Longest Consecutive SequenceLeetCode Medium +40
- Top K Frequent ElementsLeetCode Medium +40
- Insert Delete GetRandom O(1)LeetCode Medium +40
- LRU CacheLeetCode Medium +40
Stuck on Hashing?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor