Hash Maps & Dictionaries

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Module 7, Chapter 5 Time to complete: ~25 minutes

Table of Contents

1. The Idea Behind Hashing
2. Python's dict Is a Hash Map
3. Why Hash Map Operations Are O(1) Average Case
4. Collisions and Why Worst Case Is O(n)
5. Common Dictionary Operations
6. Summary & Next Steps

1. The Idea Behind Hashing

A hash function takes a key (a string, a number, a tuple — anything "hashable") and converts it into an integer, which is then used as an index into an internal array of "buckets." Instead of scanning every item to find a match (as a list requires), you compute the key's hash, jump straight to its bucket, and look there.

key "apple" → hash function → 84172... → bucket index (hash % array_size) → value stored here

This is the single idea that makes hash maps fast: you compute where to look instead of searching for it.

2. Python's dict Is a Hash Map

Every dict you've used since Python Notes Module 1 Chapter 8 is a hash map under the hood:

ages = {"Alice": 30, "Bob": 25, "Carol": 35}
 
ages["Dave"] = 40          # insert — hash "Dave", place at its bucket
print(ages["Alice"])       # lookup — hash "Alice", jump to its bucket
del ages["Bob"]             # delete — hash "Bob", remove from its bucket
print("Alice" in ages)      # membership test — hash "Alice", check its bucket

None of these operations scan the dictionary — each one computes a hash and goes (almost) directly to the relevant bucket.

3. Why Hash Map Operations Are O(1) Average Case

Recall Module 1 Chapter 5's best/average/worst-case framework — hashing is the textbook example of why that distinction matters:

For virtually all practical inputs, Python's dict behaves like the average case — get, set, and delete are all effectively O(1). This is why swapping a list for a dict/set turned an O(n) scan into an O(1) lookup back in Module 1 Chapter 1's motivating example — that wasn't a coincidence, it's the entire point of this module.

4. Collisions and Why Worst Case Is O(n)

A collision happens when two different keys hash to the same bucket. Python's dict handles this internally (via a technique called open addressing) by finding another nearby slot for the second key — but if collisions become frequent, buckets end up holding multiple items, and finding the right one degrades toward a linear scan within that bucket.

In practice, Python's hash function and internal resizing keep collisions rare enough that this worst case almost never surfaces in interview-scale problems — but it's worth naming explicitly: "hash maps are O(1)" is really "hash maps are O(1) average case, O(n) worst case," and interviewers do sometimes ask you to state that caveat.

5. Common Dictionary Operations

counts = {}
 
counts["a"] = counts.get("a", 0) + 1     # safe increment — no KeyError if "a" is missing
print(counts.get("z", 0))                  # returns 0 instead of raising KeyError
 
from collections import defaultdict
counts2 = defaultdict(int)                 # missing keys default to int() == 0
counts2["a"] += 1                           # no .get() needed
 
for key, value in counts.items():           # iterate key-value pairs — O(n)
    print(key, value)
 
print(list(counts.keys()))                   # all keys
print(list(counts.values()))                 # all values

6. Summary & Next Steps

Key Takeaways

• A hash function converts a key into an array index, letting you jump directly to a value instead of scanning for it.
• Python's dict is a hash map — get/set/delete/in are all O(1) average case.
• Collisions (two keys hashing to the same bucket) are why the worst case is O(n) — rare in practice, but worth stating explicitly in interviews.
• dict.get(key, default) and collections.defaultdict avoid KeyError when a key might not exist yet.

Concept Check

1. Why does computing a hash let you avoid scanning the whole structure to find a key?
2. What's the average-case complexity of a dictionary lookup, and what causes the worst case to degrade to O(n)?
3. What does counts.get("a", 0) + 1 do that counts["a"] + 1 would not, if "a" isn't already a key?

Next Chapter

→ Chapter 2: Sets

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index