1. Concept library
  2. Data Structures & Algorithms
  3. Module 3: Hash maps and sets

Concept

Lookup trade-offs

Hash maps give O(1) average lookups but no order; sorted arrays give O(log n) lookups and ordered traversal; balanced trees give both at O(log n). The right structure depends on which operations dominate.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

  1. Compare hash maps, sorted arrays and balanced trees on lookup, insert and ordered traversal
  2. Choose the structure for a workload and justify it with the dominant operation
  3. Spot a hash map whose keys are sorted on every query

In practice

A few lines that show Lookup trade-offs doing its job.

Python
import bisect

# Membership only: a set.
ids = {42, 7, 19}
7 in ids                              # O(1)

# Membership plus "next value above x": keep it sorted.
sorted_ids = [7, 19, 42]
i = bisect.bisect_right(sorted_ids, 20)
sorted_ids[i]                         # 42, in O(log n)

The common mistake

Watch for

Choosing a hash map by reflex and then sorting its keys on every query. If you need order more than once, a sorted structure is cheaper overall.

What to know first

Your roadmap puts these before Lookup trade-offs, unless you already know them.

How it stays learned

Once a session shows you understand Lookup trade-offs, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

  1. Day 3First recall, while it is fresh
  2. Day 7Second, a week on
  3. Day 18Last, when it has settled
Previous in the module← Frequency counting