Hash Tables - Learn Step by Step

🌟 Level 1: The Basics (Start Here!)

Level 1

What is a Hash Table? Think of it as a Restaurant Menu! 🍽️

Imagine you're at a restaurant. When you want to know the price of "Pizza", you don't read the entire menu from start to finish. You quickly find "Pizza" and see "$15" right next to it. That's exactly how a hash table works!

Menu Item

🍕

Pizza → $15

Menu Item

🍔

Burger → $12

Menu Item

🥗

Salad → $8

Menu Item

🍝

Pasta → $14

Key Points:

🔑 Each item has a key (dish name)
📦 Each key has a value (price)
⚡ Finding any item is instant (O(1) time)
🎯 No need to search through everything!

Your First Hash Table in Python 🐍

# Creating a hash table (dictionary in Python) is super easy!
restaurant_menu = {
    "Pizza": 15,     # Key: "Pizza", Value: 15
    "Burger": 12,    # Key: "Burger", Value: 12
    "Salad": 8,      # Key: "Salad", Value: 8
    "Pasta": 14      # Key: "Pasta", Value: 14
}

# Getting a price (accessing a value) - INSTANT!
pizza_price = restaurant_menu["Pizza"]   # Returns 15

# Adding a new item
restaurant_menu["Soup"] = 6   # Now we have soup!

# Checking if item exists
if "Pizza" in restaurant_menu:
    print("We have pizza!")
                                

How Does the Magic Work? The Hash Function! 🎩

A hash function is like a magical filing system that instantly tells you where to find something:

1

Input: You give it a key (like "Pizza")

2

Hash: It converts "Pizza" into a number (like 3)

3

Store/Retrieve: Uses that number as the storage spot

🎮 Try It Yourself: Build a Phone Book!

Enter names and phone numbers to build your hash table:

⚠️ Common Beginner Mistake: Not Handling Missing Keys

# ❌ WRONG - This will crash if key doesn't exist!
phone_book = {"Alice": "555-1234"}
number = phone_book["Bob"]   # KeyError!
                            

✅ The Right Way

# ✅ CORRECT - Use get() or check first
number = phone_book.get("Bob", "Not found")

# Or check if key exists
if "Bob" in phone_book:
    number = phone_book["Bob"]
                            

🤔 Why Should You Care About Hash Tables?

Hash Tables Are EVERYWHERE in Real Life!

🔐

Password Storage

Every website stores your username and (hashed) password in a hash table. When you log in, it instantly finds your account without searching through millions of users!

💳

Credit Card Verification

When you shop online, hash tables instantly verify if your card number is valid and check your account balance. No waiting!

📱

Your Phone's Contacts

When you type a name to call someone, your phone uses a hash table to instantly find their number from thousands of contacts!

🎮

Game Inventories

Video games use hash tables for your inventory. That's why checking if you have an item is instant, even with hundreds of items!

🛒

Online Shopping Carts

Amazon uses hash tables to track millions of shopping carts. Each session ID maps to your cart contents instantly!

🔍

Google Search Suggestions

As you type, Google uses hash tables to instantly find and suggest popular searches. That's why autocomplete is so fast!

💬

Spell Checkers

Your phone's spell checker uses a hash table containing hundreds of thousands of words. It instantly knows if a word is spelled correctly!

🌐

URL Shorteners

Services like bit.ly use hash tables to map short codes to long URLs. Click a short link → instantly get the full URL!

🏦

Bank Account Lookups

Banks use hash tables to instantly access your account with your account number. No searching through millions of accounts!

📊

Database Indexes

Every database uses hash tables for indexes. That's why finding a user by ID is instant, even with billions of records!

💡 The Big Idea

Hash tables give us superpowers: Instead of searching through everything (which could take forever), we can find anything instantly! It's like having a magic index that tells you exactly where everything is.

🎨 Level 2: Common Patterns

Intermediate

Pattern 1: Collision Resolution (When Two Keys Want the Same Spot)

Imagine two cars trying to park in the same spot. We need a solution!

Method 1: Chaining (Make a Line)

Bucket 0

🔗

John → 555-1111

Jane → 555-2222

Bucket 1

📱

Bob → 555-3333

Bucket 2

📞

Alice → 555-4444

Method 2: Open Addressing (Find Next Available Spot)

If your parking spot is taken, just check the next one!

Pattern 2: Two Sum Problem (Classic Interview Question)

Using Hash Table for Two Sum 🎯

def two_sum(nums, target):
    # Hash table to store: number → index
    seen = {}
    
    for i, num in enumerate(nums):
        # What number do we need?
        complement = target - num
        
        # Have we seen it before?
        if complement in seen:
            return [seen[complement], i]
        
        # Store current number and its index
        seen[num] = i
    
    return []

# Example: Find two numbers that add to 9
nums = [2, 7, 11, 15]
result = two_sum(nums, 9)  # Returns [0, 1] because nums[0] + nums[1] = 9
                                

Pattern 3: Frequency Counter

Count Character Frequency

💪 Level 3: Practice Problems

Practice Time!

Problem 1: Check for Duplicates

Given an array, check if it contains any duplicates.

Think About It! 🤔

How can a hash table help us track what we've seen?

Show Solution

def contains_duplicate(nums):
    seen = set()  # Hash set for O(1) lookups
    
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    
    return False
                                

Problem 2: Group Anagrams

Group words that are anagrams of each other.

Hint 💡

What if we sort each word and use that as a key?

🚀 Level 4: Advanced Concepts

Advanced

Load Factor and Rehashing

When a hash table gets too full (usually 75% full), it needs to resize!

1

Monitor: Track how full the table is (load factor)

2

Resize: Create a new, larger table (usually 2x size)

3

Rehash: Move all items to new table with new positions

Custom Hash Functions

Building Your Own Hash Function

def simple_hash(key, table_size):
    # Convert string to number
    hash_value = 0
    for char in key:
        hash_value += ord(char)
    
    # Use modulo to fit in table
    return hash_value % table_size

# Example
index = simple_hash("Pizza", 10)  # Returns index 0-9
                                

📖 Quick Reference

Time Complexity

Operation	Average Case	Worst Case	Plain English
Insert	O(1)	O(n)	⚡ Usually instant
Search	O(1)	O(n)	⚡ Usually instant
Delete	O(1)	O(n)	⚡ Usually instant

When to Use Hash Tables

✅ Use When:

Need fast lookups by key
Counting/frequency problems
Caching/memoization
Removing duplicates
Grouping items by property

❌ Don't Use When:

Need ordered data
Need to find min/max frequently
Keys are sequential integers (use array)
Memory is very limited

Common Hash Table Patterns

🎯 Two Pointers + Hash: Two sum, three sum problems
📊 Frequency Counter: Anagrams, duplicates, most common
🗺️ Mapping: Group by property, index mapping
💾 Caching: Store computed results (memoization)
🔍 Lookup Table: Fast existence checks