Notes › DSA
Hashing (HashMap and HashSet)
A hash table stores keys so that insert, delete and lookup take O(1) on average. It is the single most useful idea for speeding up brute-force solutions.
How it works
- A hash function turns a key into a number:
h("cat") → 98765. - That number picks a bucket:
index = h(key) % capacity. - The key (and its value) is stored in that bucket.
Two different keys can land in the same bucket — a collision. Two common fixes:
- Chaining: each bucket holds a small list of entries (C++
unordered_map, JavaHashMap). - Open addressing: on a collision, probe the next free slot (linear / quadratic probing, double hashing).
When the table gets too full (the load factor passes a limit, ~0.75 in Java), it rehashes into a bigger array — an O(n) step that happens rarely, so inserts stay O(1) amortised.
| Operation | Average | Worst case |
|---|---|---|
| Insert / delete / find | O(1) | O(n) (every key in one bucket) |
C++ containers
| Container | Ordered? | Lookup | Notes |
|---|---|---|---|
unordered_map<K,V> |
no | O(1) avg | hash table |
unordered_set<K> |
no | O(1) avg | keys only |
map<K,V> |
yes (sorted keys) | O(log n) | red-black tree |
set<K> |
yes | O(log n) | sorted, unique keys |
unordered_map<string, int> freq;
for (string w : words) freq[w]++; // missing keys start at 0
if (freq.count("apple")) cout << freq["apple"];
for (auto& [word, c] : freq) cout << word << " " << c << "\n";
unordered_set<int> seen;
seen.insert(5);
bool has = seen.count(5); // 1 or 0
freq[x]creates the key if it is missing. To only check, usecountorfind.
Java: HashMap, HashSet, TreeMap. Python: dict, set, collections.Counter.
Pattern 1: "have I seen this before?" — Two Sum
vector<int> twoSum(vector<int>& a, int target) {
unordered_map<int, int> idx; // value → index
for (int i = 0; i < a.size(); i++) {
int need = target - a[i];
if (idx.count(need)) return {idx[need], i};
idx[a[i]] = i;
}
return {};
}
Brute force is O(n²); the map makes it O(n).
Pattern 2: counting frequencies
Anagrams, first non-repeating character, majority element, top-K frequent elements.
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
int cnt[26] = {0}; // fixed alphabet: an array beats a map
for (char c : s) cnt[c - 'a']++;
for (char c : t) if (--cnt[c - 'a'] < 0) return false;
return true;
}
Pattern 3: prefix sum + hash map
Count subarrays with sum = k: if prefix[j] - prefix[i] = k, then the subarray (i, j] sums to k. Store how many times each prefix sum has appeared.
int subarraySum(vector<int>& a, int k) {
unordered_map<int, int> seen{{0, 1}};
int sum = 0, count = 0;
for (int x : a) {
sum += x;
count += seen[sum - k];
seen[sum]++;
}
return count;
}
Works with negative numbers, unlike the sliding window.
Pattern 4: grouping by a key
Group anagrams: key = the sorted word (or the 26-letter count) → map<key, vector<string>>.
Pattern 5: longest consecutive sequence
Put all numbers in a set; start counting only from numbers whose x - 1 is not in the set → O(n).
Classic problems
| Problem | Idea |
|---|---|
| Two sum | value → index map |
| Valid anagram / group anagrams | frequency / sorted key |
| Contains duplicate | set |
| Subarray sum equals K | prefix sum + map |
| Longest consecutive sequence | set |
| Top K frequent elements | count + heap or bucket sort |
| Longest substring without repeating characters | map + sliding window |
Practise them in the Hashing & Two Pointers section.
Interview one-liners
- HashMap vs TreeMap: O(1) unordered vs O(log n) sorted.
- Why can the worst case be O(n)? All keys collide into one bucket. Java 8+ turns long chains into balanced trees, so its worst case is O(log n).
- Custom keys need a good
hashCode()/equals()(Java) or a hash function (C++). - In contests,
unordered_mapcan be attacked with anti-hash tests — use a custom hash ormapif TLE.