Overview

A hash table turns a key into an array index with a hash function, giving average O(1) insert, delete and lookup. Whenever a brute-force solution asks "have I seen something like this before?" inside a loop, a hash map or set can usually remove that inner loop entirely.

Two keys can hash to the same slot (a collision). Real implementations handle this with chaining or open addressing and resize as they fill, which keeps the average cost constant. The worst case is still O(n), which matters in competitive programming where adversarial tests target std::unordered_map.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
Insert / lookup / deleteO(1) average, O(n) worst
Iterate all entriesO(n)
std::map / TreeMap operationsO(log n)

Patterns to recognise

Complement lookup

Use it for: Find two items that combine to a target.

For each x, check whether target − x is already in the map, then insert x.

Seen set

Use it for: Duplicates, cycles in sequences (happy number), first unique element.

Insert as you go and stop the moment an item repeats.

Grouping

Use it for: Bucket items that share a property.

map[key].append(item) — then read the groups.

Code template

Two Sum — complement lookup in one pass
def two_sum(nums, target):
    index_of = {}
    for i, x in enumerate(nums):
        if target - x in index_of:
            return [index_of[target - x], i]
        index_of[x] = i            # insert after checking
    return []

Common mistakes

  • Inserting before checking lets an element pair with itself.
  • Python lists are unhashable — convert to a tuple before using them as keys.
  • In C++, map[key] silently inserts a default value; use find or count to test membership.
  • Never mutate a map while iterating over it.

Quick check

Three questions on Hashing. Get all three right to earn +15 XP.

  1. What is the average cost of looking up a key in a hash map?

  2. In Two Sum with a hash map, what do you look up for each number x?

  3. Which of these cannot be used directly as a hash map key in Python?

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Hashing?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor