Hash Tables

Hash tables provide lightning-fast key-value lookups with O(1) average time complexity. They are the engine behind dictionaries, maps, and associative arrays in almost every programming language.

Hash Table Concept

A hash table stores data in key-value pairs. A hash function takes a key and computes an index (a hash code) that determines where the value is stored in an internal array. When you look up a key, the same hash function is used to find its location directly.

Hash Functions

A good hash function should be:

• Deterministic: same key always produces the same hash code
• Fast to compute
• Uniformly distributed: minimizes collisions by spreading keys evenly
• Non-invertible: hard to reconstruct the key from its hash

def simple_hash(key, table_size):
    # Simple hash for string keys
    total = 0
    for ch in str(key):
        total += ord(ch)
    return total % table_size

Collision Resolution

Collisions happen when two different keys hash to the same index. Here are the main strategies:

1. Chaining (Separate Chaining)

Each bucket stores a linked list (or another collection) of key-value pairs. When a collision occurs, the new pair is appended to the list at that index.

class HashTableChaining:
    def __init__(self, capacity=10):
        self.capacity = capacity
        self.table = [[] for _ in range(capacity)]

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

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

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.table[idx]:
            if k == key:
                return v
        return None

    def remove(self, key):
        idx = self._hash(key)
        self.table[idx] = [(k, v) for k, v in self.table[idx] if k != key]

2. Open Addressing

When a collision occurs, probe for the next empty slot. Variants include:

• Linear probing: check slot + 1, + 2, + 3, ...
• Quadratic probing: check slot + 1², + 2², + 3², ...
• Double hashing: use a second hash function to determine the step size

class HashTableLinearProbing:
    def __init__(self, capacity=10):
        self.capacity = capacity
        self.keys = [None] * capacity
        self.values = [None] * capacity

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

    def put(self, key, value):
        idx = self._hash(key)
        while self.keys[idx] is not None:
            if self.keys[idx] == key:
                self.values[idx] = value
                return
            idx = (idx + 1) % self.capacity
        self.keys[idx] = key
        self.values[idx] = value

    def get(self, key):
        idx = self._hash(key)
        while self.keys[idx] is not None:
            if self.keys[idx] == key:
                return self.values[idx]
            idx = (idx + 1) % self.capacity
        return None

Load Factor and Resizing

The load factor is the ratio of stored entries to table capacity. When it exceeds a threshold (typically 0.75), the table is resized (usually doubled in capacity) and all entries are rehashed. This keeps operations fast at the cost of occasional O(n) resizing.

Hash Set vs Hash Map

• Hash Set: stores only keys (no values). Used to track membership (e.g., visited nodes, unique elements).
• Hash Map: stores key-value pairs. Used for lookups, caching, counting frequencies, and associative data.

Applications

• Database indexing
• Cache systems (memcached, Redis)
• Compilers and interpreters (symbol tables)
• Counting word frequencies
• Detecting duplicates
• Two-sum problem and other interview classics