Build a Hash Table from Scratch in Python

“Implement a HashMap” is one of the oldest interview prompts, and it is less about the code than about whether you understand why d[key] is fast. The short version: a hash function turns a key into a number, the number picks one of a fixed set of buckets, and you look only inside that bucket. Everything interesting happens when two keys land in the same bucket, and when the table fills up.

This guide builds a working hash table in Python from nothing, breaks it on purpose three different ways, and then builds the second major design, open addressing, to show the bug that catches almost everyone. Every output shown was produced by running the code, and both tables were compared against Python’s own dict on random sequences of inserts, lookups and deletes (500 runs for chaining, 400 for open addressing, no mismatches).

The three moving parts

A hash function maps a key to an integer. Python provides hash(key).
An index is that integer reduced to a bucket number: hash(key) % capacity.
A collision rule decides what to do when two different keys want the same bucket. Two classic answers are chaining (each bucket holds a small list) and open addressing (probe forward to the next free slot).

Add a fourth duty that people forget until the table gets slow: resizing, which keeps the buckets short as more keys arrive.

Version 1: separate chaining

Each bucket is a list of (key, value) pairs. Lookups hash the key, jump to the bucket and scan that short list. A key already present is overwritten rather than duplicated.

class HashTable:
    def __init__(self, capacity=8, max_load=0.75):
        self.capacity = capacity
        self.max_load = max_load
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]
        self.resizes = 0

    def _index(self, key):
        return hash(key) % self.capacity

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)       # overwrite
                return
        bucket.append((key, value))
        self.size += 1
        if self.size / self.capacity > self.max_load:
            self._resize(self.capacity * 2)

    def get(self, key, default=None):
        for k, v in self.buckets[self._index(key)]:
            if k == key:
                return v
        return default

    def delete(self, key):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.size -= 1
                return True
        return False

    def _resize(self, new_cap):
        old = self.buckets
        self.capacity = new_cap
        self.buckets = [[] for _ in range(new_cap)]
        self.size = 0
        self.resizes += 1
        for bucket in old:
            for k, v in bucket:
                self.put(k, v)

    def __len__(self):
        return self.size

    def __contains__(self, key):
        sentinel = object()
        return self.get(key, sentinel) is not sentinel

A quick session with six fruit names:

h.get('cherry')        # -> 2
h.get('zzz')           # -> None
h.get('zzz', -1)       # -> -1
len(h), 'banana' in h  # -> (6, True)
h.put('apple', 100)    # overwrite: h.get('apple') -> 100, len(h) still 6
h.delete('date')       # -> True, then False the second time; len(h) -> 5

Two details are worth copying into your own answer. __contains__ uses a private sentinel object rather than None, because None could be a legitimate stored value. And put checks for an existing key before appending, so the size never counts a key twice.

Why resizing exists, and why it rehashes everything

With 8 buckets and 800 keys, every bucket holds about 100 pairs, and your “constant time” lookup is a linear scan. The load factor (keys divided by buckets) measures that pressure. When it passes the limit, double the buckets.

You cannot just copy the old buckets across, because the index is hash % capacity. Change the capacity and the same key maps somewhere else, so every key has to be re-inserted. In the test, a fresh table with capacity 8 and a 0.75 limit grew to 16 buckets on the seventh insert (7/8 = 0.875), and after 50 integer keys it had grown four times to 128 buckets. A single resize costs O(n), but doubling means resizes get rarer as the table grows, so the average cost per insert is still O(1). That is the idea of amortised time, covered in the Big O guide.

Break it on purpose: a bad hash

Hashing is only as good as its spread. This key class always returns the same hash, so every key collides:

class BadKey:
    def __init__(self, v): self.v = v
    def __hash__(self): return 1
    def __eq__(self, o): return self.v == o.v

Inserting 3,000 well-behaved integer keys against 3,000 of these colliding keys:

3000 good keys:      longest chain 1,     0.0041 s
3000 colliding keys: longest chain 3000,  0.5548 s

Same code, same count, about 135 times slower, and the longest chain is the entire table. This is the reason the worst case of a hash table is O(n), and why a correct __hash__ matters: whatever __eq__ treats as equal must hash equally, and unequal objects should hash differently as often as possible.

Break it again: keys must not change

A key that can change after insertion would hash to a different bucket and become impossible to find. Python refuses the problem at the source by making mutable containers unhashable:

h.put([1, 2], 'x')
# TypeError: unhashable type: 'list'

Use a tuple, a string or a number instead. This is also why a dictionary is the standard tool in the Two Sum solution, where integers are perfect keys.

Break it a third way: do not depend on hash values

Python randomises string hashes per process for security. Running hash('apple') % 8 in three separate processes printed 6, 0 and 0. Bucket positions, and therefore the iteration order of a hand-built table, change between runs. Never write code or tests that assume a specific hash value.

Version 2: open addressing with linear probing

Instead of lists, store everything in two flat arrays. If the target slot is taken by another key, step to the next slot and try again. Probing keeps data compact and cache-friendly, but it needs a lower load factor (this version grows at 0.5) and it makes deletion tricky.

class ProbeTable:
    EMPTY = object()
    DELETED = object()          # tombstone

    def __init__(self, cap=8):
        self.cap = cap
        self.keys = [self.EMPTY] * cap
        self.vals = [None] * cap
        self.n = 0

    def _probe(self, key):
        i = hash(key) % self.cap
        while True:
            yield i
            i = (i + 1) % self.cap

    def put(self, key, val):
        if (self.n + 1) / self.cap > 0.5:
            self._grow()
        first_free = None
        for i in self._probe(key):
            k = self.keys[i]
            if k is self.EMPTY:
                idx = first_free if first_free is not None else i
                self.keys[idx], self.vals[idx] = key, val
                self.n += 1
                return
            if k is self.DELETED:
                if first_free is None:
                    first_free = i
            elif k == key:
                self.vals[i] = val
                return

    def get(self, key, default=None):
        for i in self._probe(key):
            k = self.keys[i]
            if k is self.EMPTY:
                return default
            if k is not self.DELETED and k == key:
                return self.vals[i]

    def delete(self, key):
        for i in self._probe(key):
            k = self.keys[i]
            if k is self.EMPTY:
                return False
            if k is not self.DELETED and k == key:
                self.keys[i] = self.DELETED
                self.vals[i] = None
                self.n -= 1
                return True

    def _grow(self):
        old_k, old_v = self.keys, self.vals
        self.cap *= 2
        self.keys = [self.EMPTY] * self.cap
        self.vals = [None] * self.cap
        self.n = 0
        for k, v in zip(old_k, old_v):
            if k is not self.EMPTY and k is not self.DELETED:
                self.put(k, v)

The deletion bug everyone writes first

The obvious delete sets the slot back to EMPTY. But a lookup stops the moment it meets an empty slot, assuming the key cannot be further along. Remove an entry in the middle of a probe run and you cut the chain for every key behind it. With capacity 8, the keys 0 and 8 both want slot 0. Insert 0, then 8 (which probes to slot 1), then delete 0:

after deleting 0, get(8) with EMPTY-marker delete: None   # wrong, 8 is still there
after deleting 0, get(8) with tombstone delete:    b      # correct

The tombstone says “something used to live here, keep probing”. Inserts may reuse a tombstone slot, which is what first_free does, but only after confirming the key is not already further along.

Using your own table

Swap HashTable into the classic Two Sum and it behaves like a dictionary:

def two_sum(nums, target):
    seen = HashTable()
    for i, x in enumerate(nums):
        j = seen.get(target - x)
        if j is not None:
            return [j, i]
        seen.put(x, i)

two_sum([2, 7, 11, 15], 9)   # -> [0, 1]
two_sum([3, 2, 4], 6)        # -> [1, 2]
two_sum([3, 3], 6)           # -> [0, 1]

Complexity at a glance

Operation	Average	Worst case	Why
put / get / delete	O(1)	O(n)	Worst case: every key in one bucket
Resize	O(n) once	O(n)	Every key is re-hashed
Insert, amortised	O(1)	O(1) average	Doubling makes resizes rare
Space	O(n)	O(n)	Buckets plus stored pairs

Follow-up questions to prepare for

Why a power-of-two capacity, or a prime one? Powers of two make the modulo a bit mask but need a well-mixed hash. Primes tolerate sloppy hashes. Python’s own dict uses powers of two with probing and a carefully mixed hash.
How would you shrink the table? Halve the capacity when the load falls well below a lower bound, with a gap between grow and shrink thresholds so it does not thrash.
How do you make an LRU cache? A hash table for lookup plus a doubly linked list for recency. The list half is in the linked list guide.
What else uses the same idea? Hash maps drive the sliding window and prefix sum patterns, and Python’s Counter and defaultdict are summarised in the cheat sheet.

A trie is the structure to reach for when keys are strings and you need prefixes, which a hash table cannot answer. See Trie in Python for that comparison.