Hash Tables & Hash Maps — Complete Python Tutorial

The Story That Explains Hash Tables

A Hash Table (Hash Map) maps keys to values using a hash function to compute an array index directly. Average-case insert, delete, and lookup are all O(1) — constant time regardless of how many items are stored. Python's dict and set are hash tables under the hood.

How a Hash Table Works — The 4 Phases

Collision Strategies Side-by-Side

Load Factor & Rehashing

Load factor α = n / capacity — the fraction of buckets in use. As α grows, collision probability rises and average lookup time degrades. Python's dict rehashes (doubles capacity and reinserts all entries) when α exceeds roughly ⅔ (0.67).

Build a Hash Map from Scratch

We implement a minimal hash map using separate chaining. Each bucket holds a list of (key, value) pairs. Step through the animation to watch each line execute during put("name","Alice").

Python's dict, defaultdict & Counter

# ── 1. Core dict operations ───────────────────────────────
d = {}                                   # empty hash map — O(1)
d["name"] = "Alice"                     # insert / update — O(1) avg
d["age"]  = 30
print(d.get("name", "N/A"))             # safe lookup — no KeyError
print("age" in d)                       # membership — O(1)
del d["age"]                             # delete — O(1) avg
d.setdefault("score", 0)               # insert only if missing

# ── 2. defaultdict — auto-creates missing keys ────────────
from collections import defaultdict
groups = defaultdict(list)
words = ["apple", "ant", "banana", "bear", "cat"]
for w in words:
    groups[w[0]].append(w)              # group by first letter — no KeyError
print(dict(groups))

# ── 3. Counter — frequency hash map ──────────────────────
from collections import Counter
text = "hello world"
freq = Counter(text)                   # O(n) build
print(freq.most_common(3))             # top 3 items — O(n log k)
print(freq["l"])                        # O(1) count lookup

# ── Counter arithmetic ────────────────────────────────────
a = Counter(["a","b","a"])
b = Counter(["a","c"])
print(a + b)   # combine counts
print(a - b)   # subtract counts (drops zeros/negatives)

Time & Space Complexity Reference

Classic Hash Map Patterns

# ── Pattern 1: Two Sum — O(n) ─────────────────────────────
def two_sum(nums: list, target: int) -> tuple:
    seen = {}                            # key=number, val=index
    for i, x in enumerate(nums):
        complement = target - x         # what do we still need?
        if complement in seen:           # O(1) check
            return (seen[complement], i)  # found the pair!
        seen[x] = i                      # store for future iterations
    return (-1, -1)

# ── Pattern 2: Group Anagrams — O(n · k · log k) ─────────
from collections import defaultdict
def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = tuple(sorted(w))            # canonical anagram key
        groups[key].append(w)
    return list(groups.values())

# ── Pattern 3: Longest substring without repeating ────────
def length_of_longest_substring(s: str) -> int:
    last_seen = {}
    best = left = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1     # shrink window past duplicate
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

print(two_sum([2, 7, 11, 15], 9))
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
print(length_of_longest_substring("abcabcbb"))

Hash Map in Real Algorithms

# ── Subarray sum equals k — O(n) using prefix-sum map ────
def subarray_sum(nums, k):
    count     = 0
    prefix    = 0
    seen      = defaultdict(int)
    seen[0]   = 1                       # empty prefix
    for x in nums:
        prefix += x
        count  += seen[prefix - k]     # how many prior prefixes differ by k?
        seen[prefix] += 1
    return count

# ── LRU Cache — O(1) get & put — dict + doubly-linked list
from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity):
        self.cap   = capacity
        self.cache = OrderedDict()       # preserves insertion order

    def get(self, key):
        if key not in self.cache: return -1
        self.cache.move_to_end(key)     # mark as recently used
        return self.cache[key]

    def put(self, key, val):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = val
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False) # evict LRU (front)

# ── isomorphic strings — O(n) with two maps ──────────────
def is_isomorphic(s, t):
    s2t, t2s = {}, {}
    for a, b in zip(s, t):
        if s2t.get(a, b) != b or t2s.get(b, a) != a: return False
        s2t[a] = b; t2s[b] = a
    return True

print(subarray_sum([1,1,1], 2))
lru = LRUCache(2)
lru.put(1,1); lru.put(2,2); lru.put(3,3)
print(lru.get(1), lru.get(2))
print(is_isomorphic("egg", "add"), is_isomorphic("foo", "bar"))

Golden Rules