Hash maps and sets

coreCommon atGoogleMetaAmazonStripeAnthropicHRTRead firstArraysPractise in the Sandbox →

A hash map runs each key through a hash function to pick a slot in an array, so finding a key means computing one number and looking in one place. Keep the table less than full (the load factor) and the average cost of get, put and delete is O(1). A set is the same structure with keys only.

The idea in plain words

Think of a coat check with 16 numbered hooks. Instead of searching every hook for your coat, the attendant uses a rule: take the first letter of your name, map it to a hook number. To find your coat, apply the rule again and go straight there.

That rule is the hash function. It turns any key (a string, a tuple, a record) into an integer, and hash % capacity turns that integer into a bucket index. Three things make or break it:

• Collisions. Two keys can land in the same bucket (“cat” and “act” under a weak rule). The table needs a plan for that: keep a small list per bucket (chaining), or walk to the next free slot (open addressing).
• Load factor α = keys / buckets. As α rises, collisions get more common and lookups slow down.
• Resizing. When α crosses a threshold, allocate a bigger array (usually double) and rehash every key, because hash % capacity changes when capacity does.

Keep α bounded and a lookup inspects about one or two entries no matter how many million keys you store.

See it

Put a few keys, then switch the hash to sum of char codes and watch anagrams (“cat”, “act”, “tac”) pile into one bucket. Switch to linear probing, delete a key, and see why it leaves a tombstone. Push past the yellow mark to trigger a resize and watch keys move.

Hash table sandbox

sandbox

keyputgetdelete+5 randomgrow ×2clear

separate chaininglinear probing

auto-resize

[0]

[1]

[2]

[3]

fig

[4]

[5]

cat

act

[6]

[7]

dog

load factor α = keys / buckets = 0.50 (yellow mark = resize threshold)

keys4

buckets8

longest chain2

found / insertedmoved by last resizemissingtombstone

log (newest first)

Nothing yet. Try an operation.

When to reach for it

The problem says…	Why a hash map fits
“have I seen this before?”, “find the duplicate”	A set answers membership in O(1) instead of a nested O(n) scan.
“count how many times each…”	Map from item to count. See counting.
“find two things that relate” (a complement, a partner, a previous index)	Store what you’ve seen, then look up the partner in O(1).
“group by” some property	Map from the property (a canonical key) to a list.
“map ids to objects”, caches, indexes	Direct addressing by key; pair it with a linked list when you also need order.
the brute force is O(n²) because of an inner “search” loop	Replace the inner search with a lookup: O(n) total.

How it works

The mechanics inside every hash table

1. Hash. Compute h = hash(key), an integer. Equal keys must produce equal hashes.
2. Index. bucket = h mod capacity (or h & (capacity - 1) when capacity is a power of two).
3. Resolve collisions. Chaining: scan the short list in that bucket. Open addressing: probe bucket, bucket+1, … until you find the key or an empty slot.
4. Compare with equality. A matching hash is only a hint. The table always confirms with == / Equals, because different keys can share a hash.
5. Grow. After an insert, if size / capacity exceeds the max load factor, allocate about twice the buckets and reinsert every key.

Why deletes need tombstones in open addressing

With probing, a lookup stops at the first empty slot. If you simply empty a deleted slot, any key that was placed past it during an earlier collision becomes unreachable. So the slot is marked “deleted” (a tombstone): lookups step over it, inserts may reuse it, and a resize clears them all. Try it in the sandbox above.

What each language actually gives you

	Python	TypeScript / JS	C#
Map	dict	Map<K, V> (prefer over plain {})	Dictionary<TKey, TValue>
Set	set, frozenset	Set<T>	HashSet<T>
Iteration order	insertion order (guaranteed since 3.7)	insertion order (spec)	unspecified, don’t rely on it
Missing key	d[k] raises KeyError; use d.get(k, default)	get returns undefined	indexer throws KeyNotFoundException; use TryGetValue / GetValueOrDefault
Key equality	__eq__ + __hash__	SameValueZero: primitives by value, objects by reference	Equals + GetHashCode (records and tuples by value)
Collision strategy	open addressing, resize at 2/3 full	engine detail (V8: ordered hash tables with chaining)	chaining in parallel arrays, grows when full (α ≈ 1) to a prime ≈ 2×

A classic: one-to-one mapping

Two maps, one per direction, each consulted in O(1). Without the reverse map, "abba" would wrongly match "dog dog dog dog".

Python

follows_pattern.py

def follows_pattern(pattern: str, text: str) -> bool:
    """True if words in `text` map one-to-one onto letters of `pattern` ("abba" ~ "dog cat cat dog")."""
    words = text.split()
    if len(words) != len(pattern):
        return False
    letter_to_word: dict[str, str] = {}
    word_to_letter: dict[str, str] = {}
    for letter, word in zip(pattern, words):
        # 1. look up both directions in O(1) average time
        if letter_to_word.get(letter, word) != word:
            return False
        if word_to_letter.get(word, letter) != letter:
            return False
        # 2. record the pairing (a no-op if it was already there)
        letter_to_word[letter] = word
        word_to_letter[word] = letter
    return True  # 3. every pairing was consistent both ways


if __name__ == "__main__":
    assert follows_pattern("abba", "dog cat cat dog")
    assert not follows_pattern("abba", "dog cat cat fish")
    assert not follows_pattern("aaaa", "dog cat cat dog")
    assert not follows_pattern("abba", "dog dog dog dog")  # needs the reverse map
    assert follows_pattern("", "")
    print("ok")

TypeScript

follows_pattern.ts

import assert from "node:assert/strict";

/** True if words in `text` map one-to-one onto letters of `pattern` ("abba" ~ "dog cat cat dog"). */
export function followsPattern(pattern: string, text: string): boolean {
  const words = text.split(" ").filter((w) => w.length > 0);
  if (words.length !== pattern.length) return false;
  const letterToWord = new Map<string, string>();
  const wordToLetter = new Map<string, string>();
  for (let i = 0; i < words.length; i++) {
    const letter = pattern[i], word = words[i];
    // 1. look up both directions in O(1) average time
    if ((letterToWord.get(letter) ?? word) !== word) return false;
    if ((wordToLetter.get(word) ?? letter) !== letter) return false;
    // 2. record the pairing (a no-op if it was already there)
    letterToWord.set(letter, word);
    wordToLetter.set(word, letter);
  }
  return true; // 3. every pairing was consistent both ways
}

assert.equal(followsPattern("abba", "dog cat cat dog"), true);
assert.equal(followsPattern("abba", "dog cat cat fish"), false);
assert.equal(followsPattern("aaaa", "dog cat cat dog"), false);
assert.equal(followsPattern("abba", "dog dog dog dog"), false); // needs the reverse map
assert.equal(followsPattern("", ""), true);
console.log("ok");

C#

follows_pattern.cs

// True if words in `text` map one-to-one onto letters of `pattern` ("abba" ~ "dog cat cat dog").
static bool FollowsPattern(string pattern, string text)
{
    string[] words = text.Split(' ', StringSplitOptions.RemoveEmptyEntries);
    if (words.Length != pattern.Length) return false;
    var letterToWord = new Dictionary<char, string>();
    var wordToLetter = new Dictionary<string, char>();
    for (int i = 0; i < words.Length; i++)
    {
        char letter = pattern[i];
        string word = words[i];
        // 1. look up both directions in O(1) average time
        if (letterToWord.TryGetValue(letter, out var w) && w != word) return false;
        if (wordToLetter.TryGetValue(word, out var l) && l != letter) return false;
        // 2. record the pairing (indexer set overwrites, never throws)
        letterToWord[letter] = word;
        wordToLetter[word] = letter;
    }
    return true; // 3. every pairing was consistent both ways
}

if (!FollowsPattern("abba", "dog cat cat dog")) throw new Exception("expected true");
if (FollowsPattern("abba", "dog cat cat fish")) throw new Exception("expected false");
if (FollowsPattern("aaaa", "dog cat cat dog")) throw new Exception("expected false");
if (FollowsPattern("abba", "dog dog dog dog")) throw new Exception("needs the reverse map");
if (!FollowsPattern("", "")) throw new Exception("expected true");
Console.WriteLine("ok");

Composite keys: the part that bites in TypeScript

Keys like a grid point (x, y) work by value in Python (tuples, frozen dataclasses) and C# (tuples, records). In JS, Map and Set compare objects by reference, so new Set([[1,2],[1,2]]).size is 2. Encode the key as a string or number first.

Python

composite keys.py

from dataclasses import dataclass


@dataclass(frozen=True)  # frozen => immutable => safe to hash; eq + hash come from the fields
class Point:
    x: int
    y: int


def count_distinct(points: list[tuple[int, int]]) -> int:
    # 1. tuples hash by value, so (1, 2) and (1, 2) are the same key
    return len(set(points))


def visits(path: list[Point]) -> dict[Point, int]:
    counts: dict[Point, int] = {}
    for p in path:
        counts[p] = counts.get(p, 0) + 1  # 2. a value-equal object finds the same bucket
    return counts


if __name__ == "__main__":
    assert count_distinct([(1, 2), (1, 2), (3, 4)]) == 2
    v = visits([Point(0, 0), Point(1, 0), Point(0, 0)])
    assert v[Point(0, 0)] == 2  # 3. a brand-new Point(0, 0) still finds the entry
    try:
        hash([1, 2])  # lists are mutable, so they are unhashable
        raise AssertionError("lists should not hash")
    except TypeError:
        pass
    print("ok")

TypeScript

composite keys.ts

import assert from "node:assert/strict";

type Point = { x: number; y: number };

// Map and Set compare objects and arrays by *reference*, so build a string key.
const keyOf = (p: Point): string => `${p.x},${p.y}`;

export function countDistinct(points: [number, number][]): number {
  // 1. arrays are compared by identity, so encode them as strings first
  return new Set(points.map(([x, y]) => `${x},${y}`)).size;
}

export function visits(path: Point[]): Map<string, number> {
  const counts = new Map<string, number>();
  for (const p of path) {
    const k = keyOf(p); // 2. value-equal points produce the same string key
    counts.set(k, (counts.get(k) ?? 0) + 1);
  }
  return counts;
}

assert.equal(countDistinct([[1, 2], [1, 2], [3, 4]]), 2);
assert.equal(new Set([[1, 2], [1, 2]]).size, 2); // the trap: two different array objects
const v = visits([{ x: 0, y: 0 }, { x: 1, y: 0 }, { x: 0, y: 0 }]);
assert.equal(v.get(keyOf({ x: 0, y: 0 })), 2); // 3. a fresh object still finds the entry
console.log("ok");

C#

composite keys.cs

// Tuples and records get value equality and GetHashCode for free.
static int CountDistinct(List<(int X, int Y)> points) =>
    new HashSet<(int, int)>(points).Count; // 1. ValueTuple hashes by its fields

static Dictionary<Point, int> Visits(List<Point> path)
{
    var counts = new Dictionary<Point, int>();
    foreach (var p in path)
        counts[p] = counts.GetValueOrDefault(p) + 1; // 2. value-equal records share a bucket
    return counts;
}

if (CountDistinct([(1, 2), (1, 2), (3, 4)]) != 2) throw new Exception("expected 2");
var v = Visits([new Point(0, 0), new Point(1, 0), new Point(0, 0)]);
if (v[new Point(0, 0)] != 2) throw new Exception("expected 2"); // 3. a fresh record still finds it
// The trap: a plain class without Equals/GetHashCode compares by reference.
var refs = new HashSet<RefPoint> { new RefPoint(0, 0), new RefPoint(0, 0) };
if (refs.Count != 2) throw new Exception("classes hash by identity");
Console.WriteLine("ok");

record struct Point(int X, int Y);
class RefPoint(int x, int y) { public int X = x, Y = y; }

What it costs

Operation	Average	Worst case	Why
get / contains	O(1)	O(n)	All keys in one bucket turns the table into a list.
put	O(1) amortized	O(n)	An occasional resize copies all n keys; spread over the inserts that caused it, that’s O(1) each.
delete	O(1)	O(n)	Same as lookup.
iterate all keys	O(n + capacity)		Empty buckets are visited too.
space	O(n)		Plus slack: the table is kept 25-50% empty on purpose.

The O(1) has two conditions hidden inside it: the hash spreads keys evenly, and the load factor stays bounded. Hashing the key itself is O(length of key): hashing a 10 KB string is not free, and in an interview you can say “O(1) lookups, O(L) to hash a key of length L”.

The amortized resize argument: doubling from 1 to n copies 1 + 2 + 4 + … + n/2 < n keys in total, so n inserts cost under 2n work. Same trick as a dynamic array.

Expected work per lookup vs load factor

drag the slider

load α = 75%

chaining, key present

1.4

chaining, key absent

1.8

linear probing, present

2.5

linear probing, absent

8.5

Chaining degrades gently: about 1 + α steps. Linear probing is cheaper per step (one array, cache friendly) but a miss costs about ½(1 + 1/(1−α)²), which explodes near full. At 50% a miss is 2.5 probes; at 90% it is 50.5. That is why open-addressing tables resize early.

Variations you’ll meet

• Set = map without values. Use it for membership and dedupe.
• Counter / default dict: collections.Counter, defaultdict(list); in TS map.set(k, (map.get(k) ?? 0) + 1); in C# CollectionsMarshal.GetValueRefOrAddDefault for a single-lookup increment, or plain d[k] = d.GetValueOrDefault(k) + 1.
• Ordered map: insertion order (Python dict, JS Map) is not sorted order. For sorted keys you need a balanced tree: C# SortedDictionary<K,V>, Python third-party sortedcontainers, JS nothing built in. See sorted containers.
• Hash map + linked list: O(1) lookup and O(1) reordering, the backbone of recency-ordered caches. See caching.
• Open addressing variants: linear probing (cache friendly, clusters), quadratic probing, double hashing, Robin Hood hashing (steal slots from “richer” keys to even out probe lengths).
• Bitset / array as a map when keys are small integers or letters: an array of 26 counts beats a hash map. See counting.

Pitfalls

• Mutating a key after inserting it. Its hash changes, so it now lives in the wrong bucket and can’t be found. Python refuses mutable built-ins as keys (list, dict, set are unhashable); C# and JS will happily let you shoot yourself.
• Overriding Equals without GetHashCode (C#) or __eq__ without __hash__ (Python sets __hash__ = None, making the class unhashable). Equal objects must hash equal.
• Object keys in JS. {} as a map coerces keys to strings (map[1] and map["1"] are the same); Map keys objects by reference. Use string or numeric keys for value semantics.
• Relying on iteration order in C#, or on sorted order anywhere.
• Modifying while iterating. Python raises RuntimeError: dictionary changed size during iteration; C# throws InvalidOperationException. Iterate over a copy of the keys.
• Adversarial input. If an attacker can choose keys that all collide, every op is O(n) (hash flooding). Python and .NET randomize string hashes per process for this reason, which is also why hash("cat") differs between runs.

In the interview

• Say what the key is and why it uniquely identifies the thing: “I key on (user_id, day), so two events from the same user on the same day land on one entry.”
• Say “O(1) average” and know the worst case. A strong follow-up answer: “worst case O(n) if everything collides; real tables randomize the hash and resize to keep α bounded.”
• If asked to build one: name the parts (bucket array, hash, collision strategy, load factor, resize), state how delete works for your strategy, and test with a deliberately colliding hash.
• Expect: “what if the keys don’t fit in memory?” (shard by hash, or an on-disk index), “what if two threads write at once?” (a lock or a concurrent map; resizing is the dangerous moment).

Check yourself

Check yourself

pick one

A linear-probing table holds A at slot 3 and B at slot 4 (B hashed to 3 and collided). You delete A by setting slot 3 back to empty. What goes wrong?

ANothing: B is still at slot 4Bget(B) starts at slot 3, sees empty, and reports B missingCThe next insert will overwrite B

Check yourself

pick one

A table doubles its bucket array whenever the load factor passes 0.75. You insert n keys into an initially tiny table. Total work for all resizes?

AO(n²)BO(n log n)CO(n)DO(1)

Check yourself

pick one

In TypeScript, you store visited grid cells as `visited.add([r, c])` and later check `visited.has([r, c])`. What happens?

AWorks, arrays compare by valueBhas() is always false: each [r, c] is a new array object, compared by referenceCTypeScript rejects it at compile time

Practice on your own

Classic textbook exercises, not gym questions:

• Contains duplicate: does any value appear twice? Then: twice within distance k?
• Isomorphic strings: can the letters of s be replaced to get t, one-to-one?
• Happy number: repeatedly replace n by the sum of the squares of its digits; detect whether it reaches 1 or loops (a set of seen values).
• Implement intersection(a, b) for two arrays, keeping duplicates as many times as both contain them.

Go deeper

• Cormen et al., Introduction to Algorithms (CLRS), ch. 11 “Hash Tables”: chaining, open addressing and the load-factor analysis.
• Sedgewick and Wayne, Algorithms, §3.4 “Hash Tables”: separate chaining vs linear probing with code and experiments.
• CPython’s Objects/dictobject.c header comment: the compact, insertion-ordered layout and probing scheme.
• .NET Dictionary<TKey,TValue> source and MDN on Map key equality.

Related

Counting and frequency tablesThe most common thing you'll put in a map.

ArraysThe bucket array underneath, and amortized growth.

Linked listsChains in buckets; map + list for O(1) reordering.

CachingHash maps with an eviction policy.