W Code - Pattern-Based DSA Learning Platform

Bhanu Bisht

Hashing (Hash Tables)

Master the art of O(1) lookups - Hash functions, collisions, and interview problems.

Hash Table Complexity at a Glance

Operation	Average	Worst Case	When Best?
Search	O(1)	O(n)	Low load factor
Insert	O(1)	O(n)	Good hash function
Delete	O(1)	O(n)	Few collisions
Space	O(n)

What is Hashing?

Average: O(1) for all operations

Instant Key-Value Lookups

Imagine checking your bags at a hotel. Instead of searching through every single bag in the storage room when you return, the clerk hands you a claim ticket with a number. The clerk goes directly to shelf compartment number 5 to retrieve your bag instantly.

Hashing is a technique that maps keys (like names or student IDs) to specific indices in a table using a mathematical Hash Function.

Key Features:

Constant Time Performance: Offers an average complexity of O(1) for insertions, deletions, and lookups.
Hash Table: A data structure that stores key-value pairs where keys are mapped to table indices.
Comparison: Unlike linear search (O(n)) or binary search (O(log n)), hashing accesses records directly without scanning through elements.

When to Use:

You need rapid key-based search lookups.
Counting the frequency of items (e.g., character counts).
Verifying if an element has been encountered previously.

C++ Code — What is Hashing?

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

int main() {
    // Creating a hash table (unordered_map in C++)
    unordered_map<string, int> studentMarks;
    
    // Insert: O(1) average
    studentMarks["Rahul"] = 85;
    studentMarks["Priya"] = 92;
    studentMarks["Amit"] = 78;
    
    // Lookup: O(1) average
    cout << "Priya's marks: " << studentMarks["Priya"] << endl;  // 92
    
    // Check if key exists
    if (studentMarks.count("Rahul")) {
        cout << "Rahul found!" << endl;
    }
    
    // Delete: O(1) average
    studentMarks.erase("Amit");
    
    return 0;
}

Hash Functions (Division Method)

Hash computation: O(1) for integers

Interactive

Interactive Hash Table (Division Method)

Hash Function: h(key) = key % 7

idx: 0—

idx: 1—

idx: 2—

idx: 3—

idx: 4—

idx: 5—

idx: 6—

Mapping Keys to Indices

Imagine filing documents in drawers labeled 0 through 9. To file a document with serial number 148, you look at the last digit and place it directly into drawer 8.

A Hash Function takes an input key and maps it to a valid integer index within the boundaries of the hash table.

The Division Method:

The most common approach is the division method: h(key) = key % m where m is the size of the table (ideally a prime number to reduce collisions).

Properties of a Good Hash Function:

Fast Computation: It must execute in O(1) time.
Deterministic: The same key must always yield the exact same index.
Uniform Distribution: It should distribute keys evenly across all table slots to prevent clustering.
Collision Minimization: It should minimize instances where two different keys map to the same index.

C++ Code — Hash Functions (Division Method)

#include <iostream>
using namespace std;

class SimpleHashTable {
private:
    int tableSize;
    
public:
    SimpleHashTable(int size) : tableSize(size) {}
    
    // Division method hash function
    int hash(int key) {
        return key % tableSize;
    }
    
    // For string keys - sum of ASCII values
    int hashString(string key) {
        int sum = 0;
        for (char c : key) {
            sum += c;  // Add ASCII value
        }
        return sum % tableSize;
    }
};

Collision Handling: Chaining

Average: O(1 + α) where α = load factor

Interactive

Interactive Chaining (Linked List)

idx0

NULL

idx1

NULL

idx2

NULL

idx3

NULL

idx4

NULL

Resolving Overlapping Buckets

Imagine checking your coat in a locker room. If multiple coats are assigned to the same locker number, you hook them one after another on a chain hangers inside that single locker.

Since the set of possible keys is larger than the hash table size, different keys will eventually hash to the same index. This event is called a Collision.

Separate Chaining:

Each slot in the hash table points to a Linked List (or dynamic array) of all elements that hash to that same index.

Operations:

Insertion: Hash the key and append the element to the linked list at that index.
Search: Hash the key and traverse the linked list at that index.
Deletion: Find the item in the list and remove it.

Pros and Cons:

Pros: Simple to implement, and the table never technically fills up.
Cons: Consumes extra memory for storing node pointers, and performance degrades to O(n) in the worst-case if all elements hash to the same slot.

C++ Code — Collision Handling: Chaining

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

class HashTableChaining {
private:
    int size;
    vector<list<int>> table;
    
    int hash(int key) { return key % size; }
    
public:
    HashTableChaining(int s) : size(s), table(s) {}
    
    void insert(int key) {
        int idx = hash(key);
        table[idx].push_back(key);
    }
};

Collision Handling: Open Addressing

Average: O(1 / (1 - α)) | Worst: O(n) when full

Probing for Empty Slots

Imagine trying to park your car in spot number 12. If you find it occupied, you drive down the row and park in the very next open spot you see (e.g., spot 13, 14, and so on).

In Open Addressing, all element records are stored directly inside the hash table array itself. If a collision occurs, we probe the array using a systematic sequence to find the next empty slot.

Common Probing Strategies:

Linear Probing: We look at sequential slots one by one: h(k, i) = (h'(k) + i) % m
Quadratic Probing: We search using quadratic steps to reduce clustering: h(k, i) = (h'(k) + c1 * i + c2 * i²) % m
Double Hashing: We compute probe steps using a second hash function: h(k, i) = (h1(k) + i * h2(k)) % m

Pros and Cons:

Pros: Better cache locality (data is stored in contiguous memory) and no memory overhead from pointers.
Cons: The table can fill up completely, and deletions are complex because we must leave "dummy/deleted" markers to avoid breaking probe chains.

C++ Code — Collision Handling: Open Addressing

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

class HashTableOpenAddressing {
private:
    int size;
    vector<int> table;
    vector<bool> occupied;
    
    int hash(int key) {
        return key % size;
    }
    
public:
    HashTableOpenAddressing(int s) : size(s), table(s, -1), occupied(s, false) {}
    
    // Insert with linear probing
    void insert(int key) {
        int index = hash(key);
        int originalIndex = index;
        
        // Linear probing
        while (occupied[index]) {
            cout << "Collision at " << index << ", probing..." << endl;
            index = (index + 1) % size;  // Move to next slot
            
            if (index == originalIndex) {
                cout << "Table is full!" << endl;
                return;
            }
        }
        
        table[index] = key;
        occupied[index] = true;
        cout << "Inserted " << key << " at index " << index << endl;
    }
    
    // Search with linear probing
    int search(int key) {
        int index = hash(key);
        int originalIndex = index;
        
        while (occupied[index]) {
            if (table[index] == key) {
                return index;  // Found!
            }
            index = (index + 1) % size;
            
            if (index == originalIndex) break;
        }
        return -1;  // Not found
    }
    
    void display() {
        cout << "Hash Table: ";
        for (int i = 0; i < size; i++) {
            if (occupied[i]) {
                cout << "[" << i << "]:" << table[i] << " ";
            } else {
                cout << "[" << i << "]:_ ";
            }
        }
        cout << endl;
    }
};

int main() {
    HashTableOpenAddressing ht(7);
    
    ht.insert(10);  // 10 % 7 = 3
    ht.insert(17);  // 17 % 7 = 3 → collision → goes to 4
    ht.insert(24);  // 24 % 7 = 3 → collision → goes to 5
    ht.insert(31);  // 31 % 7 = 3 → collision → goes to 6
    
    cout << "\n";
    ht.display();
    
    cout << "\nSearch 17: index " << ht.search(17) << endl;  // 4
    
    return 0;
}

Load Factor & Rehashing

Rehash: O(n) | Amortized insert: O(1)

Dynamic Table Resizing

Imagine living in a studio apartment. When the apartment gets 75% full of items and furniture, finding anything becomes slow and difficult. To fix this, you move to a larger apartment and rearrange your belongings there.

The Load Factor (α) measures how full a hash table is: α = (Number of Elements) / (Table Size)

As α approaches 1.0, collision rates increase and performance degrades.

Rehashing:

To maintain fast lookups, we monitor α and resize the table once it exceeds a threshold (typically 0.7 or 0.75):

Allocate a new table, typically doubling the size (2 * m).
Re-insert (rehash) all elements from the old table into the new table using the updated hash function.
Deallocate the old table.

Complexity Check:

While rehashing takes O(n) time, it happens infrequently enough that the cost is spread out, keeping the amortized insertion time at O(1).

C++ Code — Load Factor & Rehashing

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

class HashTableWithRehash {
private:
    int size;
    int count;
    double maxLoadFactor;
    vector<list<int>> table;
    
    int hash(int key) {
        return key % size;
    }
    
    // Rehash to a bigger table
    void rehash() {
        cout << "\n⚡ REHASHING: Load factor exceeded!" << endl;
        cout << "Old size: " << size << ", Elements: " << count << endl;
        
        int oldSize = size;
        vector<list<int>> oldTable = table;
        
        // Double the size (or use next prime)
        size = size * 2;
        table = vector<list<int>>(size);
        count = 0;
        
        // Re-insert all elements
        for (int i = 0; i < oldSize; i++) {
            for (int key : oldTable[i]) {
                insert(key);  // Re-hash into new table
            }
        }
        
        cout << "New size: " << size << endl << endl;
    }
    
public:
    HashTableWithRehash(int s = 7, double mlf = 0.7) 
        : size(s), count(0), maxLoadFactor(mlf), table(s) {}
    
    void insert(int key) {
        int index = hash(key);
        table[index].push_back(key);
        count++;
        
        // Check load factor
        double loadFactor = (double)count / size;
        cout << "Inserted " << key << " | Load Factor: " << loadFactor << endl;
        
        if (loadFactor > maxLoadFactor) {
            rehash();
        }
    }
    
    double getLoadFactor() {
        return (double)count / size;
    }
};

int main() {
    HashTableWithRehash ht(7, 0.7);  // Size 7, max load 0.7
    
    // Insert elements until rehash triggers
    ht.insert(10);
    ht.insert(20);
    ht.insert(30);
    ht.insert(40);
    ht.insert(50);  // This might trigger rehash!
    ht.insert(60);
    
    return 0;
}

HashMap vs HashSet (C++ STL)

All operations: Average O(1), Worst O(n)

STL Hash Containers

C++ provides two main hash-based containers in the standard library:

1. `std::unordered_map<Key, Value>` (HashMap)

Stores unique key-value pairs.
Allows key-based value lookups.
Use case: Counting word frequencies, mapping names to objects.

2. `std::unordered_set<Key>` (HashSet)

Stores unique keys only (no values).
Allows checking if a key exists in the set.
Use case: Filtering out duplicate items, keeping track of visited nodes.

Feature	unordered_map	unordered_set
Stores	Key-Value pairs	Only Keys
Duplicates	No duplicate keys	No duplicates
Access	map[key]	—
Insert	map[k] = v	set.insert(k)
Check	map.count(k)	set.count(k)
Use Case	Frequency, Lookup	Existence Check

C++ Code — HashMap vs HashSet (C++ STL)

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

int main() {
    // ========== UNORDERED_MAP ==========
    cout << "=== unordered_map (HashMap) ===" << endl;
    
    unordered_map<string, int> freq;
    
    // Insert / Update
    freq["apple"] = 5;
    freq["banana"] = 3;
    freq["apple"]++;  // Now apple = 6
    
    // Access
    cout << "apple count: " << freq["apple"] << endl;  // 6
    
    // Check existence (SAFE way)
    if (freq.count("mango") == 0) {
        cout << "mango not found" << endl;
    }
    
    // Iterate
    cout << "All items: ";
    for (auto& p : freq) {
        cout << p.first << ":" << p.second << " ";
    }
    cout << endl << endl;
    
    // ========== UNORDERED_SET ==========
    cout << "=== unordered_set (HashSet) ===" << endl;
    
    unordered_set<int> seen;
    
    // Insert
    seen.insert(10);
    seen.insert(20);
    seen.insert(10);  // Duplicate - ignored!
    
    cout << "Size: " << seen.size() << endl;  // 2 (not 3!)
    
    // Check existence
    if (seen.count(20)) {
        cout << "20 exists!" << endl;
    }
    
    // Remove duplicates from array using set
    vector<int> arr = {1, 2, 2, 3, 3, 3, 4};
    unordered_set<int> unique(arr.begin(), arr.end());
    cout << "Unique elements: ";
    for (int x : unique) cout << x << " ";
    cout << endl;
    
    return 0;
}

Problem: Two Sum

Time: O(n) | Space: O(n)

Finding Target Pairs

Given an array of integers and a target sum, find the indices of the two numbers that add up to the target.

Brute Force Approach:

Check every pair in the array. This takes O(n²) time.

Hashing Approach (`O(n)` Time):

As you iterate through the array, check if the complement (target - current_value) is already in your hash map.

If found, return the index of the complement and the current index.
If not found, insert the current value and its index into the map.

C++ Code — Problem: Two Sum

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

// Returns indices of two numbers that add up to target
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;  // value -> index
    
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        
        // Check if complement was seen before
        if (seen.count(complement)) {
            return {seen[complement], i};  // Found!
        }
        
        // Store current number with its index
        seen[nums[i]] = i;
    }
    
    return {};  // No solution found
}

// Variation: Just check if pair exists (no indices needed)
bool hasTwoSum(vector<int>& nums, int target) {
    unordered_set<int> seen;
    
    for (int x : nums) {
        if (seen.count(target - x)) {
            return true;
        }
        seen.insert(x);
    }
    return false;
}

int main() {
    vector<int> arr = {2, 7, 11, 15};
    int target = 9;
    
    vector<int> result = twoSum(arr, target);
    
    if (!result.empty()) {
        cout << "Indices: [" << result[0] << ", " << result[1] << "]" << endl;
        cout << "Values: " << arr[result[0]] << " + " << arr[result[1]] 
             << " = " << target << endl;
    } else {
        cout << "No solution found" << endl;
    }
    
    return 0;
}

Problem: First Non-Repeating Character

Time: O(n) | Space: O(k) where k = unique characters

Identifying Unique Elements

Given a string, find the first character that does not repeat.

Double Pass Approach:

First Pass: Traverse the string to count and store the frequency of each character in a hash map.
Second Pass: Traverse the string again to find the first character with a frequency count of 1.

Optimization Tip:

For lowercase English letters, a simple integer array of size 26 can replace the hash map, reducing memory overhead and lookup times.

C++ Code — Problem: First Non-Repeating Character

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

char firstNonRepeating(const string& s) {
    // Step 1: Count frequency of each character
    unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }
    
    // Step 2: Find first character with frequency 1
    for (char c : s) {
        if (freq[c] == 1) {
            return c;
        }
    }
    
    return '$';  // No non-repeating character
}

// Optimized: Using array instead of map (for lowercase only)
char firstNonRepeatingOptimized(const string& s) {
    int freq[26] = {0};  // For 'a' to 'z'
    
    // Count frequencies
    for (char c : s) {
        freq[c - 'a']++;
    }
    
    // Find first with count 1
    for (char c : s) {
        if (freq[c - 'a'] == 1) {
            return c;
        }
    }
    
    return '$';
}

int main() {
    cout << firstNonRepeating("aabbccd") << endl;      // d
    cout << firstNonRepeating("leetcode") << endl;     // l
    cout << firstNonRepeating("aabbcc") << endl;       // $
    cout << firstNonRepeating("z") << endl;            // z
    
    return 0;
}

Problem: Subarray Sum Equals K

Time: O(n) | Space: O(n)

Range Sum Queries with Hashing

Given an array of integers (which can include negative numbers) and a target value K, find the total number of continuous subarrays that sum up to K.

Prefix Sum Strategy:

Using a naive nested loop takes O(n²) time. We can optimize this to O(n) using a running prefix sum combined with a hash map.

If the difference between two prefix sums equals K: prefixSum[i] - prefixSum[j] = K then the sum of elements from index j + 1 to i is exactly K.

Algorithm:

Maintain a running prefix sum (currentSum).
Store the frequency of each prefix sum in a hash map.
At each element, check if currentSum - K has been encountered. If it has, add its frequency count to your total.
Initialize the map with {0: 1} to handle subarrays starting at index 0.

C++ Code — Problem: Subarray Sum Equals K

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

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> prefixCount;
    prefixCount[0] = 1;  // Important! Empty prefix has sum 0
    
    int currentSum = 0;
    int count = 0;
    
    for (int num : nums) {
        currentSum += num;  // Running prefix sum
        
        // Check if (currentSum - k) was seen before
        // If yes, those many subarrays end here with sum k
        int need = currentSum - k;
        if (prefixCount.count(need)) {
            count += prefixCount[need];
        }
        
        // Add current prefix sum to map
        prefixCount[currentSum]++;
    }
    
    return count;
}

// Returns true if ANY subarray sums to k (simpler version)
bool hasSubarraySum(vector<int>& nums, int k) {
    unordered_set<int> prefixSums;
    prefixSums.insert(0);  // Empty prefix
    
    int currentSum = 0;
    
    for (int num : nums) {
        currentSum += num;
        
        if (prefixSums.count(currentSum - k)) {
            return true;
        }
        
        prefixSums.insert(currentSum);
    }
    
    return false;
}

int main() {
    vector<int> arr1 = {1, 1, 1};
    cout << "Subarrays summing to 2: " << subarraySum(arr1, 2) << endl;  // 2
    
    vector<int> arr2 = {1, 2, 3, -3, 1, 1, 1, 4, 2, -3};
    cout << "Subarrays summing to 3: " << subarraySum(arr2, 3) << endl;  // 7
    
    return 0;
}

Problem: Group Anagrams

Sorting: O(n * k log k) | Count key: O(n * k) where k = avg string length

Grouping Equivalent Character Sets

Given an array of strings, group all anagrams (words that contain the exact same characters in different orders) together.

Sorting Key Approach:

All anagrams yield the exact same sorted string:

"eat" → "aet"
"tea" → "aet"
"ate" → "aet"

We can use the sorted string as a key in a hash map (unordered_map<string, vector<string>>) to group strings together.

Character Count Key Approach (Faster):

Instead of sorting each string (which takes O(k log k) time), we can count the frequency of each character (size 26) and convert this count array into a string key (taking O(k) time).

C++ Code — Problem: Group Anagrams

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

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    
    for (string& s : strs) {
        // Create key by sorting the string
        string key = s;
        sort(key.begin(), key.end());
        
        // Add to the group with this key
        groups[key].push_back(s);
    }
    
    // Collect all groups
    vector<vector<string>> result;
    for (auto& p : groups) {
        result.push_back(p.second);
    }
    
    return result;
}

// Faster approach: Use character count as key (O(n*k) vs O(n*k*log(k)))
vector<vector<string>> groupAnagramsFast(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    
    for (string& s : strs) {
        // Create key from character counts
        int count[26] = {0};
        for (char c : s) {
            count[c - 'a']++;
        }
        
        // Convert counts to string key
        string key;
        for (int i = 0; i < 26; i++) {
            key += "#" + to_string(count[i]);
        }
        
        groups[key].push_back(s);
    }
    
    vector<vector<string>> result;
    for (auto& p : groups) {
        result.push_back(p.second);
    }
    return result;
}

int main() {
    vector<string> words = {"eat", "tea", "tan", "ate", "nat", "bat"};
    
    auto result = groupAnagrams(words);
    
    cout << "Grouped Anagrams:" << endl;
    for (auto& group : result) {
        cout << "[ ";
        for (string& s : group) {
            cout << s << " ";
        }
        cout << "]" << endl;
    }
    
    return 0;
}

Common Mistakes & Interview Tips

Know your complexities!

Hashing Pitfalls

Avoid these common mistakes when using hashing in coding interviews:

1. Poor Table Size Selection

Using a non-prime table size (e.g., m = 10). If many keys share common factors (like ending in 0), they will all map to the same slots, causing frequent collisions.

2. Ignoring Table Load Factors

Failing to resize and rehash the table as it fills up will degrade search performance from O(1) down to O(n). Keep α <= 0.7.

3. Handling Negative Modulo Operations

In C++, -3 % 7 returns -3. To compute positive hash indices for negative keys, use: int index = ((key % m) + m) % m;

4. map vs unordered_map

std::map is implemented as a Red-Black Tree (keeping elements sorted, with operations taking O(log n) time).
std::unordered_map is a hash table (unsorted, with operations taking average O(1) time).

5. Unintended Key Creation

Using myMap[key] automatically inserts an entry with a default value if the key does not exist. Use myMap.count(key) or myMap.find(key) to check for keys safely.

C++ Code — Common Mistakes & Interview Tips

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

int main() {
    // Using [] on non-existent key creates it!
    unordered_map<string, int> mp;
    
    // Creates a "ghost" entry with value 0
    if (mp["ghost"] == 0) {
        cout << "This creates the key!" << endl;
    }
    cout << "Size after check: " << mp.size() << endl;  // 1!
    
    mp.clear();
    
    // SAFE: Use count() or find()
    if (mp.count("ghost") == 0) {
        cout << "Key does not exist (no side effect)" << endl;
    }
    cout << "Size after check: " << mp.size() << endl;  // 0
    
    // Negative modulo
    int key = -15;
    int m = 7;
    // - Range of input values?
    
    return 0;
}

Quick Revision Cheatsheet

Hash Table: Maps keys to values via hash function → O(1) average

Hash Function: h(k) = k % m (m should be prime)

Collision: Resolve with chaining or open addressing

Load Factor: α = n/m, keep ≤ 0.7, rehash when exceeded

unordered_map: Key→Value pairs, use for frequency counting

unordered_set: Only keys, use for existence checking

Two Sum Pattern: Check if (target - x) seen before

Subarray Sum: Prefix sum + hash map

Operation

Average

Worst Case

When Best?

O(1)

O(n)

Low load factor

Insert

O(1)

O(n)

Good hash function

Delete

O(1)

O(n)

Few collisions

Space

O(n)

#include <iostream> #include <unordered_map> using namespace std; int main() { // Creating a hash table (unordered_map in C++) unordered_map<string, int> studentMarks; // Insert: O(1) average studentMarks["Rahul"] = 85; studentMarks["Priya"] = 92; studentMarks["Amit"] = 78; // Lookup: O(1) average cout << "Priya's marks: " << studentMarks["Priya"] << endl; // 92 // Check if key exists if (studentMarks.count("Rahul")) { cout << "Rahul found!" << endl; } // Delete: O(1) average studentMarks.erase("Amit"); return 0; }

#include <iostream> using namespace std; class SimpleHashTable { private: int tableSize; public: SimpleHashTable(int size) : tableSize(size) {} // Division method hash function int hash(int key) { return key % tableSize; } // For string keys - sum of ASCII values int hashString(string key) { int sum = 0; for (char c : key) { sum += c; // Add ASCII value } return sum % tableSize; } };

#include <iostream> #include <vector> #include <list> using namespace std; class HashTableChaining { private: int size; vector<list<int>> table; int hash(int key) { return key % size; } public: HashTableChaining(int s) : size(s), table(s) {} void insert(int key) { int idx = hash(key); table[idx].push_back(key); } };

#include <iostream> #include <vector> using namespace std; class HashTableOpenAddressing { private: int size; vector<int> table; vector<bool> occupied; int hash(int key) { return key % size; } public: HashTableOpenAddressing(int s) : size(s), table(s, -1), occupied(s, false) {} // Insert with linear probing void insert(int key) { int index = hash(key); int originalIndex = index; // Linear probing while (occupied[index]) { cout << "Collision at " << index << ", probing..." << endl; index = (index + 1) % size; // Move to next slot if (index == originalIndex) { cout << "Table is full!" << endl; return; } } table[index] = key; occupied[index] = true; cout << "Inserted " << key << " at index " << index << endl; } // Search with linear probing int search(int key) { int index = hash(key); int originalIndex = index; while (occupied[index]) { if (table[index] == key) { return index; // Found! } index = (index + 1) % size; if (index == originalIndex) break; } return -1; // Not found } void display() { cout << "Hash Table: "; for (int i = 0; i < size; i++) { if (occupied[i]) { cout << "[" << i << "]:" << table[i] << " "; } else { cout << "[" << i << "]:_ "; } } cout << endl; } }; int main() { HashTableOpenAddressing ht(7); ht.insert(10); // 10 % 7 = 3 ht.insert(17); // 17 % 7 = 3 → collision → goes to 4 ht.insert(24); // 24 % 7 = 3 → collision → goes to 5 ht.insert(31); // 31 % 7 = 3 → collision → goes to 6 cout << "\n"; ht.display(); cout << "\nSearch 17: index " << ht.search(17) << endl; // 4 return 0; }

#include <iostream> #include <vector> #include <list> using namespace std; class HashTableWithRehash { private: int size; int count; double maxLoadFactor; vector<list<int>> table; int hash(int key) { return key % size; } // Rehash to a bigger table void rehash() { cout << "\n⚡ REHASHING: Load factor exceeded!" << endl; cout << "Old size: " << size << ", Elements: " << count << endl; int oldSize = size; vector<list<int>> oldTable = table; // Double the size (or use next prime) size = size * 2; table = vector<list<int>>(size); count = 0; // Re-insert all elements for (int i = 0; i < oldSize; i++) { for (int key : oldTable[i]) { insert(key); // Re-hash into new table } } cout << "New size: " << size << endl << endl; } public: HashTableWithRehash(int s = 7, double mlf = 0.7) : size(s), count(0), maxLoadFactor(mlf), table(s) {} void insert(int key) { int index = hash(key); table[index].push_back(key); count++; // Check load factor double loadFactor = (double)count / size; cout << "Inserted " << key << " | Load Factor: " << loadFactor << endl; if (loadFactor > maxLoadFactor) { rehash(); } } double getLoadFactor() { return (double)count / size; } }; int main() { HashTableWithRehash ht(7, 0.7); // Size 7, max load 0.7 // Insert elements until rehash triggers ht.insert(10); ht.insert(20); ht.insert(30); ht.insert(40); ht.insert(50); // This might trigger rehash! ht.insert(60); return 0; }

Feature

unordered_map

unordered_set

Stores

Key-Value pairs

Only Keys

Duplicates

No duplicate keys

No duplicates

Access

map[key]

—

Insert

map[k] = v

set.insert(k)

Check

map.count(k)

set.count(k)

Use Case

Frequency, Lookup

Existence Check

#include <iostream> #include <unordered_map> #include <unordered_set> #include <vector> using namespace std; int main() { // ========== UNORDERED_MAP ========== cout << "=== unordered_map (HashMap) ===" << endl; unordered_map<string, int> freq; // Insert / Update freq["apple"] = 5; freq["banana"] = 3; freq["apple"]++; // Now apple = 6 // Access cout << "apple count: " << freq["apple"] << endl; // 6 // Check existence (SAFE way) if (freq.count("mango") == 0) { cout << "mango not found" << endl; } // Iterate cout << "All items: "; for (auto& p : freq) { cout << p.first << ":" << p.second << " "; } cout << endl << endl; // ========== UNORDERED_SET ========== cout << "=== unordered_set (HashSet) ===" << endl; unordered_set<int> seen; // Insert seen.insert(10); seen.insert(20); seen.insert(10); // Duplicate - ignored! cout << "Size: " << seen.size() << endl; // 2 (not 3!) // Check existence if (seen.count(20)) { cout << "20 exists!" << endl; } // Remove duplicates from array using set vector<int> arr = {1, 2, 2, 3, 3, 3, 4}; unordered_set<int> unique(arr.begin(), arr.end()); cout << "Unique elements: "; for (int x : unique) cout << x << " "; cout << endl; return 0; }

#include <iostream> #include <vector> #include <unordered_map> using namespace std; // Returns indices of two numbers that add up to target vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> seen; // value -> index for (int i = 0; i < nums.size(); i++) { int complement = target - nums[i]; // Check if complement was seen before if (seen.count(complement)) { return {seen[complement], i}; // Found! } // Store current number with its index seen[nums[i]] = i; } return {}; // No solution found } // Variation: Just check if pair exists (no indices needed) bool hasTwoSum(vector<int>& nums, int target) { unordered_set<int> seen; for (int x : nums) { if (seen.count(target - x)) { return true; } seen.insert(x); } return false; } int main() { vector<int> arr = {2, 7, 11, 15}; int target = 9; vector<int> result = twoSum(arr, target); if (!result.empty()) { cout << "Indices: [" << result[0] << ", " << result[1] << "]" << endl; cout << "Values: " << arr[result[0]] << " + " << arr[result[1]] << " = " << target << endl; } else { cout << "No solution found" << endl; } return 0; }

#include <iostream> #include <unordered_map> #include <string> using namespace std; char firstNonRepeating(const string& s) { // Step 1: Count frequency of each character unordered_map<char, int> freq; for (char c : s) { freq[c]++; } // Step 2: Find first character with frequency 1 for (char c : s) { if (freq[c] == 1) { return c; } } return '$'; // No non-repeating character } // Optimized: Using array instead of map (for lowercase only) char firstNonRepeatingOptimized(const string& s) { int freq[26] = {0}; // For 'a' to 'z' // Count frequencies for (char c : s) { freq[c - 'a']++; } // Find first with count 1 for (char c : s) { if (freq[c - 'a'] == 1) { return c; } } return '$'; } int main() { cout << firstNonRepeating("aabbccd") << endl; // d cout << firstNonRepeating("leetcode") << endl; // l cout << firstNonRepeating("aabbcc") << endl; // $ cout << firstNonRepeating("z") << endl; // z return 0; }

#include <iostream> #include <vector> #include <unordered_map> using namespace std; int subarraySum(vector<int>& nums, int k) { unordered_map<int, int> prefixCount; prefixCount[0] = 1; // Important! Empty prefix has sum 0 int currentSum = 0; int count = 0; for (int num : nums) { currentSum += num; // Running prefix sum // Check if (currentSum - k) was seen before // If yes, those many subarrays end here with sum k int need = currentSum - k; if (prefixCount.count(need)) { count += prefixCount[need]; } // Add current prefix sum to map prefixCount[currentSum]++; } return count; } // Returns true if ANY subarray sums to k (simpler version) bool hasSubarraySum(vector<int>& nums, int k) { unordered_set<int> prefixSums; prefixSums.insert(0); // Empty prefix int currentSum = 0; for (int num : nums) { currentSum += num; if (prefixSums.count(currentSum - k)) { return true; } prefixSums.insert(currentSum); } return false; } int main() { vector<int> arr1 = {1, 1, 1}; cout << "Subarrays summing to 2: " << subarraySum(arr1, 2) << endl; // 2 vector<int> arr2 = {1, 2, 3, -3, 1, 1, 1, 4, 2, -3}; cout << "Subarrays summing to 3: " << subarraySum(arr2, 3) << endl; // 7 return 0; }

#include <iostream> #include <vector> #include <string> #include <unordered_map> #include <algorithm> using namespace std; vector<vector<string>> groupAnagrams(vector<string>& strs) { unordered_map<string, vector<string>> groups; for (string& s : strs) { // Create key by sorting the string string key = s; sort(key.begin(), key.end()); // Add to the group with this key groups[key].push_back(s); } // Collect all groups vector<vector<string>> result; for (auto& p : groups) { result.push_back(p.second); } return result; } // Faster approach: Use character count as key (O(n*k) vs O(n*k*log(k))) vector<vector<string>> groupAnagramsFast(vector<string>& strs) { unordered_map<string, vector<string>> groups; for (string& s : strs) { // Create key from character counts int count[26] = {0}; for (char c : s) { count[c - 'a']++; } // Convert counts to string key string key; for (int i = 0; i < 26; i++) { key += "#" + to_string(count[i]); } groups[key].push_back(s); } vector<vector<string>> result; for (auto& p : groups) { result.push_back(p.second); } return result; } int main() { vector<string> words = {"eat", "tea", "tan", "ate", "nat", "bat"}; auto result = groupAnagrams(words); cout << "Grouped Anagrams:" << endl; for (auto& group : result) { cout << "[ "; for (string& s : group) { cout << s << " "; } cout << "]" << endl; } return 0; }

#include <iostream> #include <unordered_map> using namespace std; int main() { // Using [] on non-existent key creates it! unordered_map<string, int> mp; // Creates a "ghost" entry with value 0 if (mp["ghost"] == 0) { cout << "This creates the key!" << endl; } cout << "Size after check: " << mp.size() << endl; // 1! mp.clear(); // SAFE: Use count() or find() if (mp.count("ghost") == 0) { cout << "Key does not exist (no side effect)" << endl; } cout << "Size after check: " << mp.size() << endl; // 0 // Negative modulo int key = -15; int m = 7; // - Range of input values? return 0; }

Quick Revision Cheatsheet

Hash Table: Maps keys to values via hash function → O(1) average

Hash Function: h(k) = k % m (m should be prime)

Collision: Resolve with chaining or open addressing

Load Factor: α = n/m, keep ≤ 0.7, rehash when exceeded

unordered_map: Key→Value pairs, use for frequency counting

unordered_set: Only keys, use for existence checking

Two Sum Pattern: Check if (target - x) seen before

Subarray Sum: Prefix sum + hash map

Hashing (Hash Tables)

Hash Table Complexity at a Glance

What is Hashing?

Instant Key-Value Lookups

Key Features:

When to Use:

Hash Functions (Division Method)

Interactive Hash Table (Division Method)

Mapping Keys to Indices

The Division Method:

Properties of a Good Hash Function:

Collision Handling: Chaining

Interactive Chaining (Linked List)

Resolving Overlapping Buckets

Separate Chaining:

Operations:

Pros and Cons:

Collision Handling: Open Addressing

Probing for Empty Slots

Common Probing Strategies:

Pros and Cons:

Load Factor & Rehashing

Dynamic Table Resizing

Rehashing:

Complexity Check:

HashMap vs HashSet (C++ STL)

STL Hash Containers

1. std::unordered_map<Key, Value> (HashMap)

2. std::unordered_set<Key> (HashSet)

Problem: Two Sum

Finding Target Pairs

Brute Force Approach:

Hashing Approach (O(n) Time):

Problem: First Non-Repeating Character

Identifying Unique Elements

Double Pass Approach:

Optimization Tip:

Problem: Subarray Sum Equals K

Range Sum Queries with Hashing

Prefix Sum Strategy:

Algorithm:

Problem: Group Anagrams

Grouping Equivalent Character Sets

Sorting Key Approach:

Character Count Key Approach (Faster):

Common Mistakes & Interview Tips

Hashing Pitfalls

1. Poor Table Size Selection

2. Ignoring Table Load Factors

3. Handling Negative Modulo Operations

4. map vs unordered_map

5. Unintended Key Creation

Quick Revision Cheatsheet

Hashing (Hash Tables)

Hash Table Complexity at a Glance

What is Hashing?

Instant Key-Value Lookups

Key Features:

When to Use:

Hash Functions (Division Method)

Interactive Hash Table (Division Method)

Mapping Keys to Indices

The Division Method:

Properties of a Good Hash Function:

Collision Handling: Chaining

Interactive Chaining (Linked List)

Resolving Overlapping Buckets

Separate Chaining:

Operations:

Pros and Cons:

Collision Handling: Open Addressing

Probing for Empty Slots

Common Probing Strategies:

Pros and Cons:

Load Factor & Rehashing

Dynamic Table Resizing

Rehashing:

Complexity Check:

HashMap vs HashSet (C++ STL)

STL Hash Containers

1. `std::unordered_map<Key, Value>` (HashMap)

2. `std::unordered_set<Key>` (HashSet)

Hashing Approach (`O(n)` Time):

1. `std::unordered_map<Key, Value>` (HashMap)

2. `std::unordered_set<Key>` (HashSet)

Hashing Approach (`O(n)` Time):