🗺️ Graphs & Hashing: The City Map & Magic Locker Adventure
Imagine you’re the mayor of a tiny town. You need two superpowers: a map to show how everything connects, and magic lockers that instantly find anything you put inside. That’s Graphs and Hashing!
🏙️ Part 1: Graph Fundamentals — Your Town Map
What is a Graph?
Think of a graph like a connect-the-dots puzzle. You have:
- Dots (we call them nodes or vertices)
- Lines connecting them (we call them edges)
Simple Example:
Your house -------- School
| |
| |
Park ----------- Store
That’s a graph! Four places (nodes) connected by roads (edges).
Real Life:
- 🗺️ Google Maps showing roads between cities = Graph
- 👥 Facebook showing who’s friends with who = Graph
- ✈️ Flight routes between airports = Graph
📚 Graph Terminology — Learning the Words
Like learning a new game, you need to know the special words:
| Term | What It Means | Example |
|---|---|---|
| Node/Vertex | A dot (a thing) | Your house, a city, a person |
| Edge | A line (a connection) | A road, a friendship, a wire |
| Neighbor | Nodes connected by an edge | Houses next door to each other |
| Degree | How many edges touch a node | A popular person has high degree |
| Path | A walk from one node to another | Walking from home → park → school |
| Cycle | A path that ends where it started | Walking in a complete circle |
Picture it:
graph TD A["🏠 Home"] --> B["📚 School"] A --> C["🌳 Park"] B --> D["🏪 Store"] C --> D
Home has degree 2 (two roads going out). The path Home → Park → Store → School → Home is a cycle!
🗂️ Graph Representations — How Computers Remember Maps
A computer can’t draw pictures. It needs to store the map in numbers. There are two main ways:
1️⃣ Adjacency List (The Neighbor List)
Like a phone book! Each place lists its neighbors.
Home: [School, Park]
School: [Home, Store]
Park: [Home, Store]
Store: [School, Park]
✅ Good for: Most graphs (saves memory) 📦 Space: O(Nodes + Edges)
2️⃣ Adjacency Matrix (The Big Chart)
A table where ✓ means “connected” and ✗ means “not connected.”
Home School Park Store
Home ✗ ✓ ✓ ✗
School ✓ ✗ ✗ ✓
Park ✓ ✗ ✗ ✓
Store ✗ ✓ ✓ ✗
✅ Good for: Quickly checking “Are A and B connected?” 📦 Space: O(Nodes × Nodes)
➡️ Directed vs Undirected Graphs
Undirected Graph (Two-Way Streets)
If you can walk from Home to School, you can walk back. The connection goes both ways.
graph LR A["Home"] --- B["School"]
Example: Friendships on Facebook (if you’re my friend, I’m your friend)
Directed Graph (One-Way Streets)
Some roads only go one direction! We use arrows to show which way.
graph LR A["You"] --> B["Celebrity"]
Example: Following on Twitter (you can follow a celebrity, but they might not follow you back!)
⚖️ Weighted Graphs — Roads Have Distances
What if some roads are longer than others? We add weights (numbers) to edges!
graph LR A["Home"] -->|5 km| B["School"] A -->|2 km| C["Park"] B -->|8 km| D["Airport"] C -->|3 km| D
Why it matters:
- Home → School → Airport = 5 + 8 = 13 km
- Home → Park → Airport = 2 + 3 = 5 km ← Shorter!
Real Life: GPS finding the fastest route considers traffic (weights)!
🔐 Part 2: Hash Tables — The Magic Locker Room
What is a Hash Table?
Imagine a locker room with 10 lockers. You want to store your backpack instantly without checking every locker.
The Magic: A special spell (hash function) tells you EXACTLY which locker to use based on your name!
"Alice" → Spell → Locker 3
"Bob" → Spell → Locker 7
Now finding Alice’s stuff? Instant! Just use the spell again: “Alice” → Locker 3. Open it!
Real Life:
- 📖 Dictionaries (word → definition)
- 📧 Email contacts (name → email address)
- 🔑 Passwords (username → encrypted password)
🪄 Hash Functions — The Magic Spell
A hash function takes ANY input and gives back a number (locker number).
Simple Example — Adding Letter Positions:
"CAT" → C(3) + A(1) + T(20) = 24
If we have 10 lockers: 24 % 10 = Locker 4
Good Hash Function Rules:
| Rule | Why? |
|---|---|
| Fast | Computing the locker should be instant |
| Consistent | Same input ALWAYS gives same output |
| Spread out | Different inputs should go to different lockers |
Bad hash function: Always returns 1 (everyone fights for locker 1!)
Good hash function: Spreads items evenly across all lockers.
💥 Hash Collisions — Two People, One Locker!
Uh oh! What if the spell sends TWO people to the SAME locker?
"Alice" → Locker 3
"Amy" → Locker 3 ← COLLISION!
Solution 1: Chaining (Locker has a List)
Put a linked list in each locker. Both Alice and Amy share locker 3.
Locker 3: [Alice's bag] → [Amy's bag]
Solution 2: Open Addressing (Find Next Empty)
If locker 3 is taken, try locker 4, then 5…
"Alice" → Locker 3 ✓
"Amy" → Locker 3 ✗ full → Locker 4 ✓
Solution 3: Double Hashing (Second Spell)
Use a SECOND hash function to calculate how many lockers to skip.
"Amy" → First spell says 3 (full!)
→ Second spell says "skip 2"
→ Try locker 5 ✓
📦 Sets and Maps — Special Collections
Set: A Bag of Unique Items
A Set is like a bag where each toy appears only ONCE.
myToys = {car, doll, ball, car} ← car appears twice!
After Set magic: {car, doll, ball} ← only one car!
Uses:
- Removing duplicates from a list
- Checking if something exists (membership test)
- Finding common items between two groups
Map (Dictionary): Key → Value Pairs
A Map is like a phonebook: every name (key) has one phone number (value).
phoneBook = {
"Mom": "555-1234",
"Dad": "555-5678",
"Pizza": "555-0000"
}
Lookup: “What’s Mom’s number?” → Instant answer: “555-1234”
Note: Sets use hash tables (just keys, no values). Maps use hash tables too (keys + values)!
🤝 Union-Find — The Friend Groups Tracker
The Problem
You have 100 students. They keep making friends. You need to answer:
“Are Alex and Zoe in the same friend group?”
Checking every friendship would be slow!
The Solution: Union-Find (Disjoint Set)
Think of each friend group having a team captain.
Two Operations:
- Find(person): Who’s your team captain?
- Union(person1, person2): Merge two teams!
Example:
Start: Everyone is their own captain
[A] [B] [C] [D] [E]
Union(A, B): A becomes captain of B
[A-B] [C] [D] [E]
Union(C, D): C becomes captain of D
[A-B] [C-D] [E]
Union(B, D): Merge teams! A becomes everyone's captain
[A-B-C-D] [E]
Find(D) = A (captain)
Find(E) = E (still alone)
The Superpower: Path Compression
When finding the captain, make everyone point directly to the captain!
graph TD subgraph Before A1["A"] --> B1["B"] --> C1["C"] --> D1["D"] end subgraph After Find D A2["A"] --> D2["D"] B2["B"] --> D2 C2["C"] --> D2 end
Now future lookups are super fast!
Real Life Uses:
- 🌐 Detecting if two computers are on the same network
- 🖼️ Image processing (grouping similar pixels)
- 🧩 Solving maze connections
🎯 Quick Summary
| Concept | One-Line Explanation |
|---|---|
| Graph | Dots connected by lines |
| Vertex/Node | A dot (thing) |
| Edge | A line (connection) |
| Directed | One-way arrows |
| Undirected | Two-way streets |
| Weighted | Edges have numbers (distance, cost) |
| Adjacency List | Each node lists its neighbors |
| Adjacency Matrix | A table showing all connections |
| Hash Table | Magic lockers with instant lookup |
| Hash Function | The spell that picks the locker |
| Collision | Two items want the same locker |
| Chaining | Fix collision with lists in lockers |
| Open Addressing | Fix collision by finding next empty |
| Set | Bag of unique items only |
| Map | Key-value phonebook |
| Union-Find | Track which things are in the same group |
🚀 You Did It!
You now understand:
- ✅ How to represent connections (Graphs)
- ✅ Two ways computers store graphs (List vs Matrix)
- ✅ One-way vs two-way connections
- ✅ Roads with distances (Weighted graphs)
- ✅ Instant lookup magic (Hash tables)
- ✅ What happens when two items collide
- ✅ Sets (unique items) and Maps (key-value)
- ✅ Finding who’s in the same group (Union-Find)
You’re ready to build maps, create fast lookups, and track connections like a pro! 🎉