DSA Hash Tables

What Is a Hash Table?

Instead of scanning a list one element at a time, a hash table computes exactly where a value should live using a hash function, then jumps straight to that location. This is what makes dictionaries and sets in Python so fast even when they hold millions of entries.

How Hashing Works

A hash function accepts a key of any size (a string, a number, a tuple) and deterministically produces a fixed-size integer called a hash code. That integer is then reduced with the modulo operator against the table's current size to produce a bucket index. A good hash function distributes keys uniformly across buckets and is fast to compute, since it runs on every insert, lookup, and delete.

def simple_hash(key, table_size):
    total = sum(ord(char) for char in key)
    return total % table_size

print(simple_hash('apple', 10))   # e.g. 6
print(simple_hash('banana', 10))  # e.g. 3

Handling Collisions

Because many keys can hash to the same index, every hash table implementation needs a collision resolution strategy. The two dominant approaches are:

• Separate chaining - store multiple entries in the same bucket as a small list
• Open addressing - probe for the next free slot (linear, quadratic, or double hashing)
• Robin Hood hashing - redistribute entries to minimize variance in probe distance
• Resizing - grow the table and rehash all entries once the load factor gets too high

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

    def _hash(self, key):
        return hash(key) % self.size

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

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

table = HashTable()
table.put('name', 'Ada')
table.put('role', 'Engineer')
print(table.get('name'))   # Ada
print(table.get('role'))   # Engineer

print(hash('hello'))
print(hash(42))
print(hash((1, 2, 3)))

# Equal values always produce the same hash
print(hash('hello') == hash('hello'))  # True