Hash Table

A hash table maps keys to values via a hash function that converts each key to an array index. Average O(1) for insert, lookup, and delete; worst case O(n) when too many keys collide. Python's dict and set are hash tables.

Complexity

How it works

Allocate an array of m buckets. To insert (key, value): compute i = hash(key) % m, place the entry in bucket i. Resolve collisions by chaining (each bucket holds a linked list) or open addressing (probe to the next free slot). When the load factor exceeds a threshold (~0.75), grow the array and rehash everything.

Python implementation

# Python dict — already a hash table.
d = {}
d["alice"] = 30
d["bob"] = 25
print(d["alice"])      # 30 — O(1) average
print("alice" in d)    # True — O(1) average
del d["bob"]


# Hand-rolled hash table with separate chaining.
class HashTable:
    def __init__(self, capacity=16):
        self._buckets = [[] for _ in range(capacity)]
        self._size = 0

    def _bucket(self, key):
        return self._buckets[hash(key) % len(self._buckets)]

    def put(self, key, val):                # O(1) average
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, val)
                return
        bucket.append((key, val))
        self._size += 1
        if self._size > 0.75 * len(self._buckets):
            self._resize(len(self._buckets) * 2)

    def get(self, key):                     # O(1) average
        for k, v in self._bucket(key):
            if k == key:
                return v
        raise KeyError(key)

    def _resize(self, new_cap):
        old = self._buckets
        self._buckets = [[] for _ in range(new_cap)]
        self._size = 0
        for bucket in old:
            for k, v in bucket:
                self.put(k, v)


h = HashTable()
h.put("alice", 30); h.put("bob", 25)
print(h.get("alice"))   # 30

Trade-offs

• Average O(1) on every operation — the workhorse data structure of modern software.
• Worst case O(n) under hash flooding or a degenerate hash function.
• No order — iteration order is insertion order in CPython 3.7+ but not part of the abstract contract.
• For ordered lookups (range queries, sorted iteration), use a tree-based map instead.

← Back to Algorithms