Collision Handling Using Chaining in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is collision in a hash table?

Collision happens when two different keys get mapped to the same index in the hash table.

beginner

What is chaining in collision handling?

Chaining is a method where each index of the hash table holds a list (or chain) of all elements that hash to the same index.

intermediate

How does chaining help in handling collisions?

Chaining stores multiple elements at the same index using a linked list or list, so collisions do not overwrite data but are stored together.

intermediate

What is the time complexity of search in a hash table using chaining in the average case?

Average case search time is O(1 + α), where α is the load factor (number of elements / number of buckets). Usually close to O(1) if load factor is low.

beginner

Show a simple Python code snippet to insert a key-value pair using chaining in a hash table.

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

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

    def insert(self, key, value):
        index = self.hash_function(key)
        # Check if key exists and update
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        # If key not found, append
        self.table[index].append((key, value))

What does chaining use to handle collisions in a hash table?

A Linked lists or lists at each index

B Open addressing

C Rehashing the entire table

D Ignoring collisions

Chaining stores collided elements in a list or linked list at the same index.

If two keys hash to the same index, what happens in chaining?

A One key overwrites the other

B The second key is discarded

C The table resizes immediately

D Both keys are stored in a chain (list) at that index

Chaining stores all collided keys in a list at the same index.

What is the main advantage of chaining over open addressing?

A No need to resize the table

B Handles collisions without probing other slots

C Uses less memory

D Faster hash function

Chaining stores collided elements in a list, avoiding probing other slots.

What data structure is commonly used to implement chaining?

A Array

B Stack

C Linked list or list

D Queue

Chaining uses linked lists or lists to store multiple elements at the same index.

What happens if the load factor increases in a hash table using chaining?

A Search time increases because chains get longer

B Search time decreases

C Table automatically shrinks

D Collisions stop occurring

Higher load factor means longer chains, which increases search time.

Explain how collision handling using chaining works in a hash table.

Think about what happens when two keys map to the same place.

Describe the advantages and disadvantages of using chaining for collision handling.

Consider both performance and memory.