Collision handling (chaining) in Data Structures Theory - Full Explanation

Introduction

Imagine you have a list of items to store, but sometimes two items want to go to the same spot. This problem happens in hash tables when two keys produce the same address. We need a way to handle these clashes so no data is lost or overwritten.

Explanation

Hash Table Collisions

When a hash function assigns the same index to two different keys, a collision occurs. This means the hash table cannot store both items in the same slot directly. Handling collisions is essential to keep the hash table efficient and accurate.

Collisions happen when different keys map to the same index in a hash table.

Chaining Method

Chaining solves collisions by storing all items that hash to the same index in a linked list or chain. Instead of one item per slot, each slot points to a list of items. This way, multiple keys can share the same index without overwriting each other.

Chaining uses linked lists at each slot to hold multiple items that collide.

Insertion in Chaining

To insert a key, the hash function finds the index. Then the key is added to the linked list at that index. If the list is empty, a new list starts; if not, the key is appended. This keeps all collided keys accessible.

Insertion adds the new key to the linked list at the hashed index.

Searching in Chaining

To find a key, the hash function locates the index. Then the linked list at that index is searched sequentially. If the key is found in the list, it is returned; otherwise, it is not in the table.

Searching checks the linked list at the hashed index for the key.

Advantages and Drawbacks

Chaining is simple and handles collisions well even when many keys collide. However, if many keys hash to the same index, the linked list grows long, slowing search and insertion. Good hash functions and table sizing help reduce this problem.

Chaining is easy to implement but can slow down if many keys collide at one index.

Real World Analogy

Imagine a mailbox where letters are sorted by street address. Sometimes, multiple letters go to the same mailbox slot. Instead of throwing letters away, the mailbox has a small basket to hold all letters for that address. You check the basket to find your letter.

Hash Table Collisions → Multiple letters addressed to the same mailbox slot

Chaining Method → A basket inside the mailbox slot holding all letters for that address

Insertion in Chaining → Putting a new letter into the basket at the mailbox slot

Searching in Chaining → Looking through the basket to find the correct letter

Advantages and Drawbacks → The basket keeps letters safe but can get crowded, making it harder to find one

Diagram

Diagram

┌───────────────┐
│ Hash Table    │
├───────────────┤
│ Index 0       │ → None
│ Index 1       │ → [Key A] → None
│ Index 2       │ → [Key B] → [Key C] → None
│ Index 3       │ → None
│ Index 4       │ → [Key D] → None
└───────────────┘

This diagram shows a hash table where some indexes point to linked lists (chains) holding multiple keys due to collisions.

Key Facts

Collision → When two different keys hash to the same index in a hash table.

Chaining → A collision handling method that stores collided keys in a linked list at the same index.

Linked List → A sequence of nodes where each node points to the next, used to store multiple items in chaining.

Hash Function → A function that converts a key into an index for the hash table.

Load Factor → The ratio of stored keys to the number of slots in the hash table, affecting performance.

Code Example

Data Structures Theory

class HashTable:
    def __init__(self, size=5):
        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
        # Otherwise, append new key-value
        self.table[index].append((key, value))

    def search(self, key):
        index = self.hash_function(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

# Example usage
ht = HashTable()
ht.insert('apple', 10)
ht.insert('banana', 20)
ht.insert('grape', 30)  # Might collide with 'apple'
print(ht.search('apple'))
print(ht.search('banana'))
print(ht.search('grape'))
print(ht.search('orange'))

Common Confusions

Chaining stores all keys in one big list for the whole table.

Chaining stores all keys in one big list for the whole table. Chaining stores keys in separate linked lists at each index, not one global list.

Chaining removes the need for a good hash function.

Chaining removes the need for a good hash function. A good hash function is still important to distribute keys evenly and keep chains short.

Summary

Collisions happen when different keys map to the same hash table index and must be handled to avoid data loss.

Chaining handles collisions by storing collided keys in linked lists at each index, allowing multiple keys per slot.

Good hash functions and proper table size keep chains short and operations efficient.

Practice

1. What is the main idea behind collision handling by chaining in hash tables?

easy

A. Use a second hash function to find a new index

B. Overwrite the existing item when a collision occurs

C. Resize the hash table immediately after a collision

D. Store collided items in a linked list at the same index

Solution

1. Step 1: Understand collision in hash tables

   When two keys hash to the same index, a collision occurs.

2. Step 2: Explain chaining method

   Chaining stores all collided items in a linked list at that index, preserving all entries.

3. Final Answer:

   Store collided items in a linked list at the same index -> Option D

4. Quick Check:

   Chaining = linked list at index [OK]

Hint: Chaining means linked lists hold collisions at one spot [OK]

Common Mistakes:

• Thinking collisions overwrite existing data
• Confusing chaining with open addressing
• Assuming resizing happens immediately on collision

2. Which of the following is the correct way to represent chaining in a hash table?

easy

A. Each index holds a single value only

B. Each index holds a linked list of values

C. Each index holds a separate hash table

D. Each index holds a fixed-size array of values

Solution

1. Step 1: Recall chaining structure

   Chaining uses linked lists to store multiple items at one index.

2. Step 2: Match options to chaining

   Only Each index holds a linked list of values describes linked lists at each index, which is chaining.

3. Final Answer:

   Each index holds a linked list of values -> Option B

4. Quick Check:

   Chaining = linked list per index [OK]

Hint: Chaining means linked lists at each hash index [OK]

Common Mistakes:

• Choosing single value per index (no chaining)
• Confusing chaining with nested hash tables
• Thinking arrays are used instead of lists

3. Consider a hash table using chaining with 5 buckets. The hash function is h(key) = key % 5. Insert keys 7, 12, 17, 22. What does the bucket at index 2 contain?

medium

A. [7, 12, 17, 22]

B. [7, 17]

C. [12, 22]

D. [2]

Solution

1. Step 1: Calculate hash for each key

   7 % 5 = 2, 12 % 5 = 2, 17 % 5 = 2, 22 % 5 = 2. All keys map to index 2.

2. Step 2: List keys in bucket 2

   Bucket 2 contains keys 7, 12, 17, 22.

3. Step 3: Verify which keys actually hash to 2

   7 % 5 = 2, 12 % 5 = 2, 17 % 5 = 2, 22 % 5 = 2. All keys map to index 2.

4. Step 4: Check options carefully

   [7, 17] lists [7, 17], but keys 12 and 22 also hash to 2, so [7, 17] is incomplete. [7, 12, 17, 22] lists all keys, which is correct.

5. Final Answer:

   [7, 12, 17, 22] -> Option A

6. Quick Check:

   All keys mod 5 = 2 [OK]

Hint: Apply mod function to keys to find bucket [OK]

Common Mistakes:

• Miscomputing modulo operation
• Assuming keys distribute to different buckets
• Confusing bucket index with key values

4. A hash table uses chaining but the linked list at one index is not updated correctly after insertion. What is the likely error?

medium

A. The new node is not linked to the existing list

B. The hash function returns different values for same key

C. The table size is too small

D. The keys are not unique

Solution

1. Step 1: Understand chaining insertion

   When inserting, the new node must link to the existing list at that index.

2. Step 2: Identify error from symptoms

   If the list is not updated, likely the new node was not linked properly.

3. Final Answer:

   The new node is not linked to the existing list -> Option A

4. Quick Check:

   Missing link causes list update failure [OK]

Hint: Check if new node links to list head [OK]

Common Mistakes:

• Blaming hash function for insertion errors
• Thinking table size causes linking issues
• Confusing key uniqueness with chaining errors

5. You have a hash table with chaining. If many keys hash to the same index, what is the best way to improve performance?

hard

A. Ignore collisions and overwrite old keys

B. Use a linked list with more nodes at that index

C. Increase the table size and rehash all keys

D. Store all keys in a single bucket

Solution

1. Step 1: Understand impact of many collisions

   Many keys in one bucket slow down search because linked list grows long.

2. Step 2: Improve performance by resizing

   Increasing table size reduces collisions by spreading keys across more buckets.

3. Step 3: Rehash keys after resizing

   Rehashing redistributes keys according to new table size for better balance.

4. Final Answer:

   Increase the table size and rehash all keys -> Option C

5. Quick Check:

   Resize + rehash reduces collisions [OK]

Hint: Resize table and rehash keys to reduce collisions [OK]

Common Mistakes:

• Adding more nodes without resizing
• Overwriting keys loses data
• Putting all keys in one bucket defeats hashing