Hashing in DSA: Hash Maps, Hash Sets and Collisions

Many problems come down to one question asked over and over: have I seen this value before, and where? Scanning the array to answer it costs O(n) each time, so asking it for every element makes the whole solution O(n²). Hashing answers in O(1) on average by spending memory: a hash map remembers each value with something about it, such as its index or a count, and a hash set remembers just the values.

Why scanning is too slow

Two Sum gives you an array and a target and asks for the indices of two numbers that add up to it. Trying every pair is n(n − 1)/2 checks, about 5 × 10⁹ when n = 10⁵, against the roughly 10⁸ simple steps a judge allows in a second. Sorting and two pointers give O(n log n), but sorting moves the elements and the problem wants their original indices.

The idea: remember what you have seen

Walk the array once with a map from each value seen to its index. At each number, work out the complement — the value that would complete the pair — and look it up:

• It is in the map: the pair is the stored index and the current one.
• It is not: store this number and its index, because a later number might need it.

Looking up before storing means the map only holds earlier numbers, so a number never pairs with itself: with target 14, a lone 7 must not count as 7 + 7. One lookup and one insert per element, both O(1) on average, make the search O(n) time with O(n) memory.

1. For each number, the partner it needs is 14 − nums[i]. A map from value to index answers "seen it before?" in O(1), so a single pass is enough; the map starts empty.
2. nums[0] = 7 needs 14 − 7 = 7. The map is still empty — looking before storing is what stops 7 pairing with itself — so store 7 → 0.
3. nums[1] = 3 needs 11, which is not in the map, so no earlier number pairs with it. Store 3 → 1 for the numbers still to come.
4. nums[2] = 9 needs 5: not in the map either, so store 9 → 2.
5. nums[3] = 4 needs 10: not in the map either, so store 4 → 3.
6. nums[4] = 12 needs 2: not in the map either, so store 12 → 4.
7. nums[5] = 2 needs 14 − 2 = 12, and the map says 12 is at index 4: the answer is [4, 5]. One lookup and one store per number make it O(n) time and O(n) space, against O(n²) for every pair.

The code

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

// Indices of two numbers that add up to target, or {-1, -1} if no pair does.
pair<int, int> twoSum(const vector<int>& nums, int target) {
    unordered_map<int, int> indexOf;                 // value -> index where it was seen
    for (int i = 0; i < (int)nums.size(); i++) {
        int need = target - nums[i];
        auto it = indexOf.find(need);                // look first: an earlier number that completes the pair?
        if (it != indexOf.end()) return {it->second, i};
        indexOf[nums[i]] = i;                        // then store, so nums[i] never pairs with itself
    }
    return {-1, -1};
}

int main() {
    vector<int> nums = {7, 3, 9, 4, 12, 2};
    for (int target : {14, 100}) {
        pair<int, int> p = twoSum(nums, target);
        if (p.first == -1) {
            cout << "Target " << target << ": no pair\n";
        } else {
            cout << "Target " << target << ": nums[" << p.first << "] + nums[" << p.second << "] = "
                 << nums[p.first] << " + " << nums[p.second] << "\n";
        }
    }
    return 0;
}

import java.util.HashMap;
import java.util.Map;

public class Main {
    // Indices of two numbers that add up to target, or {-1, -1} if no pair does.
    static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> indexOf = new HashMap<>();   // value -> index where it was seen
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            Integer j = indexOf.get(need);                 // look first: an earlier number that completes the pair?
            if (j != null) return new int[] {j, i};
            indexOf.put(nums[i], i);                       // then store, so nums[i] never pairs with itself
        }
        return new int[] {-1, -1};
    }

    public static void main(String[] args) {
        int[] nums = {7, 3, 9, 4, 12, 2};
        for (int target : new int[] {14, 100}) {
            int[] p = twoSum(nums, target);
            if (p[0] == -1) {
                System.out.println("Target " + target + ": no pair");
            } else {
                System.out.println("Target " + target + ": nums[" + p[0] + "] + nums[" + p[1] + "] = "
                        + nums[p[0]] + " + " + nums[p[1]]);
            }
        }
    }
}

def two_sum(nums, target):
    """Indices of two numbers that add up to target, or None if no pair does."""
    index_of = {}                        # value -> index where it was seen
    for i, value in enumerate(nums):
        need = target - value
        if need in index_of:             # look first: an earlier number that completes the pair?
            return index_of[need], i
        index_of[value] = i              # then store, so value never pairs with itself
    return None


nums = [7, 3, 9, 4, 12, 2]
for target in (14, 100):
    found = two_sum(nums, target)
    if found is None:
        print(f"Target {target}: no pair")
    else:
        i, j = found
        print(f"Target {target}: nums[{i}] + nums[{j}] = {nums[i]} + {nums[j]}")

// Indices of two numbers that add up to target, or null if no pair does.
function twoSum(nums, target) {
  const indexOf = new Map(); // value -> index where it was seen
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (indexOf.has(need)) return [indexOf.get(need), i]; // look first: an earlier number that completes the pair?
    indexOf.set(nums[i], i); // then store, so nums[i] never pairs with itself
  }
  return null;
}

const nums = [7, 3, 9, 4, 12, 2];
for (const target of [14, 100]) {
  const found = twoSum(nums, target);
  if (found === null) {
    console.log(`Target ${target}: no pair`);
  } else {
    const [i, j] = found;
    console.log(`Target ${target}: nums[${i}] + nums[${j}] = ${nums[i]} + ${nums[j]}`);
  }
}

Target 14: nums[4] + nums[5] = 12 + 2
Target 100: no pair

How a hash table is stored

Underneath every hash map and set is a hash table: an ordinary array of buckets plus a hash function that turns any key into a whole number, reduced to a bucket index — typically the hash modulo the number of buckets. Finding a key repeats the same calculation, so the key's own value says where to look:

1. A hash table is an ordinary array of 8 buckets. A key's bucket is computed from the key itself — here key mod 8 — so finding it later repeats the same sum instead of searching.
2. 12 mod 8 = 4, so 12 goes into bucket 4. Equal keys always give equal buckets — the hash must be deterministic.
3. 7 mod 8 = 7, so 7 goes into bucket 7.
4. 20 mod 8 = 4, but 12 is already in bucket 4: a collision. Separate chaining just adds 20 to that bucket's list.
5. 33 mod 8 = 1, so 33 goes into bucket 1.
6. 15 mod 8 = 7, but 7 is already in bucket 7: a collision. Separate chaining just adds 15 to that bucket's list.
7. Finding 20: 20 mod 8 = 4, then compare along bucket 4's list — 2 comparisons. The keys in other buckets are never looked at.
8. Finding 28: bucket 4 again, and neither 12 nor 20 is 28, so it is not in the table. A lookup costs only the length of one list — kept short, that is O(1).

A hash function must be deterministic and should spread keys evenly. Strings mix every character (Java's String.hashCode uses powers of 31), so hashing a string of length k costs O(k).

Collisions: chaining and open addressing

There are far more possible keys than buckets, so collisions are certain. Separate chaining, drawn above, keeps a list per bucket; C++'s unordered_map and Java's HashMap work this way (Java turns a bucket of more than eight entries into a small tree). Open addressing keeps every key in the array and probes for a free slot; Python's dict and set do this, with a more scattered probe order than the linear one here:

1. Open addressing keeps every key in the array itself — no lists. A key starts at its home slot, key mod 8; if that slot is taken it tries the next one, and the next, until one is free.
2. 12 mod 8 = 4, and slot 4 is free: 12 goes there.
3. 7 mod 8 = 7, and slot 7 is free: 7 goes there.
4. 20 mod 8 = 4, but slot 4 holds 12. Linear probing tries the next slot, 5, which is free — 20 lives there, away from home.
5. 33 mod 8 = 1, and slot 1 is free: 33 goes there.
6. 15's home slot 7 holds 7, and probing past the end wraps round to slot 0, which is free. Linear probing treats the array as a circle.
7. Finding 15 follows the same path: slot 7 holds 7, not 15, so step on to slot 0 — found. A lookup stops at the key or at an empty slot, which proves the key is absent.

Why lookups are O(1) on average

Either way, a lookup only compares the key with the few keys sharing its bucket or probe path. The design question is how to keep that number small, and the answer is the load factor:

1. The load factor is keys divided by buckets. With 3 keys in 4 buckets it is 0.75, and 5 and 9 already share bucket 1. More keys in the same 4 buckets would mean longer lists to search.
2. Adding 16 would push the load past 0.75, so the table doubles to 8 buckets and re-inserts every key, since each key's bucket depends on the bucket count. One resize costs O(n), but doubling makes it rare: amortised O(1).
3. 27 and 14 go in without a resize. The load stays at or below 0.75, so a lookup checks about one key on average, whatever n is: that is the O(1). Java's HashMap resizes past 0.75; C++'s unordered_map past 1.0.
4. The guarantee rests on the hash spreading keys. A hash that sent every key to bucket 0 would make one list of all n keys: each lookup O(n), and n inserts O(n²). Built-in hashes do not do this by accident — but inputs built to attack them can.

In an interview, say "O(1) on average". When you need the keys in order, C++'s map and Java's TreeMap are balanced search trees: O(log n) per operation, but sorted, with the nearest key above or below any value.

Hash maps and hash sets in each language

The traps: in C++, reading m[k] for a missing key inserts it; in Java, unboxing the null that get returns throws; Python lists cannot be keys; a plain JavaScript object turns every key into a string, so prefer Map. And never rely on iteration order — sort before printing, as the grouping program below does.

Pattern: counting how often each value appears

The most common use of a hash map is a frequency count: one pass of count[x] += 1, then answer from the counts. Majority Element wants a count above n/2; First Unique Character in a String counts, then walks the string again so the original order decides.

Pattern: grouping by a key

To put items into groups, choose a canonical key that every member of a group shares and no outsider has, and keep a map from key to members:

1. To group anagrams, give every word a canonical key that all its anagrams share and no other word has: its letters in sorted order. Then keep a map from key to the list of words.
2. "eat" sorts to "aet", a key not seen before, so it starts a new list.
3. "tea" sorts to "aet" too, so it joins the list that already holds "eat". One lookup, no comparing words with each other.
4. "tan" sorts to "ant", a key not seen before, so it starts a new list.
5. "ate" sorts to "aet" too, so it joins the list that already holds "eat" and "tea". One lookup, no comparing words with each other.
6. "nat" sorts to "ant" too, so it joins the list that already holds "tan". One lookup, no comparing words with each other.
7. "bat" sorts to "abt", a key not seen before, so it starts a new list.
8. Every word was handled once: 3 groups from 6 words. Sorting a word of length k costs O(k log k); a key made of the 26 letter counts costs O(k) for long words.

The same idea groups strings that are equal after some allowed change, as in Groups of Special-Equivalent Strings.

The code

Because hash-map order differs between languages, the program sorts each group and then the groups before printing.

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

// Groups words that are anagrams of each other.
vector<vector<string>> groupAnagrams(const vector<string>& words) {
    unordered_map<string, vector<string>> groups;    // sorted letters -> the words that have them
    for (const string& word : words) {
        string key = word;
        sort(key.begin(), key.end());                // anagrams share the same sorted letters
        groups[key].push_back(word);
    }
    vector<vector<string>> result;
    for (auto& entry : groups) result.push_back(entry.second);
    return result;
}

int main() {
    vector<string> words = {"eat", "tea", "tan", "ate", "nat", "bat"};
    vector<vector<string>> groups = groupAnagrams(words);
    vector<string> lines;
    for (vector<string>& group : groups) {
        sort(group.begin(), group.end());
        string line;
        for (const string& word : group) line += (line.empty() ? "" : " ") + word;
        lines.push_back(line);
    }
    sort(lines.begin(), lines.end());                // hash-map order is not fixed: sort to print
    for (const string& line : lines) cout << line << "\n";
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    // Groups words that are anagrams of each other.
    static List<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> groups = new HashMap<>();   // sorted letters -> the words that have them
        for (String word : words) {
            char[] letters = word.toCharArray();
            Arrays.sort(letters);
            String key = new String(letters);                  // anagrams share the same sorted letters
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
        }
        return new ArrayList<>(groups.values());
    }

    public static void main(String[] args) {
        String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<String> lines = new ArrayList<>();
        for (List<String> group : groupAnagrams(words)) {
            Collections.sort(group);
            lines.add(String.join(" ", group));
        }
        Collections.sort(lines);                               // hash-map order is not fixed: sort to print
        for (String line : lines) System.out.println(line);
    }
}

def group_anagrams(words):
    """Group words that are anagrams of each other."""
    groups = {}                                  # sorted letters -> the words that have them
    for word in words:
        key = "".join(sorted(word))              # anagrams share the same sorted letters
        groups.setdefault(key, []).append(word)
    return list(groups.values())


words = ["eat", "tea", "tan", "ate", "nat", "bat"]
lines = [" ".join(sorted(group)) for group in group_anagrams(words)]
lines.sort()                                     # hash-map order is not fixed: sort to print
for line in lines:
    print(line)

// Groups words that are anagrams of each other.
function groupAnagrams(words) {
  const groups = new Map(); // sorted letters -> the words that have them
  for (const word of words) {
    const key = word.split("").sort().join(""); // anagrams share the same sorted letters
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(word);
  }
  return [...groups.values()];
}

const words = ["eat", "tea", "tan", "ate", "nat", "bat"];
const lines = groupAnagrams(words).map((group) => group.sort().join(" "));
lines.sort(); // hash-map order is not fixed: sort to print
for (const line of lines) console.log(line);

ate eat tea
bat
nat tan

Pattern: a set of values seen

When you need presence and nothing else, use a hash set. Contains Duplicate stops the moment a value is already in the set; Jewels and Stones makes checking each stone O(1). The cleverest use in this stage is Longest Consecutive Sequence, in O(n) despite a loop inside a loop:

1. Put every value in a set — drawn here on a number line, though nothing is sorted. A run of consecutive values can only begin at a value whose left neighbour, x − 1, is missing.
2. x = 100: 99 is missing, so 100 starts a run, but 101 is missing too: length 1.
3. x = 4: 3 is in the set, so 4 sits inside a run that starts further left. Skip it — one lookup, no walk.
4. x = 200: 199 is missing, so 200 starts a run, but 201 is missing too: length 1.
5. x = 1: 0 is missing, so 1 starts a run. Walk right while the next value is present: 1, 2, 3, 4 — length 4.
6. x = 3: 2 is in the set, so 3 sits inside a run that starts further left. Skip it — one lookup, no walk.
7. x = 2: 1 is in the set, so 2 sits inside a run that starts further left. Skip it — one lookup, no walk.
8. Longest run: 4. 12 lookups for n = 6: each value is checked once as x and walked over at most once, inside its own run, so the total is O(n). Without the start rule, walking from every value is O(n²).

A map in each direction solves mapping problems: Isomorphic Strings needs every character to map to exactly one other and no two to map to the same one, so it keeps both maps and fails on the first contradiction.

When an array beats a hash map

If the keys are small integers in a known range, the key itself is the index — 26 slots for lowercase letters, count[c - 'a']++ — with no hash, no collisions and a fixed order. Find All Numbers Disappeared in an Array even uses the input as its own table, negating index v − 1 to mark v as seen. Large, negative or non-numeric keys still need a hash map; the Strings lesson uses the 26-slot count throughout.

Time and space complexity

Hashing nearly always trades O(n) memory for a factor of n in time — a good trade when memory is measured in megabytes.

How to recognise a hashing problem

• "Find two elements that…" in an unsorted array, especially by index: a complement lookup.
• "How many times", "most frequent", "first non-repeating": a frequency count.
• "Group", "anagram", "same pattern": a canonical key and a map of lists.
• "Contains", "duplicate", "missing": a hash set, or an array for small values.
• A brute force asking "is X in the array?" inside a loop: replace the search with a lookup.
• A subarray sum equals k: prefix sums in a hash map, built up in prefix sums.

Common mistakes

• Storing before looking. In Two Sum, inserting first lets a number pair with itself.
• Relying on iteration order. Sort when the output must be ordered.
• Creating keys by reading them. In C++, if (m[k] > 0) inserts k; use count or find.
• Identity-compared keys. Java and JavaScript arrays with equal contents are different keys; convert to a string.
• Long keys. Hashing a string of length k is O(k), so a map keyed on long substrings is not O(1) per operation.
• A map where an array would do. For 26 letters, an array is simpler and faster.

Practice in this order

1. Jewels and Stones: a set instead of a scan.
2. Two Sum: the complement lookup.
3. First Unique Character in a String: count, then a second pass.
4. Majority Element: a frequency count.
5. Isomorphic Strings: a map each way.
6. Find All Numbers Disappeared in an Array: the input as its own table.
7. Groups of Special-Equivalent Strings: a canonical key.
8. Longest Consecutive Sequence: the start-of-a-run rule.
9. Top K Frequent Elements: counts, then buckets.

Every hashing problem in the catalogue is on the hash table problem list. When the first six feel routine, move on to Strings.