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.
To find a name in a list, you might check every element — O(n). A dict jumps directly to it — O(1).
Task
List
Dict / Set
Look up a value
O(n)
O(1)
Check membership (in)
O(n)
O(1)
Add an item
O(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.
🎮 Time to Practice!
Hash your way to instant answers. 🗂️
🔤
Task 1: Count the Letters
Medium
Count how many times each letter appears in "banana" using a dict and .get(). Expected: {'b': 1, 'a': 3, 'n': 2}.
counts = {}
for letter in "banana":
counts[letter] = counts.get(letter, 0) + 1
print(counts)
🎯
Task 2: Two-Sum (the famous one!)
Challenge
Does any pair add up to target? The slow way is O(n²). The fast way: for each number, check if target - number is already in a set — O(n)! Test [2, 7, 11] target 9 → True, then target 20 → False.
🧹
Task 3: Remove Duplicates
Easy
Turn [1, 2, 2, 3, 4, 4] into a sorted list of unique values using a set. Expected: [1, 2, 3, 4]. (Hint: sorted(set(...)).)
Two words are anagrams if they use exactly the same letters. Write is_anagram(a, b) using letter-count dictionaries (or sorted letters). Print it for "listen"/"silent" and "hello"/"world".
In "swiss cheese", find the first character that appears exactly once (ignore spaces). Count everything in a dictionary first, then walk the text again and return the first count of 1.
w
text = "swiss cheese"
counts = {}
for ch in text:
if ch != " ":
counts[ch] = counts.get(ch, 0) + 1
for ch in text:
if ch != " " and counts[ch] == 1:
print(ch)
break
🗂️
Task 7: Group by First Letter
Medium
Sort ["ant", "bee", "alpaca", "bear", "cat"] into a dictionary where each first letter maps to a list of words. Print the dictionary.
words = ["ant", "bee", "alpaca", "bear", "cat"]
groups = {}
for word in words:
letter = word[0]
if letter not in groups:
groups[letter] = []
groups[letter].append(word)
print(groups)
🤝
Task 8: What Do They Share?
Medium
With a = [1, 2, 3, 4] and b = [3, 4, 5], use sets to print: the values in both (&), all values with no repeats (|), and the values only in a (-). Print each as a sorted list.
[3, 4]
[1, 2, 3, 4, 5]
[1, 2]
a = [1, 2, 3, 4]
b = [3, 4, 5]
print(sorted(set(a) & set(b)))
print(sorted(set(a) | set(b)))
print(sorted(set(a) - set(b)))
📊
Task 9: Boss Level: Top Three Words
Boss
Count the words in "the cat and the hat and the bat" with a dictionary, then print the three most common as the: 3 lines, most common first. Hint: sorted(counts.items(), key=lambda pair: pair[1], reverse=True).
the: 3
and: 2
bat: 1
text = "the cat and the hat and the bat"
counts = {}
for word in text.split():
counts[word] = counts.get(word, 0) + 1
ranked = sorted(counts.items(), key=lambda pair: (-pair[1], pair[0]))
for word, count in ranked[:3]:
print(f"{word}: {count}")