λDSA Learning Hubpart of DSA Atlas

Hash Tables

Beginner~3h · 8 lessons12 practice problems

O(1) average lookup by key: hash functions, collision handling by chaining and open addressing, and the frequency/two-sum/grouping patterns built on top.

0 of 8 lessons checked off

Introduction

What it is

  • A hash table stores key → value pairs in an array of buckets. A hash function turns each key into a bucket index, so lookups jump straight to the right neighbourhood instead of searching.
  • Python's dict and set are hash tables; so are Java's HashMap and Go's map. When interviewers say 'use a hash map', this is the machine they mean.

Why it matters

  • It's the single highest-leverage structure in interviews: 'have I seen this before?', 'how many of each?', 'what pairs with x?' — each becomes an O(1) question instead of an O(n) rescan.
  • The classic upgrade story: Two Sum drops from O(n²) to O(n) the moment you remember complements in a dict.

How it works

  • hash(key) % capacity picks a bucket. Two keys can share a bucket — a collision — which must be handled, not hoped away.
  • Chaining stores a small list per bucket; open addressing probes forward for the next free slot (CPython's dict does a variant of this).
  • When the load factor (items ÷ buckets) grows, the table resizes and rehashes everything — O(n) occasionally, amortised into O(1) inserts.

Where it's used

  • Database indexes for exact-match queries, HTTP session stores, compilers' symbol tables, deduplication in ETL pipelines, and caches at every layer of the stack.

In interviews

  • Two Sum and its complement-lookup family, group anagrams (signature keys), duplicate detection, frequency counting, prefix-sum + hash map for subarray sums, LRU/LFU designs.
Analogy: A hash table is a coat check: your ticket number says exactly which hook holds your coat. Nobody walks the racks comparing coats — and two coats on one hook (a collision) just hang together on a small chain.

Interactive diagram

Watch hash(key) route each word to a bucket — and what happens when two words share bucket 3.

7 buckets, chaining for collisions

A hash function maps each key to a bucket index. Colliding keys are chained in a list inside the bucket — lookups stay O(1) on average while chains stay short.

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. Hash functions

    Determinism, uniform spread, and why equal objects must hash equally.

    20 min
  2. Hash maps and hash sets

    Key→value vs membership-only; dict/set operations and costs.

    15 min
  3. Collision handling: chaining

    Buckets hold small chains; load factor keeps chains short.

    20 min
  4. Collision handling: open addressing

    Linear/quadratic probing, tombstones, and clustering.

    20 min
  5. Frequency counting

    Counter patterns: top-k prep, anagram signatures, majority element.

    15 min
  6. The two-sum / complement pattern

    Store what you've seen; ask for what would complete the answer.

    20 min
  7. Grouping and duplicate detection

    Canonical-form keys: sorted strings, frequency tuples, normalised coordinates.

    15 min
  8. Caching use cases

    Memoization tables and LRU — dict as the backbone of speed.

    15 min

Operations

Insert and lookup with chaining

Hash to a bucket, then scan only that bucket's short chain. Uniform hashing keeps chains near length load-factor.

7 buckets, chaining for collisions

A hash function maps each key to a bucket index. Colliding keys are chained in a list inside the bucket — lookups stay O(1) on average while chains stay short.

class HashMap:    """Separate-chaining hash map. Average O(1) get/put/delete."""    def __init__(self, capacity: int = 8) -> None:        self._buckets: list[list[tuple[str, int]]] = [[] for _ in range(capacity)]        self._size = 0    def _bucket(self, key: str) -> list[tuple[str, int]]:        return self._buckets[hash(key) % len(self._buckets)]    def put(self, key: str, value: int) -> None:        bucket = self._bucket(key)        for i, (k, _) in enumerate(bucket):            if k == key:                      # update in place                bucket[i] = (key, value)                return        bucket.append((key, value))        self._size += 1        if self._size > 0.75 * len(self._buckets):            self._resize()    def get(self, key: str) -> int | None:        for k, v in self._bucket(key):            if k == key:                return v        return None    def delete(self, key: str) -> bool:        bucket = self._bucket(key)        for i, (k, _) in enumerate(bucket):            if k == key:                bucket.pop(i)                self._size -= 1                return True        return False    def _resize(self) -> None:        old = self._buckets        self._buckets = [[] for _ in range(2 * len(old))]        self._size = 0        for bucket in old:            for key, value in bucket:                self.put(key, value)          # rehash into new buckets
Time: Average O(1); worst O(n) if everything collidesSpace: O(n + buckets)

Edge cases

  • Updating an existing key must replace, not duplicate.
  • Resize must REHASH — bucket indexes change with capacity.
  • get on a missing key: return a sentinel or raise; pick one and be consistent.

Common mistakes

  • Forgetting the load-factor resize, letting chains grow to O(n).
  • Using unhashable keys (lists) — convert to tuples first.

The complement-lookup pattern (Two Sum)

One pass: before storing each value, ask whether its complement was already seen. The dict trades O(n) space for O(n²)→O(n) time.

The complement-lookup pattern (Two Sum)
def two_sum(nums: list[int], target: int) -> list[int]:    """Indices of the pair summing to target. O(n) time, O(n) space."""    seen: dict[int, int] = {}          # value -> index    for i, x in enumerate(nums):        complement = target - x        if complement in seen:            return [seen[complement], i]        seen[x] = i                    # store AFTER checking    return []
Time: O(n) — one pass, O(1) average per lookupSpace: O(n)

Edge cases

  • Duplicates like [3, 3] with target 6 work because the check precedes the store.
  • The same element must not pair with itself — again guaranteed by check-then-store.
  • No valid pair: define the return (empty list / exception) up front.

Common mistakes

  • Storing before checking, letting x match itself when target = 2x.
  • Building all pairs first 'to be safe' — that's the O(n²) you were asked to beat.

Frequency counting and grouping

Counting is a dict whose values are tallies; grouping is a dict whose keys are canonical forms. Both are one linear pass.

Frequency counting and grouping
from collections import Counter, defaultdictdef top_k_frequent(nums: list[int], k: int) -> list[int]:    """k most frequent values via bucket sort on counts. O(n)."""    counts = Counter(nums)                     # value -> frequency    buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]    for value, freq in counts.items():        buckets[freq].append(value)            # index by frequency    result: list[int] = []    for freq in range(len(buckets) - 1, 0, -1):        for value in buckets[freq]:            result.append(value)            if len(result) == k:                return result    return result
Time: top-k: O(n); grouping: O(total chars × log word length)Space: O(n)

Edge cases

  • k equal to the number of distinct values returns everything.
  • Frequency can't exceed n — hence n+1 buckets.
  • Empty-string words group together under the empty key.

Common mistakes

  • Sorting all items by count (O(n log n)) when bucket-by-frequency gives O(n).
  • Choosing a non-canonical group key (e.g. the first word seen) that splits true groups.

Complexity analysis

OperationBestAverageWorstSpace
get / put / delete / containsO(1)O(1)O(n)O(n)
Resize (rehash all)O(n)O(n)O(n)O(n)
Iterate all entriesO(n)O(n)O(n)O(1)
Find min / max keyO(n)O(n)O(n)O(1)

The worst case is real (adversarial or terrible hashing) but rare; interviews accept 'O(1) average' — say 'average' and you're precise. Note the last row: hash tables have no order; range/min queries want a tree or heap.

Python implementation

Production-quality code with type hints, validation, and docstrings.

Open addressing with linear probing (the other collision strategy)
class ProbingHashSet:    """Hash set using open addressing + linear probing.    Deletions use tombstones so probe chains stay intact."""    _EMPTY = object()    _TOMBSTONE = object()    def __init__(self, capacity: int = 8) -> None:        self._slots: list[object] = [self._EMPTY] * capacity        self._size = 0    def _probe(self, key: object) -> int:        """First slot where key lives or could be inserted."""        i = hash(key) % len(self._slots)        first_tombstone = -1        while self._slots[i] is not self._EMPTY:            if self._slots[i] is self._TOMBSTONE:                if first_tombstone < 0:

What interviewers expect you to know

What interviewers expect you to know

  • The three-step pipeline: hash → index → resolve collisions.
  • 'O(1) average, O(n) worst' — and WHY: collisions concentrate keys; resizing and good hash functions keep that improbable.
  • Requirements on keys: hashable/immutable, and equal keys must have equal hashes.
  • Hash tables are unordered: min, max, range queries, and 'nearest key' all need different structures.

Classic follow-ups

  • "What happens when the table gets full?" — load factor triggers a resize + rehash; amortised O(1) by the doubling argument.
  • "Design a hash map without built-ins" — chaining version above; mention resize policy and update-vs-insert.
  • "Why can't lists be dict keys?" — mutation would change the hash, stranding the entry in the wrong bucket.
  • "When would you NOT use a hash map?" — ordered iteration, range queries, tiny n where an array beats hashing constants, or adversarial inputs without hash randomisation.

How to deploy it in interviews

  • Say the trade explicitly: 'I'll spend O(n) space on a dict to cut lookups to O(1), making the whole pass O(n).'
  • Name your key design: grouping problems are solved the moment you can say 'the canonical key is the sorted word / the frequency tuple / (row−col) for this diagonal'.

Common mistakes

Mutable keys

Lists and dicts can't be keys; a mutated custom key silently loses its entry. Freeze to tuples/frozensets first.

Assuming order

Never rely on bucket order for logic. (CPython dicts preserve insertion order as an implementation detail — sorting problems still need sorting.)

dict[key] on a maybe-missing key

Raises KeyError mid-interview. Reach for .get(key, default), defaultdict, or an explicit `in` check.

Quoting O(1) as a guarantee

It's average case. Say 'average O(1), worst O(n) under collisions' once — it costs three seconds and buys credibility.

Two-sum store-before-check

Storing the current value before checking its complement lets target = 2x match an element with itself.

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

Easy (4)

Medium (7)

Hard (1)

Topic quiz

6 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Concept1. Two different keys land in the same bucket. This is called…
  2. Code output2. What does this print?
    seen = {}nums = [3, 5, 2, 4]target = 6for i, x in enumerate(nums):    if target - x in seen:        print(seen[target - x], i)        break    seen[x] = i
  3. Complexity3. n inserts into a hash map that doubles at 75% load cost…
  4. Scenario4. You need the smallest key ≥ x (successor query) many times. Why is a hash map the wrong tool?
  5. Concept5. In open addressing, deleting by simply emptying the slot is wrong because…
  6. Scenario6. Group these by anagram: ['eat','tea','tan','ate','nat','bat']. What's the best dict key?
0 of 6 answered

Frequently asked questions

Why are Python dict lookups 'O(1) average' and not just O(1)?

Because collisions exist. With a sound hash function and bounded load factor, expected probes are constant — but pathological inputs (or adversarial keys before hash randomisation) can chain everything into one bucket, hitting O(n).

Chaining vs open addressing — which should I describe in an interview?

Chaining is easier to explain and implement correctly under pressure; lead with it. Mention open addressing (better cache behaviour, tombstone subtlety, used by CPython/Go) as the production alternative if probed.

How do I choose the dict key for grouping problems?

Find the property all group members share and normalise it: sorted string for anagrams, (row − col) for a matrix diagonal, tuple of slopes for collinear points. Canonical key design IS the solution.

Summary & cheat sheet

Key takeaways

  • hash → bucket → resolve collisions; load factor + resize keep it O(1) average.
  • The dict answers three interview questions in O(1): seen it? how many? what pairs with it?
  • Check-then-store defeats self-pairing in complement problems.
  • Hash tables trade away ORDER — range and min/max queries belong to trees.
  • Canonical keys turn grouping problems into one-liners.

Formulas & cheat sheet

  • load factor α = items / buckets; expected chain length ≈ α
  • bucket = hash(key) % capacity
  • Resize at α ≈ 0.7, double capacity, rehash everything

Interview checklist

  • I can implement a chaining hash map with resize.
  • I can explain tombstones in open addressing.
  • I can write two-sum blind and justify check-then-store.
  • I can pick canonical keys for grouping problems.