Hash Tables and Sets

Intuition: the theater coat check

You hand in your jacket at the coat check and get ticket number 42. At the end of the night, the attendant doesn't search every hanger; they walk straight to hook 42. A hash table works the same way: from the key it computes exactly where the value lives, instead of scanning everything.

That's why lookup, insertion, and deletion take O(1) on average. In an array, lookup costs O(n); in a sorted array, O(log n). A lot of interview problems are solved by switching from "check everything" to "ask the hash table," and you're about to learn how to do that.

How it works inside

Under the hood it's a plain array. Its slots are called buckets. To store a key, the table takes two steps:

1. A hash function turns the key into a number: hash("cat") → 9182734.
2. That number is reduced to a bucket index: 9182734 % 7 → 1. The key goes into bucket 1.

A lookup repeats the same two steps and lands right in the correct bucket.

Collisions

There's a finite number of buckets and an infinite number of possible keys, so two different keys sometimes end up in the same bucket. That's called a collision, and it happens in every hash table. There are two main ways to handle it:

• Chaining: each bucket holds a small list, and a lookup walks through it. In the diagram above, "dog" and "fox" sit in a chain.
• Open addressing: if a bucket is taken, the table tries the next one according to a fixed rule.

When the number of elements gets large relative to the number of buckets (that ratio is called the load factor), the table resizes. It usually roughly doubles and moves every element over. A single resize costs O(n), but it happens rarely, so insertion stays O(1) on average. This is called an amortized bound.

💡 A good hash function spreads keys evenly across buckets. Then the chains stay short and everything is fast. You won't have to write one yourself in an interview: you'll use the built-in dict, HashMap, unordered_map, Map, map.

Set vs map

	Set	Map / dict
What it stores	keys only	key → value pairs
Main question	"is this element here?"	"what's stored under this key?"
Python	set()	dict()
Java	HashSet	HashMap
C++	unordered_set	unordered_map
JS	Set	Map
Go	map[K]struct{}	map[K]V

They're built the same way. You can think of a set as a map whose values don't matter.

Three go-to patterns

1. "Have I seen this before?" Walk through the array and put elements into a set. Before adding one, check whether it's already there. That's how you find duplicates, the first repeated character, or a cycle in a sequence.

2. Counting frequencies. The key is the element, the value is how many times it appeared. Reach for this when the problem asks for "the most frequent element," "appears exactly once," or "same set of letters."

3. Grouping by key. For each element, compute a "group signature" and use it as the key, with a list of elements as the value. For example, grouping words by their first letter: groups[w[0]].append(w). The interesting part of these problems is coming up with the right key.

💡 If the problem says "find a pair," "have we seen," "how many times," or "group," you almost certainly need a hash table.

Code template: frequencies and duplicates

def count_freq(words):
    freq = {}
    for w in words:
        freq[w] = freq.get(w, 0) + 1  # 0 if the key isn't there yet
    return freq

def has_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:      # seen it already: found a duplicate
            return True
        seen.add(x)
    return False

print(count_freq(["a", "b", "a"]))  # {'a': 2, 'b': 1}
print(has_duplicate([1, 2, 3, 1]))  # True

Complexity

Operation	Average	Worst
Insert	O(1)*	O(n)
Lookup	O(1)	O(n)
Delete	O(1)	O(n)
Memory	O(n)	O(n)

* amortized, counting the occasional resize.

The O(n) worst case happens when every key lands in the same bucket and a lookup turns into a walk down a long chain. That comes from a bad hash function or from deliberately crafted keys (a hash-flooding attack). Both examples above run in O(n) time and O(n) memory.

How it sounds in an interview

"The naive approach compares every pair, which is O(n²). Instead I'll keep a hash set and make a single pass over the array. For each element I check whether it's already in the set, which is O(1) on average. That's O(n) time and O(n) extra space overall. In the worst case, collisions can degrade operations to O(n), but in practice that's rare."

You name the naive solution, improve on it, and honestly call out the worst case. Interviewers appreciate that move.

Common mistakes

• A mutable key. In Python a list can't be a key; you need a tuple. In Java, don't mutate an object that's already a key in a HashMap: its hash changes and the table "loses" it.
• A custom class without equals/hashCode (Java) or without a hasher (C++). Then two objects that mean the same thing are treated as different.
• Relying on order. A hash table doesn't guarantee iteration order, and in Go it's deliberately randomized. If you need an order, sort the keys separately.
• Reading with freq[w] in C++. That quietly creates the key with value 0. To check for a key, use count or find.
• Forgetting about memory. O(1) time comes at the cost of O(n) memory, and it's worth saying so out loud.

Now you know how a hash table works and how to use its three main patterns. Next up are problems where you'll need to spot them in the statement.