How Hashing Works
A hash map converts a key to a bucket index via: index = hash(key) % table_size. If two keys map to the same bucket (collision), they're stored in a linked list there (chaining). Average case: O(1). Worst case (all collide): O(n).
C++ containers:
unordered_map = O(1) average. map = O(log n) ordered. Prefer unordered_map for speed unless you need sorted keys.C++ Hash Containers
unordered_map
Key → Value. O(1) avg. Use for lookup, grouping, memoization.
unordered_map<int,int> mp;
unordered_set
Keys only. O(1) membership check. Use for deduplication.
unordered_set<int> s;
map / set
Ordered (BST-backed). O(log n). Use when sorted order matters.
map<int,int> mp;
6 Core Use Cases
Frequency Count
Count occurrences of each element.
mp[x]++;Complement Lookup
Check if (target-x) was seen.
mp.count(target-x)Memoization
Cache recursive results.
memo[state]=resultGrouping
Group by a computed key.
mp[key].push_back(v)Index Tracking
Remember where you saw something.
seen[val]=indexDeduplication
Fast membership check.
s.count(x) → foundCore Pattern Code
Frequency Map
C++
// Count frequency of each element
unordered_map<int,int> freq;
for (int x : arr) freq[x]++;
// Access and check
freq[5]; // count of 5 (0 if not present)
freq.count(5); // 1 if exists, 0 if not
freq.find(5) != freq.end(); // same as count
// Iterate
for (auto& [key, val] : freq)
cout << key << ": " << val << "\n";
Grouping by Computed Key (Group Anagrams)
C++
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for (auto& s : strs) {
string key = s;
sort(key.begin(), key.end()); // anagram key
mp[key].push_back(s);
}
vector<vector<string>> res;
for (auto& [k, v] : mp) res.push_back(v);
return res;
}
// Time: O(n·k·log k) Space: O(n·k)
Interactive: Hash Table Insert with Chaining
8 buckets, h(k)=k mod 8. Watch how keys map to buckets and collisions form chains.
Deeper Understanding
🧠 Under the Hood
Under the hood, unordered_map maintains an array of "bucket" lists. The hash function maps your key to a bucket index in O(1). If two keys share a bucket (collision), they are chained in a linked list inside that bucket. As the load factor (n/capacity) grows past ~0.75, the table automatically doubles its capacity and reinserts all keys — this rehash is O(n) but happens rarely.
⚖️ When to Use / When NOT to Use
✅ Use when you need O(1) lookup, insert, or delete by key
No structure beats a hash map for membership and frequency counting.
✅ Use when you need to count or group elements
freq[x]++ is a one-liner that replaces an inner loop, turning O(n²) → O(n).
❌ Avoid when you need keys in sorted order
Instead: Use std::map (O(log n)) or sort the keys separately. unordered_map iteration order is undefined.
❌ Avoid when keys are unhashable (pair<int,int>, vector)
Instead: Encode as a string key, or use map<pair<int,int>, V> (ordered, O(log n)).
❌ Avoid when worst-case guarantees matter
Instead: A poorly chosen hash can degrade to O(n) per op. Use map for guaranteed O(log n).
🚫 Common Misconceptions
❌ "unordered_map is always O(1)"
Worst case is O(n) when all keys collide into the same bucket. Custom hash or adversarial input can trigger this — rare in practice, but real in competitive programming.
❌ "Iteration order is insertion order"
unordered_map iteration order is implementation-defined and NOT stable between runs. If you need insertion order, use a separate vector or std::vector of pairs.
❌ "map and unordered_map are interchangeable"
map: sorted keys, O(log n) per op, no hash needed. unordered_map: O(1) avg, unsorted. Pick based on whether you need ordered iteration or floor/ceil queries.
🎤 Interview Follow-ups
Q: How does rehashing work?
When load factor > threshold (~0.75), allocate a new array of double size and reinsert all existing keys (O(n)). Amortized O(1) per insert overall.
Q: unordered_map vs map — when to use each?
unordered_map for fast lookup when order doesn't matter. map when you need lower_bound / upper_bound, iterate in sorted order, or keys can't be hashed.
Q: How would you design a hash for pair<int,int>?
Combine with XOR or polynomial: hash = first * 1e9+7 + second. Or encode as a string key. Production: use boost::hash_combine.
Practice Problems
#217Contains DuplicateEasy
Return true if any value appears at least twice.
Pattern: Insert into set. If already present → duplicate.
C++
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> seen;
for (int n : nums) {
if (seen.count(n)) return true;
seen.insert(n);
}
return false;
}
// Time: O(n) Space: O(n)
#242Valid AnagramEasy
Return true if t is an anagram of s (same characters, same counts).
Pattern: Count[26] array. Increment for s, decrement for t. All zeros → anagram.
C++
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
int cnt[26] = {};
for (int i = 0; i < s.size(); i++) {
cnt[s[i]-'a']++;
cnt[t[i]-'a']--;
}
for (int c : cnt) if (c != 0) return false;
return true;
}
// Time: O(n) Space: O(1) — 26 letters
#347Top K Frequent ElementsMedium
Return k most frequent elements. [1,1,1,2,2,3], k=2 → [1,2].
Pattern (Bucket Sort): Frequency ≤ n, so create n+1 buckets. Fill by freq, read from top down.
C++
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> freq;
for (int n : nums) freq[n]++;
int n = nums.size();
vector<vector<int>> buckets(n+1);
for (auto& [val, cnt] : freq)
buckets[cnt].push_back(val);
vector<int> res;
for (int i = n; i >= 1 && res.size() < k; i--)
for (int v : buckets[i]) res.push_back(v);
return res;
}
// Time: O(n) Space: O(n)
#560Subarray Sum Equals KMedium
Count subarrays with sum equal to k. [1,1,1], k=2 → 2.
Pattern: Prefix sum + hash map. If prefix[j] - prefix[i] = k → subarray [i+1..j] sums to k. Check (prefix - k) in map.
C++
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int> seen = {{0,1}};
int count = 0, prefix = 0;
for (int n : nums) {
prefix += n;
count += seen[prefix - k]; // 0 if not found
seen[prefix]++;
}
return count;
}
// Time: O(n) Space: O(n)
#49Group AnagramsMedium
Group strings that are anagrams of each other into sublists.
Pattern: Sort each word → same key for all anagrams. Group by sorted key.
C++
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for (auto& s : strs) {
string key = s;
sort(key.begin(), key.end());
mp[key].push_back(s);
}
vector<vector<string>> res;
for (auto& [k,v] : mp) res.push_back(v);
return res;
}
#1Two Sum (Hash Map Pattern)Easy
Return indices of two numbers summing to target. The canonical hash map pattern.
Pattern: complement = target - num. Check if complement seen. Store num → index.
C++
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> seen;
for (int i = 0; i < nums.size(); i++) {
int comp = target - nums[i];
if (seen.count(comp)) return {seen[comp], i};
seen[nums[i]] = i;
}
return {};
}
// Memorize this pattern — it appears in 30+ problems
#169Majority ElementEasy
Find element appearing more than n/2 times. O(1) space required.
Boyer-Moore Voting: Majority "survives" pairing against different elements. count=0 → pick new candidate.
C++
int majorityElement(vector<int>& nums) {
int count = 0, candidate = 0;
for (int n : nums) {
if (count == 0) candidate = n;
count += (n == candidate) ? 1 : -1;
}
return candidate;
}
// Time: O(n) Space: O(1)
#383Ransom NoteEasy
Can ransomNote be built using letters from magazine (each letter used once)?
Pattern: Count[26] of magazine. Subtract each letter of ransomNote. Negative count → impossible.
C++
bool canConstruct(string ransomNote, string magazine) {
int cnt[26] = {};
for (char c : magazine) cnt[c-'a']++;
for (char c : ransomNote) {
if (--cnt[c-'a'] < 0) return false;
}
return true;
}
// Time: O(m+n) Space: O(1)
#242Valid AnagramEasy
Given strings s and t, return true if t is an anagram of s.
Pattern: Count characters in s with a hash map, decrement for each char in t. Any negative count or leftover key means not an anagram.
C++
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
unordered_map<char,int> cnt;
for (char c : s) cnt[c]++;
for (char c : t) { if (--cnt[c] < 0) return false; }
return true;
}
// Time: O(n) Space: O(1) — at most 26 distinct chars
#128Longest Consecutive SequenceMedium
Find the length of the longest sequence of consecutive integers. Must be O(n).
Pattern: Insert all into a hash set. Only start counting from n where (n−1) is NOT in the set — these are true sequence starts. Avoid re-counting sub-sequences.
C++
int longestConsecutive(vector<int>& nums) {
unordered_set<int> s(nums.begin(), nums.end());
int best = 0;
for (int n : s) {
if (!s.count(n - 1)) { // sequence start
int cur = n, len = 1;
while (s.count(cur + 1)) { cur++; len++; }
best = max(best, len);
}
}
return best;
}
// Time: O(n) Space: O(n)
#560Subarray Sum Equals KMedium
Count the number of contiguous subarrays whose sum equals k.
Pattern: Prefix sum + hash map. For each prefix sum P, look up how many times (P−k) has appeared — each occurrence is a valid subarray ending here.
C++
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int> prefixCnt = {{0,1}}; // empty prefix
int sum = 0, ans = 0;
for (int x : nums) {
sum += x;
ans += prefixCnt[sum - k]; // subarrays ending here summing to k
prefixCnt[sum]++;
}
return ans;
}
// Time: O(n) Space: O(n)
#49Group AnagramsMedium
Group an array of strings by anagram family. Order within groups doesn't matter.
Pattern: Sorted string as hash key — all anagrams share the same sorted form. Map<sortedStr, group>.
C++
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string,vector<string>> mp;
for (auto& s : strs) {
string key = s; sort(key.begin(), key.end());
mp[key].push_back(s);
}
vector<vector<string>> res;
for (auto& [k,v] : mp) res.push_back(v);
return res;
}
// Time: O(n·k·log k) Space: O(n·k)
#76Minimum Window SubstringHard
Find the minimum length substring of s that contains all characters of t (including duplicates).
Pattern: Sliding window + two frequency maps. Expand right until window is valid (all t chars covered), shrink left to minimize, track best window.
C++
string minWindow(string s, string t) {
unordered_map<char,int> need, win;
for (char c : t) need[c]++;
int have=0, req=need.size(), l=0, best=INT_MAX, bl=0;
for (int r=0; r<s.size(); r++) {
char c=s[r]; win[c]++;
if(need.count(c)&&win[c]==need[c]) have++;
while(have==req) {
if(r-l+1<best){best=r-l+1;bl=l;}
char lc=s[l++]; win[lc]--;
if(need.count(lc)&&win[lc]<need[lc]) have--;
}
}
return best==INT_MAX?"":s.substr(bl,best);
}
// Time: O(|s|+|t|) Space: O(|s|+|t|)
Golden Rule: When an inner loop searches for something → that's your O(n²) signal. Replace the search with an unordered_map lookup and get O(n).