Track 04 of 10

Data StructuresIntermediate Level~20 Mins

4. Hash Maps & Sets: O(1) Amortized Mechanics

Understand hash functions, key hashing, bucket indexing, and collision resolution.

The "WHY" Core Principle

Searching a list requires scanning item by item (O(N)). A Hash Map passes the key through `hash(key)`, takes `hash % bucket_count`, and jumps directly to that memory slot in O(1) time!

Interactive Visualizer

Interactive Big-O Complexity 2D Graph & Operation Profiler

Move the slider to observe operation growth curves smoothly scale as input size N increases.

Input N:25

Smooth 2D Growth Curves (X = Input N, Y = Relative Operation Growth)Hover over graph to inspect coordinates

N = 1 (Small Input)

N = 100 (Large Input)

Y = Operation Complexity

Toggle Curves:

O(1)Constant Time

Instant (<0.01 ms)

Operations at N = 25

Python Pattern:

def get_first(arr):
    return arr[0]  # Direct memory offset

Analogy: Jumping directly to a page number in an indexed book.

O(log N)Logarithmic Time

Ultra Fast (~0.02 ms)

Operations at N = 25

Python Pattern:

while low <= high:
    mid = (low + high) // 2  # Halve search space

Analogy: Finding a name in a phonebook by opening to the middle repeatedly.

O(N)Linear Time

Fast (~0.1 ms)

Operations at N = 25

Python Pattern:

for item in arr:
    if item == target: return True  # Single sweep

Analogy: Reading every page in a book line by line from front to back.

O(N log N)Linearithmic Time

Efficient (~0.8 ms)

116

Operations at N = 25

Python Pattern:

def merge_sort(arr):
    # Divide array (log N) & merge halves (N)

Analogy: Sorting a deck of cards by splitting into 2 piles recursively.

O(N²)Quadratic Time

Moderate (~15 ms)

625

Operations at N = 25

Python Pattern:

for i in range(n):
    for j in range(i + 1, n):  # Compare every pair

Analogy: Comparing every card in a deck against every other card.

O(2ⁿ)Exponential Time

CPU Crash Threat!

∞ (Explodes CPU)

Operations at N = 25

Python Pattern:

def fib(n):
    return fib(n-1) + fib(n-2)  # 2 recursive calls per step

Analogy: Trying every possible combination password lock.

WHY BIG-O MATTERS FOR HIGH-PERFORMANCE CODE:

Notice how O(1) and O(log N) remain near the bottom of the graph even as $N$ grows, while O(N²) and O(2ⁿ) curve steeply upward. This difference is why selecting the correct data structure prevents CPU bottlenecks!

Interactive Code Snippets (1 Lessons)

Lesson 01

O(1) Hash Lookup vs O(N) List Lookup

O(1) Set vs O(N) ListO(N)

Benchmark Python `dict` key lookup against `list` search with 50,000 items.

WHY Under The Hood:

Dict lookup computes `hash(key) & mask` to immediately locate the bucket index. List lookup performs a linear scanning loop.

CPython C Struct Detail: Python dicts use a combined dense key table + sparse index table layout.

O(1) Hash Lookup vs O(N) List Lookup

Pyodide WASM Engine

Type, edit code, and click 'Run & Profile' to see live runtime ms and operation count!

Python 3.12 Code (Editable)

Expected:Time: O(1) Set vs O(N) ListSpace: O(N)

Test Your Understanding

WHY can unhashable types (like Python lists) NOT be used as keys in a dictionary or set?

Prev: 3. Array Patterns: Two Pointers & Sliding Window Next: 5. Binary Search & Divide and Conquer