Topics

Hashing: A Study Guide

Hashing turns a key into an array index by running it through a hash function, so a hash table can store and retrieve values in expected constant time. Python’s dict and set are hash tables. That average O(1) lookup is the single most useful tool in interview problem solving: an enormous fraction of “make it faster than brute force” questions come down to “put it in a hash map.”

Why Hashing Matters#

The pattern is almost mechanical. A nested loop that checks every pair is O(n^2); a hash map that remembers what you have already seen makes it O(n). Two Sum, group anagrams, subarray sum equals k, first unique character, and detecting duplicates are all this trade: spend O(n) memory to buy O(n) time. Recognizing when to swap a scan for a lookup is a core interview skill.

Key Operations and Their Big-O#

OperationAverageWorst case
InsertO(1)O(n)
Lookup / membershipO(1)O(n)
DeleteO(1)O(n)
Iterate all keysO(n)O(n)

The worst case (O(n)) happens when many keys collide into the same bucket. With a good hash function and a low load factor it effectively never occurs in practice, but interviewers like to hear that you know it exists.

A Short Example#

Two Sum in one pass: remember each number’s complement as you go.

1def two_sum(nums, target):
2    seen = {}                      # value -> index
3    for i, x in enumerate(nums):
4        need = target - x
5        if need in seen:
6            return [seen[need], i]
7        seen[x] = i
8    return []

Common Pitfalls#

  • Unhashable keys. Lists and other mutable objects cannot be dict keys or set members. Convert to a tuple or a frozenset first.
  • Mutating a key after insertion. If a key’s hash changes after it is stored, you can no longer find it. Keep keys immutable.
  • Assuming order. Sets are unordered; dicts preserve insertion order in modern Python but never sort. Do not rely on iteration order for correctness.
  • Counting characters the hard way. Reach for collections.Counter and defaultdict instead of hand-rolling if key in d checks everywhere.

Where the Curriculum Covers This#

In the 60-day challenge: