🗂️ Hash Tables & Sets

The magic behind instant lookups

← Back to Algorithms

🪄 The big idea

A hash table stores key→value pairs so you can look up any value instantly — O(1) on average. In Python, the dict you already know is a hash table!

How? A hash function turns a key into a number that points straight to a slot in memory. No searching through items one by one — it jumps right to the answer.

scores = {"Alice": 90, "Bob": 85} print(scores["Alice"]) # O(1) — instant, no scanning!

⚡ Why it beats a list

To find a name in a list, you might check every element — O(n). A dict jumps directly to it — O(1).

TaskListDict / Set
Look up a valueO(n)O(1)
Check membership (in)O(n)O(1)
Add an itemO(1)*O(1)

🎒 Sets — a hash table of just keys

A set is like a dict with keys but no values. It stores unique items and checks membership in O(1).

seen = set() seen.add("apple") seen.add("apple") # duplicate ignored print("apple" in seen) # True — instant print(len(seen)) # 1

🧰 The hash table superpower: counting

Hash tables make counting things effortless. This pattern appears in tons of problems:

counts = {} for letter in "banana": counts[letter] = counts.get(letter, 0) + 1 print(counts) # {'b': 1, 'a': 3, 'n': 2}

💡 Remember .get(key, 0)

It returns the current count, or 0 if the key isn't there yet — perfect for "add one to the tally."

✅ What you learned

  • Hash tables (Python dict) give O(1) lookups via a hash function.
  • Sets store unique items with instant membership checks.
  • Use a dict to count things with .get(key, 0) + 1.
  • Trade a little memory for huge speed gains.