Chaining in Hashing: What It Is and How It Works

Chaining in hashing is a technique to handle collisions by storing multiple elements that hash to the same index in a linked list or chain. When two keys map to the same hash table slot, chaining keeps them in a list at that slot, allowing efficient storage and retrieval.

How It Works

Imagine a row of mailboxes where each mailbox represents a slot in a hash table. When you want to store a letter (data), you use an address (hash function) to find the right mailbox. Sometimes, two letters have the same address and need the same mailbox. Instead of throwing one away, chaining puts all letters for that mailbox into a small box inside it, like a chain of letters.

This chain is usually a linked list or another simple data structure that holds all items with the same hash index. When you want to find a letter, you go to the mailbox and look through the chain until you find the right one. This way, collisions don’t cause data loss and the hash table stays efficient.

Example

This example shows a simple hash table using chaining to handle collisions. Each slot holds a list of values that share the same hash index.

python

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

    def hash_function(self, key):
        return key % self.size

    def insert(self, key):
        index = self.hash_function(key)
        self.table[index].append(key)

    def search(self, key):
        index = self.hash_function(key)
        if key in self.table[index]:
            return True
        return False

# Create a hash table of size 5
hash_table = HashTable(5)

# Insert keys
hash_table.insert(10)  # Goes to index 0
hash_table.insert(15)  # Also index 0, collision handled by chaining
hash_table.insert(7)   # Goes to index 2

# Search keys
print(hash_table.search(10))  # True
print(hash_table.search(15))  # True
print(hash_table.search(7))   # True
print(hash_table.search(3))   # False

Output

True
True
True
False

When to Use

Chaining is useful when you expect collisions in a hash table because it keeps all items safely without overwriting. It works well when the number of keys is unknown or can grow, as chains can expand dynamically.

Real-world uses include database indexing, caching systems, and symbol tables in compilers, where quick access to data is needed even if many keys share the same hash slot.

Key Points

• Chaining stores collided items in a list at the same hash index.
• It prevents data loss from collisions by allowing multiple items per slot.
• Chains can grow dynamically, making it flexible for many keys.
• Search time depends on chain length but is usually efficient with a good hash function.

Key Takeaways

Chaining handles hash collisions by storing multiple items in a list at the same index.

It keeps data safe and accessible even when keys share hash values.

Chaining is flexible and works well when the number of keys changes.

Good hash functions reduce chain length and improve performance.

Commonly used in databases, caches, and symbol tables for fast data access.