Hi everyone ✋

Welcome back to the Array & Hashing stop on our DSA Deep Dive roadmap 🗺️. Last time we laid down arrays ─ fast to index, but painfully slow (O(n)) to search when the data isn’t sorted. Today we meet the idea that fixes exactly that weakness, and unlocks a huge family of problems ─ hashing 🔑.

Hashing is the trick behind that near-magical O(1) lookup ─ “is this value here?” answered in essentially constant time, no matter how much data we have. Get comfortable with it and a startling number of medium-difficulty problems collapse into a few clean lines.

Today’s post covers hashing as a problem-solving tool ─ how a hash table actually works under the hood, its real complexity, the C++ containers that give it to us, the core patterns it unlocks, and the traps to sidestep along the way.

Let’s take a deep dive 🦴

The problem hashing solves 🐌

Picture a plain, unsorted array and the question “does the value 42 appear in here?” With nothing but an array, we have no choice but to walk it element by element ─ that’s an O(n) search, every single time. Ask that question a thousand times and we’ve paid O(n) a thousand times.

Hashing answers the same question in O(1) average time ─ effectively instant. Instead of scanning for a value, we compute where it would live and look straight there. That single shift, from searching to computing a location, is the whole idea. Let’s picture it.

My little reference ─ the coat-check cloakroom 🧥

Here’s the mental model to keep ─ hashing is a coat-check cloakroom 🧥.

We hand the attendant our coat (the value) along with our name (the key). Rather than hanging it on the next free hook and forgetting where, the attendant runs a quick rule on our name ─ say, a calculation based on its letters ─ to pick an exact hook number. That rule is the hash function, and the hook is the bucket.

To get our coat back, the attendant runs the same rule on our name, lands on the same hook, and grabs it ─ instantly, without searching the whole rack. Store and retrieve, both in constant time. 🎯

Two wrinkles complete the picture. If two different names happen to compute to the same hook, those coats simply share it ─ that’s a collision, and the attendant does a tiny check among the few coats hanging there. And if the cloakroom gets too crowded, the staff add more hooks and re-hang everything to keep each hook short ─ that’s rehashing. Keep the cloakroom in mind; every hashing fact below is just a detail of how the attendant works.

How a hash table works 🔧

Let’s make the cloakroom precise. A hash table is, at heart, an array of buckets. Storing a key follows three steps ─

1. Hash the key ─ a hash function turns the key (a number, a string, anything) into a big integer.
2. Map it to a bucket ─ take that integer modulo the number of buckets to get an index into the bucket array.
3. Store it there ─ drop the key (and its value) into that bucket.

Looking a key up runs the exact same computation, lands in the same bucket, and finds it there. Because steps 1–3 don’t depend on how many items are stored, the whole thing is O(1) on average ⚡.

The two details from the analogy have real names ─

• Collisions. Different keys can map to the same bucket. The common fix is chaining ─ each bucket holds a little list, and a lookup scans just that short list. As long as buckets stay short, this stays fast.
• Load factor & rehashing. The load factor is roughly items ÷ buckets. When it climbs too high (buckets getting long), the table rehashes ─ it grows the bucket array and redistributes everything, keeping buckets short again. Rehashing is occasional and its cost averages out.

The complexity ─ average O(1), worst-case O(n) ⏱️

This is the part worth being precise about, because it’s where hashing’s reputation is both earned and misunderstood.

Operation	Average	Worst case
Insert	O(1)	O(n)
Find / lookup	O(1)	O(n)
Erase	O(1)	O(n)

The average is O(1) ─ with a decent hash function, keys spread evenly across buckets, so every bucket stays tiny and operations are effectively constant time. The worst case is O(n), which happens only if every key collides into one bucket (a pathological or adversarial input) ─ then a lookup degrades to scanning one giant list, just like an unsorted array. In everyday problem solving with the standard library, we treat hashing as O(1) and it delivers ─ but it’s honest to know the guarantee is average, not guaranteed. We also pay O(n) space to hold all those buckets ─ hashing trades memory for speed, and that trade is almost always worth it.

Meet the tools ─ unordered_set & unordered_map 🧰

C++ hands us hashing through two containers. An unordered_set stores unique keys ─ perfect for “have I seen this?” An unordered_map stores key → value pairs ─ perfect for “what’s associated with this key?”

#include <iostream>
#include <string>
#include <unordered_set>
#include <unordered_map>
using namespace std;

int main()
{
    unordered_set<int> seen;
    seen.insert(5);
    seen.insert(8);
    cout << "has 5? " << seen.count(5) << ", has 9? " << seen.count(9) << endl;

    unordered_map<string, int> age;   // name -> age
    age["Ada"] = 36;
    age["Bob"] = 41;
    cout << "Ada is " << age["Ada"] << endl;

    return 0;
}

The output will be ─

has 5? 1, has 9? 0
Ada is 36

count gives 1 if a key is present and 0 if not (a clean membership test), while operator[] reads or writes a mapped value. Both insert, count, and [] run in O(1) average time. For the full container tour, our STL posts on unordered_map and unordered_set go deeper.

Unordered vs ordered ─ hash table vs balanced tree ⚖️

Just like arrays gave us a raw vs vector decision, hashing gives us an unordered vs ordered one ─ and again, it’s a complexity call. C++ has a second family, map and set, backed not by a hash table but by a balanced binary search tree. Here’s the trade ─

Property	unordered_map / unordered_set	map / set
Insert / find / erase	O(1) average	O(log n)
Worst case	O(n)	O(log n) guaranteed
Backed by	hash table	balanced BST
Keeps keys sorted?	✗ (no order)	✓ (sorted)
Ordered / range iteration	✗	✓

The verdict writes itself from the complexity ─ when we just need fast lookup, counting, or membership, reach for the unordered_ versions for their O(1) average speed 🥇. Reach for map / set only when we actually need what the tree gives ─ sorted order, ordered iteration, range queries, or a guaranteed O(log n) worst case. If order doesn’t matter, paying O(log n) for it is just wasted time. (Our STL series covers both families ─ map and set alongside their unordered cousins.)

The core hashing patterns 🎯

Here’s where hashing earns its keep. Almost every hashing problem is one of a few patterns ─ learn these and you’ll spot them instantly.

1 ─ Frequency counting. Count how many times each thing appears. Because a missing key reads as 0, freq[x]++ just works ─

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main()
{
    string s = "banana";
    unordered_map<char, int> freq;

    for (char c : s)
        freq[c]++;            // missing key defaults to 0, then increments

    cout << "a:" << freq['a'] << " n:" << freq['n'] << " b:" << freq['b'] << endl;
    return 0;
}

Output ─ a:3 n:2 b:1. This one pattern powers anagram checks, “most frequent element,” and countless counting problems.

2 ─ Grouping by a computed key. Bucket items together by some signature. Anagrams, for instance, share the same letters ─ so their sorted form makes a perfect key ─

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

int main()
{
    vector<string> words = { "eat", "tea", "tan", "ate", "nat" };
    map<string, vector<string>> groups;   // (map here just for tidy output)

    for (const string& w : words) {
        string key = w;
        sort(key.begin(), key.end());     // canonical key = sorted letters
        groups[key].push_back(w);         // drop each word under its key
    }

    for (auto& [key, group] : groups) {
        cout << key << ": ";
        for (const string& w : group) cout << w << " ";
        cout << endl;
    }
    return 0;
}

The output will be ─

aet: eat tea ate 
ant: tan nat 

Words that share a key are anagrams, neatly grouped. (We used map here purely for sorted, predictable output ─ in real code unordered_map is the faster default.)

3 ─ The complement / “seen” pattern. As we scan, we remember what we’ve seen in a hash container, so that for each new element we can instantly ask whether its needed partner already showed up. This is the single most powerful hashing pattern ─ and it’s exactly what our warm-up problem below is built on 👇.

When to hash vs when to sort 🤔

Two tools often solve the same problem ─ hashing and sorting ─ so it’s worth knowing which to grab. It’s a complexity trade ─

• Hashing ─ O(n) time, O(n) extra space, and leaves data unordered. Ideal for counting, membership, and complement lookups, when we don’t care about order.
• Sorting ─ O(n log n) time but often O(1) extra space, and leaves data ordered. Ideal when the problem needs order anyway, when memory is tight, or when sorting unlocks a two-pointer or binary-search sweep.

The quick rule ─ need speed, counting, or membership? hash. Need order, or want to save memory? sort. Many problems accept either; recognising the trade is what lets us pick the cleaner one.

The challenges of hashing ─ and how to beat them ⚠️

Hashing is powerful, but it has its own set of traps. Let’s meet each with an example ─ and its fix.

1 ─ operator[] silently inserts. On an unordered_map, using [] with a missing key doesn’t just read ─ it creates that key (with a default value) ─

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main()
{
    unordered_map<string, int> m;
    m["Ada"] = 36;

    if (m["Bob"] == 0) { }   // ☠️ this just created "Bob" -> 0!
    cout << "size after m[\"Bob\"]: " << m.size() << endl;

    cout << "contains Cid? "      << m.count("Cid") << endl;   // ✅ no insert
    cout << "size after count: "  << m.size()       << endl;
    return 0;
}

Output ─ size after m["Bob"]: 2, then contains Cid? 0, size after count: 2. Fix ─ when you only want to check whether a key exists, use m.count(key), m.find(key), or m.contains(key) (C++20) ─ and reserve [] for when we actually intend to read-or-create.

2 ─ No built-in hash for pair or custom types. unordered_set<pair<int,int>> won’t compile ─ the standard library doesn’t hash a pair out of the box. The simplest fix is to encode the parts into one hashable value ─

#include <iostream>
#include <unordered_set>
using namespace std;

int main()
{
    unordered_set<long long> visited;      // instead of a pair key
    int COLS = 1000;

    long long key = (long long)3 * COLS + 7;   // encode (row=3, col=7) -> one number
    visited.insert(key);

    cout << "visited (3,7)? " << visited.count((long long)3 * COLS + 7) << endl;
    return 0;
}

Output ─ visited (3,7)? 1. Fix ─ encode multi-part keys into a single long long (as here), or supply a custom hash functor, or fall back to map/set (which only need <, not a hash).

3 ─ Iteration order is unspecified. Looping over an unordered_map visits keys in no guaranteed order ─ and that order can even change between runs or compilers. Fix ─ never rely on it; if we need sorted output, use map/set, or collect the keys into a vector and sort them.

4 ─ The worst case really is O(n). With adversarial keys that all collide, lookups degrade to a linear scan. It’s rare in practice, but for competitive or security-sensitive code it’s worth knowing. Fix ─ it’s usually a non-issue with the standard hash; when it matters, a custom hash or an ordered container’s guaranteed O(log n) is the safe choice.

5 ─ Rehashing invalidates references and iterators. Just like a vector reallocating, an insert that triggers a rehash can move elements, dangling any reference, pointer, or iterator into the container. Fix ─ don’t hold a reference across an insert, and reserve up front when the size is known.

Notice the theme ─ every fix comes back to understanding what the container is really doing.

Tips & tricks of hashing 🧰

A few moves turn up again and again ─

• Lean on the default-0. For counting, freq[x]++ needs no initialisation ─ a missing key is 0. Clean and idiomatic.
• Encode composite keys. Turn (row, col) into row * COLS + col, or join strings with a separator, to sidestep custom hashes (as above).
• reserve to skip rehashing. If we know roughly how many keys are coming, m.reserve(n) pre-sizes the table and avoids the reshuffles.
• Check without inserting. Prefer count / find / contains over [] when we only want to test membership.
• Store value → index. When a problem asks “which two elements…”, map each value to where it lives, so we can return positions ─ the heart of the warm-up next.
• unordered_set for instant dedup. Dropping a range into a set removes duplicates in O(n).

A worked warm-up ─ Two Sum (LeetCode 1) 🏋️

Let’s cash in the complement pattern on the most famous hashing problem of them all.

The problem (Two Sum, #1, paraphrased): given an array nums and a target, return the indices of the two numbers that add up to target (exactly one such pair exists).

The intuition: the brute force checks every pair ─ O(n²). The repeated work is searching for a partner. So as we scan, we remember each number and its index in a hash map; then for each new number x, the partner we need is target - x, and we can check if we’ve already seen it in O(1).

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target)
{
    unordered_map<int, int> seen;              // value -> index

    for (int i = 0; i < (int)nums.size(); i++) {
        int need = target - nums[i];
        if (seen.count(need))                  // has the partner appeared already?
            return { seen[need], i };
        seen[nums[i]] = i;                     // otherwise remember this number
    }
    return {};                                 // (problem guarantees a solution)
}

int main()
{
    vector<int> nums = { 2, 7, 11, 15 };
    vector<int> ans = twoSum(nums, 9);

    cout << ans[0] << " " << ans[1] << endl;
    return 0;
}

The output will be ─

0 1

The walkthrough: at i = 0, nums[0] = 2, we need 7; not seen yet, so remember 2 → 0. At i = 1, nums[1] = 7, we need 2 ─ and 2 is in the map, at index 0, so we return {0, 1}. Time: O(n), a single pass. Space: O(n) for the map. We turned an O(n²) brute force into a clean O(n) solution ─ and the entire leap was one hash-map lookup replacing a search 🥳.

So what should we remember? 🤔

Let’s wrap up the foundations of hashing ─

• Hashing answers “is this value here?” in O(1) average time by computing a location instead of searching ─ the cure for the array’s slow O(n) search.
• Picture the coat-check cloakroom 🧥 ─ a rule (the hash function) sends each key to a hook (bucket); same rule retrieves it instantly. Two keys sharing a hook is a collision; a crowded rack triggers a rehash.
• The complexity is O(1) average, O(n) worst case (all-collide), plus O(n) space ─ we trade memory for speed.
• Use unordered_set for membership and unordered_map for key→value ─ both O(1) average.
• Unordered vs ordered ─ default to unordered_ for raw speed; use map/set only when we need sorted order, range queries, or a guaranteed O(log n).
• The core patterns ─ frequency counting (freq[x]++), grouping by a computed key, and the complement / “seen” pattern (the heart of Two Sum).
• Hash vs sort ─ hash for speed/counting/membership; sort for order or to save memory.
• Dodge the traps ─ [] silently inserts (use count/find/contains), no default hash for pairs (encode the key), unspecified iteration order, and rehash invalidation (reserve).

Arrays gave us instant access by position; hashing gives us instant access by value. Together they’re the bedrock of problem solving ─ which is exactly why they share the very first stop on our roadmap 👀✨.

Congratulations 🥳🥳🥳
We’ve now got both halves of the foundation ─ arrays and hashing ─ and even solved Two Sum with them.

That wraps up the concepts of Array & Hashing. In the next post we stop learning and start solving ─ we roll up our sleeves for our first proper LeetCode problem, putting today’s hashing patterns straight to work 😉

Happy Coding 💻 🎵