Hash Maps & Sets

Why hashing is everywhere

A hash table stores key → value pairs and supports insert, delete and lookup in O(1) average time. Most brute-force solutions spend their time searching ("is there an element that…?"). Replacing that search with a hash lookup removes a whole factor of n.

How it works (enough to reason about it)

1. A hash function turns a key into an integer.
2. That integer mod the table size picks a bucket.
3. Collisions (two keys, same bucket) are handled by chaining (a list per bucket) or open addressing (probe the next slot).
4. When the table gets too full (load factor ≈ 0.75), it resizes (doubles and rehashes) — amortized O(1).

Worst case is O(n) per operation if everything collides, which is why adversarial inputs can break unordered_map in competitive programming (see the C++ note below).

The toolbox

from collections import Counter, defaultdict

seen = set()
seen.add(3); 3 in seen; seen.discard(3)

freq = Counter("mississippi")         # {'i': 4, 's': 4, 'p': 2, 'm': 1}
freq.most_common(2)                    # [('i', 4), ('s', 4)]

groups = defaultdict(list)             # missing keys start as []
groups["key"].append(1)

last_index = {}
last_index.get("x", -1)                # default when missing

# iterate
for key, val in freq.items(): ...

#include <unordered_map>
#include <unordered_set>

unordered_set<int> seen;
seen.insert(3); seen.count(3); seen.erase(3);

unordered_map<char, int> freq;
for (char c : s) freq[c]++;            // operator[] default-inits to 0

auto it = freq.find('x');
if (it != freq.end()) { /* it->second */ }

// ordered alternatives (O(log n), sorted iteration)
map<int, int> m;  set<int> st;

Pattern 1: Complement lookup

“Find two items that combine into a target.” For each item, compute what its partner would have to be and look it up.

def two_sum(nums, target):
    index_of = {}
    for i, x in enumerate(nums):
        if target - x in index_of:          # check BEFORE inserting x
            return [index_of[target - x], i]
        index_of[x] = i
    return []

vector<int> twoSum(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;
    }
    return {};
}

Checking before inserting avoids pairing an element with itself.

Pattern 2: Frequency counting

def is_anagram(s, t):
    if len(s) != len(t):
        return False
    count = [0] * 26
    for a, b in zip(s, t):
        count[ord(a) - 97] += 1
        count[ord(b) - 97] -= 1
    return all(c == 0 for c in count)

Frequency maps also power sliding windows (count characters inside the window) — see Sliding Window.

Pattern 3: Grouping by a canonical key

Items that are “equivalent” should map to the same key. Designing that key is the whole problem.

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = [0] * 26
        for ch in w:
            key[ord(ch) - 97] += 1
        groups[tuple(key)].append(w)       # O(L) key instead of O(L log L) sort
    return list(groups.values())

Other canonical keys you'll see:

Pattern 4: Prefix sum + hash map

Counting subarrays with a given sum (even with negatives): if prefix[j] - prefix[i] = k then subarray (i, j] sums to k. As you scan, count how many earlier prefixes equal prefix − k.

def subarray_sum(nums, k):
    count = {0: 1}          # empty prefix
    prefix = ans = 0
    for x in nums:
        prefix += x
        ans += count.get(prefix - k, 0)
        count[prefix] = count.get(prefix, 0) + 1
    return ans

Covered in depth in Prefix Sums.

Pattern 5: Set for O(1) membership → linear algorithms

def longest_consecutive(nums):
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 not in s:                # x starts a run
            y = x
            while y + 1 in s:
                y += 1
            best = max(best, y - x + 1)
    return best

The inner loop looks quadratic but each number is visited by the inner while at most once overall (only from the start of its run) → O(n).

Pattern 6: Index as hash (O(1) extra space)

When values are in the range [1, n], the array itself can serve as a hash table: mark presence by negating nums[v-1], or place each value at its "home" index with cyclic swaps.

def first_missing_positive(nums):
    n = len(nums)
    for i in range(n):
        # keep swapping nums[i] into its home slot nums[i]-1
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            j = nums[i] - 1
            nums[i], nums[j] = nums[j], nums[i]
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

Hash map vs sorted map

Common mistakes

• Pairing an element with itself in complement problems (insert after checking).
• Forgetting to seed count[0] = 1 in prefix-sum counting.
• Using a mutable list as a Python dict key (TypeError) — convert to tuple.
• C++: m[key] inserts a default value when the key is missing; use find/count to check existence without inserting.
• C++ competitive programming: anti-hash tests can make unordered_map O(n) per op. Use a custom hash (e.g. splitmix64) or map.

struct SplitMix {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t R = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + R);
    }
};
unordered_map<long long, int, SplitMix> safeMap;

Complexity summary