Module 05: Hash Tables — Hashing Internals, Collisions & Patterns

Goal: Master hashing mathematics, collision resolution mechanisms (Chaining vs Open Addressing vs Robin Hood), dynamic rehashing, std::unordered_map internals, and hash-based algorithmic patterns.
Language: C++ (C++17/C++20)
Prerequisites: Modules 01 to 04.

📑 Table of Contents

Under the Hood: How Hashing Works
Collision Resolution Strategies
Load Factor & Dynamic Rehashing
C++ std::unordered_map vs std::map
Custom Hash Functions in C++
Core Algorithmic Hashing Patterns
5 Practice Problems with Detailed Solutions
Top 10 FAANG Interview Questions

1. Under the Hood: How Hashing Works

A Hash Table implements an associative array mapping keys to values using a Hash Function that computes an integer index into an array of buckets.

Key ("apple") ──► [ Hash Function: hash(key) ] ──► 0x9F3B21 ──► [ Index = hash % M ] ──► Bucket [ 3 ]

Bucket Array (Size M = 8):
Index:     0          1          2          3                  4          5          6          7
Buckets: [ null ]  [ null ]  [ null ]  [ ("apple", 5) ]     [ null ]  [ null ]  [ null ]  [ null ]

1.1 Properties of a Good Hash Function

Deterministic: Same key must always produce the exact same hash code.
Uniform Distribution: Uniformly scatters keys across all buckets to minimize collisions.
Fast Computation: $O(1)$ computation time with respect to key length.
Avalanche Effect: A 1-bit change in input key flips ~50% of the bits in the output hash code.

2. Collision Resolution Strategies

When two distinct keys $k_1 \ne k_2$ produce the same index: $\text{hash}(k_1) \pmod M = \text{hash}(k_2) \pmod M$.

                    ┌──────────────────────────────────────────────┐
                    │        Collision Resolution Strategies       │
                    └──────────────────────┬───────────────────────┘
                                           │
                      ┌────────────────────┴────────────────────┐
                      ▼                                         ▼
        ┌───────────────────────────┐             ┌───────────────────────────┐
        │     Separate Chaining     │             │      Open Addressing      │
        │ (Linked List / Tree / Vec)│             │ (Probing within same array│
        └───────────────────────────┘             └─────────────┬─────────────┘
                                                                │
                                     ┌──────────────────────────┼──────────────────────────┐
                                     ▼                          ▼                          ▼
                         ┌───────────────────────┐  ┌───────────────────────┐  ┌───────────────────────┐
                         │    Linear Probing     │  │   Quadratic Probing   │  │    Double Hashing     │
                         │ h(k, i) = (h + i) % M │  │h(k,i)=(h+c₁i+c₂i²)% M │  │h(k,i)=(h₁+i·h₂)% M    │
                         └───────────────────────┘  └───────────────────────┘  └───────────────────────┘

2.1 Separate Chaining

Each bucket stores a pointer to a linked list (or dynamic array) of key-value pairs.

Insert: $O(1)$ at head.
Search / Delete: $O(1)$ average, $O(N)$ worst-case if all keys hash to the same bucket.
Advantage: Simple, degradation is gradual when load factor exceeds 1.0.

Bucket [3] ──► [ "apple": 5 ] ──► [ "cherry": 9 ] ──► nullptr

2.2 Open Addressing: Linear Probing

All entries reside directly in the table array. If bucket $h(k)$ is occupied, probe consecutive slots: $$h(k, i) = (h(k) + i) \pmod M \quad \text{for } i = 0, 1, 2, \dots$$

Primary Clustering: Long contiguous clusters of occupied slots form, degrading search time to $O(N)$.
Deletion: Requires a special sentinel value (TOMBSTONE / DELETED) so lookups don't terminate prematurely.

2.3 Robin Hood Hashing

An advanced open addressing variant where elements keep track of their distance from their ideal bucket ("probe sequence length"). During insertion, if the newcomer has traveled further than the current occupant, the newcomer takes the slot and the old occupant is bumped forward. This minimizes variance in probe lengths.

3. Load Factor & Dynamic Rehashing

The Load Factor $\alpha$ measures table fullness: $$\alpha = \frac{N}{M} = \frac{\text{Number of elements stored}}{\text{Total number of buckets}}$$

When $\alpha \ge \alpha_{\text{max}}$ (typically $0.7$ to $0.75$):
1. Allocate new bucket array of size $2M$ (or next prime number).
2. Iterate over all existing elements and re-insert them into the new table (since $\text{index} = \text{hash}(k) \pmod{2M}$ changes).
3. Deallocate old array.
Rehashing Cost: $O(N)$ work, but happens infrequently, yielding amortized $O(1)$ insertions.

4. C++ `std::unordered_map` vs `std::map`

Feature	`std::unordered_map`	`std::map`
Underlying Structure	Hash Table (Separate Chaining)	Red-Black Tree (Self-Balancing BST)
Search Time	$O(1)$ Average, $O(N)$ Worst	Guaranteed $O(\log N)$ Worst
Insertion / Deletion	Amortized $O(1)$, $O(N)$ Worst	Guaranteed $O(\log N)$
Ordering	No ordering of keys	Keys stored in strict sorted order (`<`)
Bidirectional Iteration	Forward only	Bidirectional (`rbegin()`, `prev()`)
Range Queries (`lower_bound`)	Not Supported	Supported in $O(\log N)$
Memory Overhead	Bucket vector + node pointers	3 pointers + color bit per node

5. Custom Hash Functions in C++

To use custom structs or std::pair in std::unordered_map, supply a hash functor and equality operator.

#include <iostream>
#include <unordered_map>
#include <string>

struct Point {
    int x, y;
    
    // Equality operator required for hash collisions
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// Custom Hash Functor using boost-style hash_combine
struct PointHash {
    std::size_t operator()(const Point& p) const {
        std::size_t h1 = std::hash<int>{}(p.x);
        std::size_t h2 = std::hash<int>{}(p.y);
        // Bit-mixing formula to prevent hash collisions
        return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
    }
};

int main() {
    std::unordered_map<Point, std::string, PointHash> pointMap;
    pointMap[{10, 20}] = "Start";
    pointMap[{30, 40}] = "End";
    
    std::cout << pointMap[{10, 20}] << "\n"; // Output: Start
}

6. Core Algorithmic Hashing Patterns

6.1 Frequency Counter

std::unordered_map<char, int> freq;
for (char c : str) freq[c]++;

6.2 Complement Lookup (Two Sum Pattern)

std::unordered_map<int, int> numToIndex;
for (int i = 0; i < nums.size(); ++i) {
    int complement = target - nums[i];
    if (numToIndex.count(complement)) return {numToIndex[complement], i};
    numToIndex[nums[i]] = i;
}

6.3 State Normalization / Canonical Key Representation (Group Anagrams)

Sort string or count character frequencies to create a canonical hash key for grouping.

7. 5 Practice Problems with Detailed Solutions

Problem 1: Group Anagrams (LeetCode #49 - Medium)

Problem: Given an array of strings strs, group the anagrams together.

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) {
    std::unordered_map<std::string, std::vector<std::string>> anagramGroups;
    
    for (const std::string& s : strs) {
        std::string key = s;
        std::sort(key.begin(), key.end()); // Canonical representation
        anagramGroups[key].push_back(s);
    }
    
    std::vector<std::vector<std::string>> result;
    result.reserve(anagramGroups.size());
    for (auto& pair : anagramGroups) {
        result.push_back(std::move(pair.second));
    }
    return result;
}
// Time Complexity: O(N * K log K) where N = number of strings, K = max string length
// Space Complexity: O(N * K)

Problem 2: Longest Consecutive Sequence (LeetCode #128 - Medium)

Problem: Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence in $O(N)$ time.

#include <vector>
#include <unordered_set>
#include <algorithm>

int longestConsecutive(const std::vector<int>& nums) {
    std::unordered_set<int> numSet(nums.begin(), nums.end());
    int longestStreak = 0;
    
    for (int num : numSet) {
        // Only start counting if 'num' is the beginning of a sequence (num - 1 not in set)
        if (!numSet.count(num - 1)) {
            int currentNum = num;
            int currentStreak = 1;
            
            while (numSet.count(currentNum + 1)) {
                currentNum++;
                currentStreak++;
            }
            
            longestStreak = std::max(longestStreak, currentStreak);
        }
    }
    
    return longestStreak;
}
// Time Complexity: O(N) - each number is visited at most twice
// Space Complexity: O(N) for hash set

Problem 3: Insert Delete GetRandom O(1) (LeetCode #380 - Medium)

Problem: Implement RandomizedSet with $O(1)$ average time for insert, remove, and getRandom.

#include <vector>
#include <unordered_map>
#include <cstdlib>

class RandomizedSet {
private:
    std::vector<int> nums;
    std::unordered_map<int, int> valToIndex; // val -> index in nums

public:
    RandomizedSet() {}

    bool insert(int val) {
        if (valToIndex.count(val)) return false;
        nums.push_back(val);
        valToIndex[val] = nums.size() - 1;
        return true;
    }

    bool remove(int val) {
        if (!valToIndex.count(val)) return false;
        
        // Swap element with last element in vector to achieve O(1) erase
        int lastVal = nums.back();
        int idx = valToIndex[val];
        
        nums[idx] = lastVal;
        valToIndex[lastVal] = idx;
        
        nums.pop_back();
        valToIndex.erase(val);
        return true;
    }

    int getRandom() {
        int randomIndex = std::rand() % nums.size();
        return nums[randomIndex];
    }
};
// insert: O(1) avg
// remove: O(1) avg
// getRandom: O(1)

Problem 4: 4Sum II (LeetCode #454 - Medium)

Problem: Given 4 integer arrays of size $N$, compute how many tuples $(i, j, k, l)$ have $A[i] + B[j] + C[k] + D[l] = 0$.

#include <vector>
#include <unordered_map>

int fourSumCount(const std::vector<int>& nums1, const std::vector<int>& nums2,
                 const std::vector<int>& nums3, const std::vector<int>& nums4) {
    std::unordered_map<int, int> sumAB;
    
    // Store all pairwise sums of nums1 and nums2
    for (int a : nums1) {
        for (int b : nums2) {
            sumAB[a + b]++;
        }
    }
    
    int count = 0;
    // Check if -(c + d) exists in map
    for (int c : nums3) {
        for (int d : nums4) {
            int target = -(c + d);
            if (sumAB.count(target)) {
                count += sumAB[target];
            }
        }
    }
    
    return count;
}
// Time Complexity: O(N^2) instead of O(N^4)
// Space Complexity: O(N^2)

Problem 5: Isomorphic Strings (LeetCode #205 - Easy)

#include <string>
#include <vector>

bool isIsomorphic(const std::string& s, const std::string& t) {
    if (s.length() != t.length()) return false;
    
    std::vector<int> m1(256, 0);
    std::vector<int> m2(256, 0);
    
    for (size_t i = 0; i < s.length(); ++i) {
        if (m1[s[i]] != m2[t[i]]) return false;
        m1[s[i]] = i + 1; // Record 1-indexed last seen position
        m2[t[i]] = i + 1;
    }
    return true;
}
// Time Complexity: O(N)
// Space Complexity: O(1)

8. Top 10 FAANG Interview Questions

Q1: What is a Hash Table Denial of Service (DoS) attack, and how is it prevented?

Answer: If an attacker knows the hash function (e.g., standard std::hash<int> which is often the identity function $h(x) = x$), they can craft $N$ inputs that all hash to the same bucket ($x_i \equiv 0 \pmod M$). This causes $N$ collisions, degrading all $O(1)$ operations into $O(N)$, resulting in $O(N^2)$ server execution time. Prevention: Use randomized seeded hash functions (like MurmurHash3 or SipHash) with a per-process random seed.

Q2: Why must the equality operator `==` be provided along with a custom hash function?

Answer: Hashing only determines which bucket to search. Because of hash collisions (pigeonhole principle) and modulo operations, multiple distinct keys can end up in the same bucket. The container uses operator== to identify the exact matching key within that bucket.

Q3: What is the difference between Primary Clustering and Secondary Clustering?

Answer:

Primary Clustering (Linear Probing): Long continuous blocks of occupied cells form. Any key whose hash lands anywhere inside or near the block prolongs the cluster.
Secondary Clustering (Quadratic Probing): Keys that produce the same initial hash follow the exact same probe sequence, although distinct initial hashes do not merge probe paths.

Q4: Why is deleting an element in Open Addressing more complex than in Separate Chaining?

Answer: In open addressing, search stops upon finding an empty slot. If an intermediate slot is deleted and set to empty, subsequent lookups for keys placed after that slot during earlier collision probing will prematurely terminate and report "not found". Deletion must write a TOMBSTONE marker (slot is available for insert, but probing continues during lookup).

Q5: When would you choose `std::map` over `std::unordered_map`?

Answer:

When elements need to be printed or iterated in sorted order.
When predecessor/successor or range operations (lower_bound, upper_bound) are needed.
When guaranteed worst-case $O(\log N)$ is required for real-time systems without latency spikes from rehashing.

Q6: What is Cuckoo Hashing?

Answer: Uses 2 hash functions $h_1(k)$ and $h_2(k)$ and 2 tables. A key is always at either $T_1[h_1(k)]$ or $T_2[h_2(k)]$. Lookups take guaranteed worst-case $O(1)$ time (at most 2 checks). If both slots are occupied during insertion, the newcomer evicts the existing element, which then moves to its alternative location (like a cuckoo bird kicking eggs out of a nest).

Q7: How does Java 8+ optimize Separate Chaining HashMap under high collisions?

Answer: When a single bucket chain exceeds 8 nodes and the table capacity is $\ge 64$, the linked list in that bucket is converted into a Red-Black Tree (Treeification). This bounds worst-case lookup from $O(N)$ down to $O(\log N)$.

Q8: What is the optimal initial bucket size for `std::unordered_map`?

Answer: If you know ahead of time that you will insert $N$ items, call map.reserve(N). This pre-allocates $\lceil N / \alpha_{\text{max}} \rceil$ buckets, completely eliminating all rehashing and memory reallocation overhead during insertions.

Q9: Can floating-point numbers (`float`/`double`) be used as hash keys?

Answer: Technically yes, but practically dangerous because of precision rounding issues and special values. For example, +0.0 == -0.0 is true, but their bit representations differ. NaN == NaN is false by IEEE-754 standard, violating equivalence relation axioms.

Q10: How do you design an $O(1)$ time and $O(1)$ space lookup for whether a string has all unique characters?

Answer: If string consists only of lowercase letters 'a'-'z' (26 characters), use a 32-bit integer as a bitmask:

int bitmask = 0;
for (char c : s) {
    int bit = c - 'a';
    if (bitmask & (1 << bit)) return false; // Duplicate
    bitmask |= (1 << bit);
}
return true;

Time: $O(N)$, Space: $O(1)$ (1 integer).

05-hash-tables.md