Why Should You Care About Hash Tables?
Hash Tables Are EVERYWHERE in Real Life!
They 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.
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 and 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 Basics: What is a Hash Table?
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!
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:
Input: You give it a key (like "Pizza")
Hash: It converts "Pizza" into a number (like 3)
Store/Retrieve: Uses that number as the storage spot
Try It Yourself: Build a Phone Book!
Common Beginner Mistake: Not Handling Missing Keys
Accessing a key that doesn't exist will crash your program!
# ✘ WRONG - This will crash if key doesn't exist!
phone_book = {"Alice": "555-1234"}
number = phone_book["Bob"] # KeyError!
# ✔ 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"]Common Patterns
Pattern 1: Collision Resolution
When two keys want the same spot - imagine two cars trying to park in the same space. We need a solution!
Method 1: Chaining (Make a Line)
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)
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] = 9Pattern 3: Frequency Counter
Practice Problems
Easy Problem 1: Check for Duplicates
Given an array, check if it contains any duplicates. How can a hash table help us track what we've seen?
Use a hash set. For each element, check if it's already in the set before adding it.
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 FalseMedium Problem 2: Group Anagrams
Group words that are anagrams of each other.
What if we sort each word and use that as a key? All anagrams will have the same sorted form.
from collections import defaultdict
def group_anagrams(words):
groups = defaultdict(list)
for word in words:
key = "".join(sorted(word))
groups[key].append(word)
return list(groups.values())
# Example
words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(words))
# [["eat","tea","ate"], ["tan","nat"], ["bat"]]Advanced: Load Factor and Rehashing
When a hash table gets too full (usually 75% full), it needs to resize!
Monitor: Track how full the table is (load factor)
Resize: Create a new, larger table (usually 2x size)
Rehash: Move all items to new table with new positions
Custom Hash Functions
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-9Quick Reference
| Operation | Average Case | Worst Case | Notes |
|---|---|---|---|
| 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
Need fast lookups by key, counting/frequency problems, caching/memoization, removing duplicates, grouping items by property.
When NOT to Use
Need ordered data, need to find min/max frequently, keys are sequential integers (use array), memory is very limited.
Common Patterns
Two Pointers + Hash (two sum, three sum), Frequency Counter (anagrams, duplicates), Mapping (group by property), Caching (memoization), Lookup Table (existence checks).