6. Hash Maps & Sets

How a Hash Map Works

A hash map (Python dict) uses a hash function to convert a key into an array index where the value is stored. This enables $O(1)$ average-case lookup — far faster than searching a sorted list.

Analogy: A hotel with room numbers. Instead of checking every room to find "Alice's room," you have a front desk that instantly tells you the room number — that's hashing.

---

6.1 Frequency Counting

The most common use of hash maps in real code.

# --- Count word frequencies ---
def word_frequency(text: str) -> dict[str, int]:
    freq: dict[str, int] = {}
    for word in text.lower().split():
        word = word.strip(".,!?")
        freq[word] = freq.get(word, 0) + 1
    return freq

text = "the cat sat on the mat the cat"
print(word_frequency(text))
# {'the': 3, 'cat': 2, 'sat': 1, 'on': 1, 'mat': 1}

# --- Same thing with Counter ---
from collections import Counter
print(Counter(text.split()))

# --- Check if two strings are anagrams ---
def is_anagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

print(is_anagram("listen", "silent"))   # True
print(is_anagram("hello", "world"))     # False

---

6.2 Caching / Memoization with Dicts

# --- Manual function result cache ---
_cache: dict[int, int] = {}

def fibonacci(n: int) -> int:
    if n <= 1:
        return n
    if n in _cache:
        return _cache[n]     # O(1) lookup instead of recomputing
    result = fibonacci(n - 1) + fibonacci(n - 2)
    _cache[n] = result
    return result

# --- Python's built-in cache decorator (preferred) ---
from functools import cache

@cache
def fibonacci_cached(n: int) -> int:
    if n <= 1:
        return n
    return fibonacci_cached(n - 1) + fibonacci_cached(n - 2)

---

6.3 Sets for Deduplication & Fast Membership

# --- Remove duplicates while preserving order ---
def unique_ordered(items: list) -> list:
    seen = set()
    result = []
    for item in items:
        if item not in seen:
            seen.add(item)
            result.append(item)
    return result

print(unique_ordered([3, 1, 4, 1, 5, 9, 2, 6, 5, 3]))
# [3, 1, 4, 5, 9, 2, 6]

# --- Two Sum (classic interview problem) ---
# "Find two numbers that add up to target."
def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}    # value → index
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i
    return []

print(two_sum([2, 7, 11, 15], 9))   # [0, 1] — nums[0]+nums[1] = 9

# --- Find common elements between two lists efficiently ---
def common_elements(a: list, b: list) -> list:
    return list(set(a) & set(b))   # O(n+m) vs O(n*m) with nested loop

print(common_elements([1, 2, 3, 4], [3, 4, 5, 6]))   # [3, 4]

---

6.4 Grouping with defaultdict

from collections import defaultdict

# --- Group people by their department ---
employees = [
    ("Alice", "Engineering"),
    ("Bob", "Marketing"),
    ("Carol", "Engineering"),
    ("Dave", "Marketing"),
    ("Eve", "Engineering"),
]

by_dept: dict[str, list[str]] = defaultdict(list)
for name, dept in employees:
    by_dept[dept].append(name)

print(dict(by_dept))
# {'Engineering': ['Alice', 'Carol', 'Eve'], 'Marketing': ['Bob', 'Dave']}

# --- Group anagrams ---
def group_anagrams(words: list[str]) -> list[list[str]]:
    groups: dict[tuple, list] = defaultdict(list)
    for word in words:
        key = tuple(sorted(word))   # sorted letters as key
        groups[key].append(word)
    return list(groups.values())

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

---