Learn DSA Part 3: Hashing - HashMap and HashSet Explained with Interview Patterns

If one data structure turns slow interview solutions into fast ones, it is the hash table. Whenever you catch yourself writing a nested loop to "find whether something exists" or "count how many times something appears", a hash map can usually remove the inner loop and bring O(n^2) down to O(n).

This is Part 3 of the Learn DSA series. We cover how hashing works, what happens on collisions, the right container to pick in C++ and Java, and the five hashing patterns that solve most interview problems. Code is in C++ and Java.

1. How a hash table works

A hash table stores key-value pairs in an array of buckets. A hash function turns the key into an integer, and that integer modulo the array size picks the bucket. To look up a key you hash it again and go straight to its bucket, so insert, delete and search are O(1) on average, independent of how many items are stored.

The worst case happens when many keys land in the same bucket. A good hash function spreads keys evenly so this almost never happens in practice.

2. Collisions, load factor and rehashing

Two different keys can hash to the same bucket. That is a collision, and there are two classic ways to handle it:

• Separate chaining: each bucket holds a small list of entries. Java's HashMap and C++'s unordered_map both use chaining. Since Java 8, a bucket with many entries is converted into a balanced tree, so the worst case per bucket becomes O(log n).
• Open addressing: all entries live in the array itself; on a collision you probe the next slot (linear probing, quadratic probing or double hashing).

The load factor is entries / buckets. When it crosses a threshold (0.75 by default in Java), the table rehashes: it allocates about twice as many buckets and reinserts every entry. That single step is O(n), but it is rare, so operations stay amortized O(1), just like dynamic arrays in Part 2.

3. Which container to use in C++ and Java

4. The five hashing patterns for interviews

1. Frequency counting. Count occurrences in one pass, then answer questions about the counts: anagrams, first unique character, majority element, top K frequent.

2. Complement lookup (Two Sum). For each element x, ask whether target - x has already been seen. This replaces the O(n^2) pair search with one O(n) pass.

// Two Sum: indices of two numbers adding to target. O(n) time, O(n) space
vector<int> twoSum(const vector<int>& nums, int target) {
    unordered_map<int, int> seen;              // value -> index
    for (int i = 0; i < (int)nums.size(); i++) {
        auto it = seen.find(target - nums[i]);
        if (it != seen.end()) return {it->second, i};
        seen[nums[i]] = i;
    }
    return {};
}

// Two Sum: indices of two numbers adding to target. O(n) time, O(n) space
static int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();   // value -> index
    for (int i = 0; i < nums.length; i++) {
        Integer j = seen.get(target - nums[i]);
        if (j != null) return new int[]{j, i};
        seen.put(nums[i], i);
    }
    return new int[0];
}

3. Prefix sum + hash map. To count subarrays with sum k, keep a running sum s and a map of how many times each prefix sum has occurred. Every earlier prefix equal to s - k ends a valid subarray here. This also works with negative numbers, where a sliding window does not.

// Count subarrays whose sum is exactly k. O(n) time
int subarraySum(const vector<int>& nums, int k) {
    unordered_map<long long, int> freq;
    freq[0] = 1;                       // empty prefix
    long long sum = 0;
    int count = 0;
    for (int x : nums) {
        sum += x;
        auto it = freq.find(sum - k);
        if (it != freq.end()) count += it->second;
        freq[sum]++;
    }
    return count;
}

// Count subarrays whose sum is exactly k. O(n) time
static int subarraySum(int[] nums, int k) {
    Map<Long, Integer> freq = new HashMap<>();
    freq.put(0L, 1);                   // empty prefix
    long sum = 0;
    int count = 0;
    for (int x : nums) {
        sum += x;
        count += freq.getOrDefault(sum - k, 0);
        freq.merge(sum, 1, Integer::sum);
    }
    return count;
}

4. Grouping by a canonical key. Group anagrams by using the sorted word (or a 26-letter count signature) as the key; group points by slope; group strings by pattern.

5. Seen set. Detect duplicates, cycles in sequences (such as the Happy Number problem), or the start of a consecutive run (Longest Consecutive Sequence: only start counting from x when x - 1 is not in the set, which keeps it O(n)).

5. Common pitfalls

• Custom objects as keys: in Java, override both equals() and hashCode(), or lookups silently fail. In C++, provide a hash function for unordered_map keys such as pairs, or encode the pair into a single 64-bit number.
• Mutating a key after inserting it changes its hash, so the entry becomes unreachable. Keys should be immutable.
• No ordering: iteration order of hash containers is unspecified. If the output must be sorted, sort afterwards or use a tree map.
• C++ operator[] inserts: reading m[key] for a missing key creates it with a default value. Use count or find when you only want to check.
• Adversarial inputs in contests: some judges include tests that make unordered_map collide heavily. A custom randomized hash or switching to map avoids the slowdown.

Practice problems

These are classic LeetCode-style problems, listed from easy to hard. Search for them by name and try each before reading a solution.

1. Contains Duplicate (easy)
2. Valid Anagram (easy)
3. Two Sum (easy)
4. First Unique Character in a String (easy)
5. Group Anagrams (medium)
6. Top K Frequent Elements (medium)
7. Longest Consecutive Sequence (medium)
8. Subarray Sum Equals K (medium)
9. 4Sum II (medium)
10. Longest Substring Without Repeating Characters (medium, hash + sliding window)
11. LRU Cache (medium, hash map + linked list)