Hashing and Advanced Linear Structures

reading · we frame, you read MIT or the canonical taught · we author, no canonical fits ↺ spirals back to earlier lessons

Course locked

Complete Trees and Priority Queues first.

This course unlocks once you've finished its prerequisite. Open prerequisite →

Prerequisites

Introduction to Algorithms and Complexity not yet

Linear Data Structures not yet

Complete prerequisites first to enroll.

reading · 35 min + ~212 min canonical

Hash Functions: What "Random" Means When It Has to Be Deterministic

A Ruby Hash gives you O(1) lookup. So does Python's dict, Java's HashMap, Go's map. They all do the same trick: take whatever key you give them — a string, a tuple, an arbitrary o…

primary UC Berkeley CS61B — Hashing sections

preview →

reading · 30 min + ~212 min canonical L1

Hash Tables: Buckets, Collisions, and the Load Factor

A hash table is two things glued together: an array of buckets, and a hash function that picks which bucket a key belongs to. Both pieces are simple. The combination earns you O(1…

primary UC Berkeley CS61B — Hashing sections

after L1 locked

reading · 30 min + ~212 min canonical L1

Open Addressing in Practice: Probing, Tombstones, and Why Robin Hood Hashing Won

The chained hash table from the last lesson works, but it has one cost that doesn't show up in the Big O analysis: it allocates a linked-list node per entry, and those nodes are s…

primary UC Berkeley CS61B — Hashing sections

after L2 locked

reading · 35 min + ~212 min canonical L1

Bloom Filters: Trading Certainty for Memory by 10x

Every data structure you've built so far has been exact: ask "does this set contain x?" and the answer is yes or no, always correct. A Bloom filter is the first data structure on …

primary UC Berkeley CS61B — Hashing sections

after L3 locked

reading · 30 min + ~212 min canonical L1

Skip Lists and Union-Find: Two Structures Worth Knowing

Two structures end this quarter's data-structures tour: skip lists (a probabilistic alternative to balanced trees, used by Redis for sorted sets) and union-find (a tiny structure …

primary UC Berkeley CS61B — Hashing sections

after L4 locked

exercise reading · 15 min L1

Exercises: Easy (Warm-up)

- [ ] Two Sum (#1) — NC/LC — Hash map for complement lookup in O(n) - [ ] Valid Anagram (#242) — NC/LC — Character frequency counting with hash - [ ] Contains Duplicate (#217) — N…

after L5 locked

exercise reading · 30 min L1

Exercises: Medium (Core)

- [ ] Group Anagrams (#49) — NC/LC — Hash map with sorted-string keys - [ ] Top K Frequent Elements (#347) — NC/LC — Hash map + bucket sort or heap - [ ] Longest Consecutive Seque…

after L6 locked

exercise reading · 45 min L1

Exercises: Hard (Stretch)

- [ ] LRU Cache (#146) — NC/LC — Hash map + doubly-linked list for O(1) get/put - [ ] Find the Duplicate Number (#287) — NC/LC — Floyd's cycle detection on array indices

after L7 locked

exercise reading · 60 min L1

Mini-Project

- [ ] Build a spell checker in Ruby — load a dictionary into a hash table, implement Levenshtein distance for suggestions, add a Bloom filter for fast "definitely not in dictionar…

after L8 locked

L10

project reading · 360 min L1

Project: Ruby Hash Reimplementation

Build MyHash in Ruby using open addressing with linear probing. Implement []=, [], delete, key?, each, keys, values, automatic resizing at 75% load factor. Benchmark against Ruby'…

after L9 locked

L11

project reading · 300 min L1

Project: Union-Find Maze Solver

Generate random mazes using Union-Find (Kruskal's algorithm for random spanning trees on a grid). Then solve the maze using BFS. Output the maze and solution path as ASCII art. In…

after L10 locked

L12

assessment reading · 70 min L1

Self-Assessment: Hashing and Advanced Linear Structures

- [ ] How does a hash table work? Explain hash functions, buckets, and collision resolution. - [ ] What is the difference between chaining and open addressing (linear probing)? - …

after L11 locked

L13

assessment reading · 60 min L1

Quarter 2 Gate Check: Core Data Structures

- [ ] Course 2.1 knowledge check passed - [ ] Course 2.2 knowledge check passed - [ ] Course 2.3 knowledge check passed - [ ] Database Index Engine capstone completed

after L12 locked

13 lessons. Read in order; spiral back when you need to. By the end you'll have used the core ideas twice — once on the abstract, once on something you'll meet at work next week.