Hash Table Patterns

🗄️ Hash Tables: Your Magic Treasure Chest!

Imagine you have a magical treasure chest with special pockets. Each pocket has a secret label. When you want to find your toy car, you don’t search through everything—you just say the magic word “car” and the chest opens the exact pocket!

That’s what a Hash Table does. It’s a super-fast way to store and find things!

📦 Hash Map Fundamentals

What is a Hash Map?

A Hash Map is like a dictionary where every word has its meaning right next to it.

Think of it this way:

• You have labeled boxes
• Each label is a “key” (like your friend’s name)
• Inside the box is a “value” (like their phone number)

# Creating a phone book
phone_book = {}
phone_book["Emma"] = "555-1234"
phone_book["Noah"] = "555-5678"

# Finding Emma's number
print(phone_book["Emma"])
# Output: 555-1234

Why is it fast? Instead of looking through every name, the hash map uses a magic formula to jump directly to Emma’s box!

graph TD
    A["Key: Emma"] --> B["Hash Function"]
    B --> C["Magic Number: 3"]
    C --> D["Go to Box 3"]
    D --> E["Find: 555-1234"]

🎯 Hash Set Fundamentals

What is a Hash Set?

A Hash Set is like a guest list at a party. You only care if someone is on the list or not—no extra info needed!

Key difference from Hash Map:

• Hash Map: stores key + value (name + phone)
• Hash Set: stores only the key (just names)

# Creating a guest list
guests = set()
guests.add("Emma")
guests.add("Noah")
guests.add("Emma")  # Emma again!

print(guests)
# Output: {'Emma', 'Noah'}
# Emma appears only once!

Super power: Sets automatically remove duplicates!

# Quick way to find unique items
numbers = [1, 2, 2, 3, 3, 3]
unique = set(numbers)
print(unique)
# Output: {1, 2, 3}

💥 Hash Collision Resolution

What happens when two keys get the same box?

Sometimes, two different keys get the same “magic number.” This is called a collision—like two friends trying to sit in the same chair!

Example:

• “cat” might hash to box 5
• “act” might also hash to box 5

How do we fix it?

Method 1: Chaining (Most Common) Each box holds a small list. Multiple items can share one box!

graph TD
    A["Box 5"] --> B["List"]
    B --> C["cat → meow"]
    B --> D["act → perform"]

Method 2: Open Addressing If box 5 is full, check box 6, then box 7, until you find an empty one!

# Python handles collisions for you!
# But here's how chaining works:
data = {}
data["cat"] = "meow"
data["act"] = "perform"
# Both work perfectly!

🎯 Two Sum Pattern

The Classic Problem

Question: Find two numbers that add up to a target.

The slow way: Check every pair. If you have 100 numbers, that’s 4,950 checks!

The smart way: Use a hash map to remember what you’ve seen!

How it works:

def two_sum(nums, target):
    seen = {}  # Our memory box

    for i, num in enumerate(nums):
        need = target - num

        if need in seen:
            return [seen[need], i]

        seen[num] = i

    return []

# Example
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))
# Output: [0, 1]
# Because 2 + 7 = 9

graph TD
    A["See 2"] --> B["Need 7 to make 9"]
    B --> C["Is 7 in memory? No"]
    C --> D["Save 2 at index 0"]
    D --> E["See 7"]
    E --> F["Need 2 to make 9"]
    F --> G["Is 2 in memory? YES!"]
    G --> H["Return indices 0 and 1"]

📊 Frequency Counting

Counting How Often Things Appear

Problem: How many times does each letter appear in a word?

Solution: Use a hash map as a counter!

def count_letters(word):
    counter = {}

    for letter in word:
        if letter in counter:
            counter[letter] += 1
        else:
            counter[letter] = 1

    return counter

print(count_letters("banana"))
# Output: {'b': 1, 'a': 3, 'n': 2}

Even easier with Python:

from collections import Counter

word = "banana"
print(Counter(word))
# Output: Counter({'a': 3, 'n': 2, 'b': 1})

Real-world uses:

• 📝 Finding most common words in a book
• 🎵 Finding your most-played song
• 🛒 Finding best-selling products

🗂️ Grouping by Key

Putting Similar Things Together

Problem: Group anagrams (words with same letters).

Example: “eat”, “tea”, “ate” all have the same letters!

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)

    for word in words:
        # Sort letters to make a key
        key = ''.join(sorted(word))
        groups[key].append(word)

    return list(groups.values())

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(words))
# Output: [['eat', 'tea', 'ate'],
#          ['tan', 'nat'],
#          ['bat']]

graph TD
    A["eat → aet"] --> D["Group aet"]
    B["tea → aet"] --> D
    C["ate → aet"] --> D
    E["tan → ant"] --> F["Group ant"]
    G["nat → ant"] --> F
    H["bat → abt"] --> I["Group abt"]

The trick: Create a “signature” for each group. Items with the same signature go together!

🎯 Subarray Sum Equals K

Finding Hidden Sums

Problem: How many continuous chunks of numbers add up to K?

Example: In [1, 2, 3] with K=3:

• [1, 2] = 3 ✓
• [3] = 3 ✓
• Answer: 2 subarrays

The Brilliant Trick: Prefix Sums!

def subarray_sum(nums, k):
    count = 0
    running_sum = 0
    sum_count = {0: 1}  # Key insight!

    for num in nums:
        running_sum += num

        # If (sum - k) seen before,
        # we found subarrays!
        if running_sum - k in sum_count:
            count += sum_count[running_sum - k]

        # Remember this sum
        if running_sum in sum_count:
            sum_count[running_sum] += 1
        else:
            sum_count[running_sum] = 1

    return count

nums = [1, 1, 1]
k = 2
print(subarray_sum(nums, k))
# Output: 2
# [1,1] starting at 0 and [1,1] starting at 1

Why does this work?

If you’re at position X with total sum S, and you’ve seen sum (S-K) before at position Y, then the numbers between Y and X add up to exactly K!

graph TD
    A["Sum at Y = S-K"] --> B["Sum at X = S"]
    B --> C["X minus Y = K"]
    C --> D["Found a subarray!"]

🌟 Summary: Your Hash Table Toolkit

🚀 You Did It!

You now understand how hash tables work! They’re like your brain’s super-fast filing system:

1. Hash Maps = Your personal dictionary
2. Hash Sets = Your unique collection
3. Collisions = Traffic jams with solutions
4. Two Sum = The classic “find the pair” trick
5. Frequency Counting = Tallying like a pro
6. Grouping = Organizing your closet
7. Subarray Sum = Finding hidden patterns

Remember: Hash tables turn slow searches into instant lookups. That’s their superpower! 🦸‍♂️