Hashing — Hash Maps & Hash Sets

Hash Maps & Hash Sets · Collision Handling · Frequency Counting · Grouping — the single most powerful technique for reducing O(n²) solutions to O(n).

11 Sections 13 Practice Problems Intermediate ← Back to Roadmap

Section 1 — What Is Hashing?

Hashing is the process of converting a key of any type into a fixed-size integer (the hash code) and using that integer as an index into an array (the hash table). This gives us O(1) average-case insertion, deletion, and lookup — regardless of how many elements are stored.

Why Hashing Matters This is the single most powerful technique for reducing O(n) or O(n²) solutions to O(n). Almost every medium-hard problem that does not involve ordering or hierarchy has a hash-based optimal solution.

1.1 — Hash Function & Collision Handling

A hash function maps keys to indices. Two keys can hash to the same index — a collision. C++ resolves collisions via chaining (linked list at each index) in unordered_map.

Chaining: Each bucket holds a linked list. Average O(1); worst case O(n) if all keys collide.
Load factor: When table is ≥ 75% full, it rehashes to a larger table. O(n) but amortized O(1).
In C++: unordered_map uses open addressing with std::hash internally.

1.2 — C++ API

```cpp // unordered_map — key-value store unordered_map freq; freq["hello"]++; // insert or increment freq.count("world"); // 0 or 1 — check existence freq.find("hello"); // returns iterator freq.erase("hello"); // remove key

// unordered_set — existence only unordered_set seen; seen.insert(42); seen.count(42); // 1 if exists, 0 if not

// Default int value in map is 0 unordered_map<int,int> cnt; cnt[key]++; // OK — default-initialises to 0 then increments

</div>
<div class="ch-cplx-row">
  <span class="ch-cplx"><span>All ops average</span>O(1)</span>
  <span class="ch-cplx"><span>Space</span>O(n)</span>
  <span class="ch-cplx"><span>Worst case</span>O(n)</span>
</div>
</div>
<div class="chapter-section">
<h2 class="section-heading">Section 2 — Pattern: Existence Check</h2>
<p>Use <code>unordered_set</code> when you just want to know if a value has been seen. O(1) average per lookup.</p>
<div class="ch-code-wrap">
```cpp
// Pangram check — has the sentence all 26 letters?
unordered_set<char> letters(sentence.begin(), sentence.end());
return letters.size() == 26;

// Has any duplicate?
unordered_set<int> seen;
for (int x : nums) {
    if (seen.count(x)) return true; // duplicate found
    seen.insert(x);
}
return false;

Section 3 — Pattern: Frequency Count

Use unordered_map<T, int> to count how many times each element appears. Foundation for anagram, top-K, most-frequent problems.

```cpp // Frequency count for any iterable unordered_map freq; for (int x : arr) freq[x]++;

// Is Anagram — same char frequencies? unordered_map<char,int> cnt; for (char c : s) cnt[c]++; for (char c : t) { if (—cnt[c] < 0) return false; } return true;

// Top K frequent elements — combine freq map + heap unordered_map<int,int> freq; for (int x : nums) freq[x]++; priority_queue<pair<int,int>, vector<pair<int,int>>, // min-heap by frequency greater<pair<int,int>>> pq; for (auto& [val, cnt] : freq) { pq.push({cnt, val}); if (pq.size() > k) pq.pop(); }

</div>
</div>
<div class="chapter-section">
<h2 class="section-heading">Section 4 — Pattern: Two-Sum Lookup</h2>
<p>For each element x, check if its complement (target - x) exists in the hash map. One-pass O(n).</p>
<div class="insight-box">
  <span class="insight-label">General Two-Sum Pattern</span>
  Store what you have seen so far. For each new element, ask: "Is its complement already here?" This converts O(n²) nested search into O(n) with one hash table lookup.
</div>
<div class="ch-code-wrap">
```cpp
// Classical two-sum — return indices
unordered_map<int,int> seen; // val → index
for (int i = 0; i < nums.size(); i++) {
    if (seen.count(target - nums[i]))
        return {seen[target-nums[i]], i};
    seen[nums[i]] = i;
}
// Counting elements (x+1 exists for all x in set)
unordered_set<int> s(arr.begin(), arr.end());
int count = 0;
for (int x : arr) if (s.count(x+1)) count++;
return count;

Section 5 — Pattern: Grouping

Map a grouping key to a list of all elements sharing that key. Classic example: group anagrams by their sorted form.

```cpp // Group Anagrams — map sorted key → strings unordered_map> groups; for (string& s : strs) { string key = s; sort(key.begin(), key.end()); groups[key].push_back(s); } vector> result; for (auto& [key, group] : groups) result.push_back(group); return result; ```

Section 6 — Pattern: Sliding Window + HashMap

Maintain a frequency map of elements in the current window. Expand right, shrink left when constraint violated.

```cpp // Longest substring with at most k distinct characters unordered_map freq; int left = 0, ans = 0; for (int right = 0; right < s.size(); right++) { freq[s[right]]++; while (freq.size() > k) { // shrink if (--freq[s[left]] == 0) freq.erase(s[left]); left++; } ans = max(ans, right - left + 1); } ```

Section 7 — Pattern: Prefix Sum + HashMap

Store cumulative prefix sums and their frequencies. For each prefix sum curr, the count of subarrays summing to target ending at this index = freq[curr - target].

```cpp // Count subarrays with sum == k unordered_map freq; freq[0] = 1; int curr = 0, ans = 0; for (int x : nums) { curr += x; ans += freq[curr - k]; // subarrays ending here summing to k freq[curr]++; } // Count subarrays with equal number of 0s and 1s // Transform: 0 → -1. Then counts subarrays summing to 0. unordered_map freq; freq[0] = 1; int curr = 0, ans = 0; for (int x : nums) { curr += (x == 1 ? 1 : -1); ans += freq[curr]; freq[curr]++; } ```

Practice Problems

#	Problem	Pattern	Diff
1	1832. Check if the Sentence Is Pangram	Existence check (set)	Easy
2	268. Missing Number	Existence check (set)	Easy
3	1426. Counting Elements	Two-sum lookup (x+1)	Easy
4	1. Two Sum	Two-sum lookup	Easy
5	383. Ransom Note	Frequency count	Easy
6	771. Jewels and Stones	Existence check (set)	Easy
7	2225. Find Players With Zero or One Losses	Frequency count (map)	Medium
8	1133. Largest Unique Number	Frequency count (unique = 1)	Easy
9	1189. Maximum Number of Balloons	Frequency ratio	Easy
10	49. Group Anagrams	Grouping (sorted key)	Medium
11	347. Top K Frequent Elements	Frequency count + heap	Medium
12	560. Subarray Sum Equals K	Prefix sum + HashMap	Medium
13	146. LRU Cache	HashMap + Doubly Linked List	Medium