Python Program to Implement a Hash Table from Scratch

A hash table (or hash map) is the data structure behind Python's own dict — it gives average O(1) insert, lookup, and delete by converting a key into an array index using a hash function. Understanding how one works under the hood is a common interview topic and genuinely useful once you need a custom key-value store with different collision behavior than the built-in dict.

The two things any hash table needs are a hash function that maps a key to a bucket index, and a strategy for handling collisions — when two different keys hash to the same bucket. Here we use separate chaining: each bucket holds a small list of (key, value) pairs, so a collision just means appending to that bucket's list instead of overwriting anything.

Python Program to Implement a Hash Table from Scratch

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

    def _hash(self, key):
        # Convert the key into a bucket index
        return hash(key) % self.size

    def insert(self, key, value):
        bucket = self.buckets[self._hash(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # update existing key
                return
        bucket.append((key, value))

    def get(self, key):
        bucket = self.buckets[self._hash(key)]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)

    def delete(self, key):
        bucket = self.buckets[self._hash(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                return
        raise KeyError(key)


ht = HashTable()
ht.insert("name", "Alice")
ht.insert("age", 30)
ht.insert("city", "Paris")

print(ht.get("name"))
print(ht.get("age"))

ht.delete("age")
try:
    ht.get("age")
except KeyError:
    print("age was deleted")

Output:

Alice
30
age was deleted

Each bucket is a small Python list, so looking inside one is just iterating over a list of the (usually one or two) pairs stored there. With a good hash function and enough buckets, each bucket stays small and insert/get/delete all average O(1) — the real dict in CPython works on this same principle, with open addressing instead of chaining and a lot of low-level optimization. If a bucket grows too large (many collisions), performance degrades toward O(n) for that bucket, which is why production hash tables automatically resize and rehash as they fill up.