A hash table maps keys to values using a computed index, enabling fast lookup, insertion, and deletion. Understanding arrays and linked lists is essential before working with hash tables.

Core Mechanism

An array serves as the underlying storage, where each slot—called a bucket—holds a key-value pair. A hash function processes the key, and the result is combined with the array length via a modulo operation to produce the target bucket index. This index directly yields the memory location of the bucket, allowing immediate access to the stored data.

def compute_index(key, capacity):
    h = hash_function(key)
    return h % capacity

Collision Scenarios

Hash collisions occur when distinct keys yield the same bucket index after hashing and modulo operations. Multiple entries then contend for the same slot.

Collision Resolution Strategies

Bucket-Linked Lists

When a collision happens, the new entry is appended to a linked list inside the occupied bucket. Lookup requires traversing this list to match the desired key. Traversal makes this approach slower for heavily loaded buckets.

class BucketNode:
    def __init__(self, k, v):
        self.key = k
        self.val = v
        self.next = None

class HashTable:
    def __init__(self, size):
        self.cap = size
        self.store = [None] * size

    def insert(self, k, v):
        idx = compute_index(k, self.cap)
        node = self.store[idx]
        if not node:
            self.store[idx] = BucketNode(k, v)
            return
        while node:
            if node.key == k:
                node.val = v
                return
            if not node.next:
                break
            node = node.next
        node.next = BucketNode(k, v)

Dynamic Resizing

Increasing the number of buckets reduces the probability of collisions because the modulo result changes for existing keys. This process rebuilds the table with a larger array and reinserts all entries—known as rehashing. Since every key’s index may differ, performance overhead is significant.

def resize(table, new_cap):
    old_store = table.store
    table.cap = new_cap
    table.store = [None] * new_cap
    for head in old_store:
        curr = head
        while curr:
            table.insert(curr.key, curr.val)
            curr = curr.next

In parctice, systems often combine both strategies: initial collisions are handled with linked lists per bucket, and once a list exceeds a threshold length, resizing is triggered. To mitigate rehashing cost, migration can be performed incrementally during normal operations, retaining the old bucket array until relocation completes.