Collision handling (chaining) in Data Structures Theory - Time & Space Complexity

Time Complexity: Collision handling (chaining)

O(n/k)

Understanding Time Complexity

When storing data in a hash table, sometimes two items want the same spot. This is called a collision.

We want to understand how handling collisions by chaining affects the time it takes to find or add items.

Scenario Under Consideration

Analyze the time complexity of inserting and searching using chaining in a hash table.

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

    def insert(self, key, value):
        index = hash(key) % self.size
        self.table[index].append((key, value))

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

This code stores items in buckets (lists) at positions based on the key's hash. Collisions are handled by adding items to the list at that bucket.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the list (chain) at a bucket during search.
• How many times: Depends on how many items collided and are stored in the same bucket.

How Execution Grows With Input

As more items are added, the chains in each bucket can grow longer if the table size stays the same.

Input Size (n)	Approx. Operations (chain length)
10	About 1 or 2 items per bucket
100	About 10 items per bucket if size is 10
1000	About 100 items per bucket if size is 10

Pattern observation: If the number of buckets stays fixed, the time to search or insert grows roughly in proportion to the number of items per bucket.

Final Time Complexity

Time Complexity: O(n/k) where n is number of items and k is number of buckets

This means the time depends on how many items share the same bucket. If buckets grow with items, it stays close to O(1).

Common Mistake

[X] Wrong: "Searching in a chained hash table is always O(1) no matter what."

[OK] Correct: If many items collide in the same bucket, the chain grows and search time increases. So it depends on how well the hash spreads items and the table size.

Interview Connect

Understanding collision handling with chaining helps you explain how hash tables work in real systems and why choosing a good hash function and table size matters.

Self-Check

"What if we doubled the number of buckets as we add more items? How would the time complexity change?"

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