Introduction to Hash Tables

EditorialUpdated Oct 25, 2026

Is it here? Scanning against jumping

Contains Duplicate: does any value appear twice in nums? Without help, every value has to be compared with every other: 49,995,000 comparisons for 10,000 numbers. Sorting first brings it down to O(n log n). But the question each step really asks is "have I seen this value before?", and there's a structure that answers that in about one step.

A hash table doesn't search for a key. It computes where the key would be. A hash function turns the key into a number, and that number picks one bucket out of an array of buckets. To check a key, you look in its bucket and nowhere else. So one pass over nums, asking the table and then adding to it, answers Contains Duplicate with about one look per number.

A hash table with 8 buckets holding the keys 12, 15, 33, 20, 41, 13, 18, 29, 16, 10, 27, 38, each in bucket key % 8. Looking up 21: 21 % 8 = 5, so only bucket 5 is checked, which holds 13 and 29. Two comparisons say 21 isn't there, where scanning would compare it with all 12 keys.

How it stays fast

Two different keys can land in the same bucket, a collision. Then the bucket holds both, as a short list (that's chaining; Python's dict instead tries the next free slots, open addressing), and a lookup compares the key with what's there.

So the cost of a lookup is the size of one bucket. With n keys in m buckets that's n / m on average, the load factor. Hash tables keep it small by growing: when the load factor passes a limit, the table allocates about twice as many buckets and moves every key to its new bucket. One growth copies everything, but growths get rarer as the table gets bigger: over n inserts the copying adds up to less than n + n/2 + n/4 + … = 2n moves, so each insert costs O(1) on average.

You can watch it happen. Inserting the keys 1 to 1,000 into a C++ unordered_map, the number of buckets went 13, 29, 59, 127, 257, 541, 1,109: roughly doubling, and never fewer than the keys, because its load factor limit is 1. Java's HashMap starts with 16 buckets and grows when it's three quarters full.

The same 12 keys in two tables. With 4 buckets (key % 4) the buckets hold up to 4 keys each. After the table doubles to 8 buckets (key % 8), every key moves to its new bucket and no bucket holds more than 2. Growing keeps the buckets short, and short buckets keep lookups fast.

The catch is the word average. If many keys land in the same bucket, a lookup compares with all of them: O(n). Good hash functions make that unlikely for normal data, but it can be forced. Asking a C++ unordered_map with 62,233 buckets to store 50,000 keys that are all multiples of 62,233 put all 50,000 of them in one bucket. Contest problems use exactly that trick against unordered_map; Java's HashMap limits the damage by turning a long bucket into a balanced tree.

In short: O(1) per lookup and insert on average, O(n) in the worst case, and O(n) memory.

Sets and maps: have I seen it?

There are two kinds of hash table, and every language has both:

a set stores keys only. It answers "have I seen x?". Contains Duplicate is a set.
a map stores a value with each key. It answers "what do I know about x?": where it was, how many times it came up.

Two Sum: find the two indexes whose values add up to target. The brute force tries every pair, O(n²). Turn it around: when you reach x, the partner you need is target - x. If you remember every value you've passed, along with its index, one lookup tells you whether that partner exists. Ask first, then store x: if you stored it first, x could pair with itself.

Two Sum on [3, 8, 4, 11, 6, 5] with target 10 — The row is nums. Below it is the map of values seen so far, value to index, and the lookup for the partner of the current number.

vector<int> twoSum(const vector<int>& nums, int target) {
    unordered_map<int, int> seen;                      // value -> index, for the values before i
    for (int i = 0; i < (int)nums.size(); i++) {
        int need = target - nums[i];
        auto it = seen.find(need);                     // find, not seen[need]: [] would insert need
        if (it != seen.end()) return {it->second, i};  // ask before storing nums[i]
        seen[nums[i]] = i;
    }
    return {};                                         // the problem promises a pair
}

def two_sum(nums, target):
    seen = {}                                   # value -> index, for the values before i
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:                        # ask before storing x, so x can't pair with itself
            return [seen[need], i]
        seen[x] = i
    return []                                   # the problem promises a pair

static int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();      // value -> index, for the values before i
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        if (seen.containsKey(need)) return new int[]{seen.get(need), i};   // ask before storing nums[i]
        seen.put(nums[i], i);
    }
    return new int[0];                                 // the problem promises a pair
}

function twoSum(nums, target) {
    const seen = new Map();                            // value -> index, for the values before i
    for (let i = 0; i < nums.length; i++) {
        const need = target - nums[i];
        if (seen.has(need)) return [seen.get(need), i];   // ask before storing nums[i]
        seen.set(nums[i], i);
    }
    return [];                                         // the problem promises a pair
}

Each prints 2 4, 0 1, 1 2, 0 1 and 0 2 for [3, 8, 4, 11, 6, 5] with target 10, [2, 7, 11, 15] with target 9, [3, 2, 4] with target 6, [3, 3] with target 6 and [-3, 4, 3, 90] with target 0. One pass, one lookup and one insert per number: O(n) time and O(n) space, against O(n²) for every pair.

Every hashing solution answers the same three questions: what do I store, keyed by what, and what do I ask before storing the next one? For Two Sum: indexes, keyed by value, and "is target − x already here?".

A set that knows where runs start

Longest Consecutive Sequence: the longest run of consecutive values, like 1, 2, 3, 4, in an unsorted array, in O(n). Sorting would do it in O(n log n); a set does better, with one idea.

Put every value in a set. A run can be walked upward from any of its values (is x + 1 there? x + 2?), but if you walk from every value, a run of length L gets walked L times. So walk only from a run's start: a value x whose x − 1 isn't in the set. Each run is then walked once, so every value is checked once as a possible start and stepped on once inside its run: at most 2n set lookups, O(n).

int longestConsecutive(const vector<int>& nums) {
    unordered_set<int> values(nums.begin(), nums.end());
    int best = 0;
    for (int x : values) {
        if (values.count(x - 1)) continue;             // x - 1 is there: x isn't the start of a run
        int length = 1;
        while (values.count(x + length)) length++;     // walk the run up from its start
        best = max(best, length);
    }
    return best;
}

def longest_consecutive(nums):
    values = set(nums)
    best = 0
    for x in values:
        if x - 1 in values:
            continue                            # x - 1 is there: x isn't the start of a run
        length = 1
        while x + length in values:             # walk the run up from its start
            length += 1
        best = max(best, length)
    return best

static int longestConsecutive(int[] nums) {
    Set<Integer> values = new HashSet<>();
    for (int x : nums) values.add(x);
    int best = 0;
    for (int x : values) {
        if (values.contains(x - 1)) continue;          // x - 1 is there: x isn't the start of a run
        int length = 1;
        while (values.contains(x + length)) length++;  // walk the run up from its start
        best = Math.max(best, length);
    }
    return best;
}

function longestConsecutive(nums) {
    const values = new Set(nums);
    let best = 0;
    for (const x of values) {
        if (values.has(x - 1)) continue;               // x - 1 is there: x isn't the start of a run
        let length = 1;
        while (values.has(x + length)) length++;       // walk the run up from its start
        best = Math.max(best, length);
    }
    return best;
}

Each prints 4, 9, 0, 3 and 4 for [100, 4, 200, 1, 3, 2], [0, 3, 7, 2, 5, 8, 4, 6, 0, 1], [], [1, 2, 0, 1] and [9, 1, -3, 2, 4, 8, 3, -1, 6, -2, -4, 7].

Hash tables in your language

The hash set and hash map in each language, and the balanced tree that keeps keys in order (O(log n) a step):

Language	Hash set	Hash map	Keys in order
C++	`unordered_set`	`unordered_map`	`set`, `map`
Python	`set`	`dict`; `Counter` and `defaultdict` for counts	none built in
Java	`HashSet`	`HashMap`; `getOrDefault` and `merge` save the null checks	`TreeSet`, `TreeMap`
JavaScript	`Set`	`Map`	none built in

And the trap in each, run on the judge:

C++: reading with m[key] inserts the key when it's missing: after if (c[x] > 0) for three missing keys, the map's size was 3. Use count, find or (C++20) contains to ask.
Python: a key must be hashable, which means it can't change: a list as a key raises TypeError: unhashable type: 'list'. Use a tuple.
Java: the values are Integer objects, and == compares objects, not numbers. Java shares one object for each value from −128 to 127, so two counts of 127 compared with == gave true, and two counts of 128 gave false. Compare with .equals.
JavaScript: a plain object turns every key into a string, so 1 and "1" are the same key: after setting both, the object had 1 key and the Map had 2. Use Map and Set.

When a hash table isn't the answer

Clues that point to a hash table:

"have I seen…", "is there a pair…", "does it appear twice…" in an unsorted input;
you'd otherwise search inside a loop, making it O(n²);
you need to look values up by something other than position.

And when to reach for something else:

You need order (the smallest key, keys in a range, the next bigger key): a hash table has no order. Use a balanced tree map (map/TreeMap), O(log n) per step.
The keys are small integers (0 to n, or 26 letters): a plain array indexed by the key is simpler and faster. That's the next lesson's counting array.
The input is sorted: two pointers or binary search need no extra memory. Two Sum II - Input Array Is Sorted is Two Sum without the map.
Memory is tight: a hash table trades O(n) extra space for its speed.

Common mistakes

Storing before asking. seen[x] = i before the lookup in Two Sum

On [3, 2, 4] with target 6 it returns [0, 0]: 3 found itself as its own partner. Ask first, store second.

Asking with a value that can be 0. if seen.get(need):

On [5, 2, 9] with target 7 it returns [], though 5 + 2 = 7. The partner 5 is stored at index 0, and 0 counts as false, so the lookup looks like a miss. Ask whether the key is there: need in seen (in JavaScript, seen.has(need), not if (seen[need])).

Comparing Integer counts with == in Java. a.get(c) != b.get(c)

A Java check that two strings have the same letter counts said true for "127 a's and a b" against "a b and 127 a's", and false for the same strings with 128 a's. Small tests pass and big ones fail. Use .equals, or compare ints.

Walking every run from every value. Longest Consecutive Sequence without the x - 1 check

Still correct, but on the values 0 to 1,999 it made 2,001,000 set lookups instead of 4,000: every value walked the rest of the run again. Only start at a run's start.

Check yourself

Quiz

1 / 6

Multiple choice

Two Sum on [3, 2, 4] with target 6. Why look up the partner before storing nums[i]?

Practice problems

From easier to harder:

Introduction to Hashing: answer "is x in the array?" queries with a hash set.
Contains Duplicate: a set, asked before adding.
Two Sum: a map from value to index, asked before storing.
Contains Duplicate II: a map from value to its last index.
Longest Consecutive Sequence: a set, walked only from the starts of runs.
Design HashMap: build the buckets yourself.

Next: Frequency Counting with Hash Maps.