14. Hash Tables — Dictionaries Under the Hood

What problem does this solve? Arrays and lists find elements by index in O(1) time. But what if you want to find an element by its value (not position)? A hash table maps keys to values, giving O(1) average-time lookup, insert, and delete.

1. The Hash Table Concept

Mental Model

2. Hash Functions

Requirements

1. Deterministic: Same key always produces the same hash
2. Efficient: O(1) to compute
3. Uniform distribution: Keys spread evenly across buckets

Common Hash Functions

python
Run Inline
# runnable
def hash_mod(key, table_size):
    """Simple modulo hash (for integer keys)."""
    return key % table_size
def hash_string(s, table_size):
    """Polynomial hash for strings."""
    h = 0
    for ch in s:
        h = (h * 31 + ord(ch)) % table_size
    return h
# Python's built-in hash
print(hash("apple"))        # Some large integer
print(hash(42))             # 42 (for small ints, hash = self)
print(hash("apple") % 10)   # Modulo to get an index

3. Collision Resolution — Chaining

Mental Model

Implementation

python
Run Inline
# runnable
class HashTableChaining:
    """Hash table with separate chaining."""
    def __init__(self, capacity=10):
        self._table = [[] for _ in range(capacity)]
        self._capacity = capacity
        self._size = 0
    def _hash(self, key):
        """Compute hash index for key."""
        return hash(key) % self._capacity
    def __setitem__(self, key, value):
        """Insert key-value pair. O(1) average."""
        idx = self._hash(key)
        bucket = self._table[idx]
        # Update existing key
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        # Insert new key
        bucket.append((key, value))
        self._size += 1
        # Resize if load factor > 0.75
        if self._size > 0.75 * self._capacity:
            self._resize(2 * self._capacity)
    def __getitem__(self, key):
        """Get value for key. O(1) average."""
        idx = self._hash(key)
        for k, v in self._table[idx]:
            if k == key:
                return v
        raise KeyError(key)
    def __delitem__(self, key):
        """Delete key-value pair. O(1) average."""
        idx = self._hash(key)
        bucket = self._table[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self._size -= 1
                return
        raise KeyError(key)
    def _resize(self, new_capacity):
        """Resize and rehash all entries."""
        old_table = self._table
        self._table = [[] for _ in range(new_capacity)]
        self._capacity = new_capacity
        self._size = 0
        for bucket in old_table:
            for k, v in bucket:
                self[k] = v
# Test
ht = HashTableChaining(4)
ht["apple"] = "a fruit"
ht["banana"] = "yellow"
ht["cherry"] = "red"
print(ht["banana"])       # yellow
ht["banana"] = "ripe"
print(ht["banana"])       # ripe
del ht["apple"]
# print(ht["apple"])      # KeyError

4. Collision Resolution — Open Addressing (Linear Probing)

Mental Model

python
Run Inline
# runnable
class HashTableLinearProbing:
    """Hash table with linear probing."""
    def __init__(self, capacity=10):
        self._keys = [None] * capacity
        self._values = [None] * capacity
        self._capacity = capacity
        self._size = 0
        self._DELETED = object()  # Tombstone marker
    def _hash(self, key):
        return hash(key) % self._capacity
    def __setitem__(self, key, value):
        idx = self._hash(key)
        original_idx = idx
        while self._keys[idx] is not None and self._keys[idx] is not self._DELETED:
            if self._keys[idx] == key:
                self._values[idx] = value  # Update existing
                return
            idx = (idx + 1) % self._capacity
            if idx == original_idx:
                raise Exception("Table full")
        self._keys[idx] = key
        self._values[idx] = value
        self._size += 1
        if self._size > 0.7 * self._capacity:
            self._resize(2 * self._capacity)
    def __getitem__(self, key):
        idx = self._hash(key)
        original_idx = idx
        while self._keys[idx] is not None:
            if self._keys[idx] == key:
                return self._values[idx]
            idx = (idx + 1) % self._capacity
            if idx == original_idx:
                break
        raise KeyError(key)
    def __delitem__(self, key):
        idx = self._hash(key)
        original_idx = idx
        while self._keys[idx] is not None:
            if self._keys[idx] == key:
                self._keys[idx] = self._DELETED  # Tombstone
                self._values[idx] = None
                self._size -= 1
                return
            idx = (idx + 1) % self._capacity
            if idx == original_idx:
                break
        raise KeyError(key)
    def _resize(self, new_capacity):
        old_keys, old_values = self._keys, self._values
        self._keys = [None] * new_capacity
        self._values = [None] * new_capacity
        self._capacity = new_capacity
        self._size = 0
        for k, v in zip(old_keys, old_values):
            if k is not None and k is not self._DELETED:
                self[k] = v
# Test
ht = HashTableLinearProbing(4)
ht["apple"] = "fruit"
ht["banana"] = "yellow"
ht["cherry"] = "red"
print(ht["banana"])

Linear Probing Trace

pseudo
Table size = 5. Insert: 15 (hash=0), 25 (hash=0), 35 (hash=0)
Insert 15: hash=0 → keys[0] = 15
Insert 25: hash=0 → keys[0]=15 (occupied), try keys[1] = 25
Insert 35: hash=0 → keys[0]=15, keys[1]=25, keys[2] = 35
Search 35: hash=0 → keys[0]=15≠35, keys[1]=25≠35, keys[2]=35 ✅

5. Load Factor & Performance

6. Comparison

Practice Questions

Answers

A1. Chaining: 10→3, 22→1, 31→3, 4→4, 15→1, 28→0. Linear probing would skip occupied slots.

A2. α = 1000/2000 = 0.5.

A3. Prime table size reduces clustering with certain hash functions, but for chaining any size works. With linear probing, prime size reduces primary clustering.

A4. A tombstone marks a deleted slot in open addressing so search doesn't stop early. Without tombstones, deleting an entry would break the search chain for subsequent entries.

A5. Chaining: table (m pointers) + n nodes (each: key + value + next pointer). Linear probing: just the table (keys + values arrays). Chaining uses more memory due to node overhead.

A6. Map the letter prefix to a number and combine with the digits: h(roll) = (26²·CS_value + 26·year_value + digits) % table_size.

A7. Resizing doubles capacity and rehashes all entries. This is O(n) but happens rarely (amortized O(1)). Python's dict resizing is highly optimized in C.

A8. When all keys hash to the same bucket — O(n) for all operations. With good hash functions, this is astronomically unlikely. Join Discord Previous13. Dynamic Arrays & Amortized AnalysisNext15. Binary Trees & Traversals