Collision Handling Using Chaining in DSA Java - Execution Trace

Concept Flow - Collision Handling Using Chaining

Insert key-value pair

↓

Compute hash index

↓

Check bucket at index

↓

Empty

↓

Create [Traverse linked list

↓

Add new node at head

↓

Done

When inserting, compute the hash index. If bucket is empty, create a new list. If collision occurs, add new node at the head of the linked list in that bucket.

Execution Sample

DSA Java

hashTable = new LinkedList[3];
insert(1, 'A');
insert(4, 'B');
insert(7, 'C');

Insert keys 1, 4, 7 into a hash table of size 3 using chaining to handle collisions.

Execution Table

Step	Operation	Bucket Index	Nodes in Bucket	Pointer Changes	Visual State
1	Insert key=1, value='A'	1 % 3 = 1	Empty	Create new list at index 1, add node (1, A)	[null, (1,A)->null, null]
2	Insert key=4, value='B'	4 % 3 = 1	(1,A)	Add new node (4,B) at head of list at index 1	[null, (4,B)->(1,A)->null, null]
3	Insert key=7, value='C'	7 % 3 = 1	(4,B)->(1,A)	Add new node (7,C) at head of list at index 1	[null, (7,C)->(4,B)->(1,A)->null, null]
4	End of insertions	-	-	-	[null, (7,C)->(4,B)->(1,A)->null, null]

💡 All keys inserted; collisions handled by chaining at bucket index 1.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
hashTable[0]	null	null	null	null	null
hashTable[1]	null	(1,A)->null	(4,B)->(1,A)->null	(7,C)->(4,B)->(1,A)->null	(7,C)->(4,B)->(1,A)->null
hashTable[2]	null	null	null	null	null

Key Moments - 3 Insights

Why do we add new nodes at the head of the linked list instead of the tail?

Adding at the head is faster because we don't need to traverse the list. See execution_table steps 2 and 3 where new nodes are added at the front.

What happens if the bucket is empty when inserting a new key?

A new linked list is created at that bucket and the node is added. See execution_table step 1 where bucket 1 was empty initially.

How does chaining handle multiple keys hashing to the same index?

All keys are stored in a linked list at that bucket. New keys are added at the head, preserving all entries. See execution_table steps 2 and 3.

Visual Quiz - 3 Questions

Look at the execution_table, what is the state of bucket index 1 after step 2?

A (1,A)->(4,B)->null

B (4,B)->(1,A)->null

C (7,C)->(4,B)->(1,A)->null

D null

💡 Hint

Check the 'Nodes in Bucket' and 'Visual State' columns at step 2.

At which step does the first collision occur in the hash table?

A Step 1

B Step 3

C Step 2

D No collision occurs

💡 Hint

Look at the 'Bucket Index' and 'Nodes in Bucket' columns to see when a bucket already has nodes.

If the hash table size changed to 4, where would key=7 be inserted?

A Bucket 3

B Bucket 1

C Bucket 0

D Bucket 2

💡 Hint

Calculate 7 % 4 and check the bucket index.

Concept Snapshot

Collision Handling Using Chaining:
- Use a linked list at each bucket to store multiple keys.
- Compute index = key % table_size.
- If bucket empty, create list and add node.
- If collision, add new node at head of list.
- Efficient insertion and lookup with chaining.

Full Transcript

Collision Handling Using Chaining stores multiple keys in the same bucket using linked lists. When inserting, the hash index is computed by key modulo table size. If the bucket is empty, a new linked list is created and the node is added. If the bucket already has nodes (collision), the new node is added at the head of the linked list. This method efficiently handles collisions by chaining nodes together. The example inserts keys 1, 4, and 7 into a hash table of size 3, all colliding at bucket index 1, forming a linked list with nodes (7,C), (4,B), and (1,A).

Practice

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

easy

A. Replace the existing element with the new one

B. Resize the hash table immediately on collision

C. Store collided elements in a linked list at the same index

D. Ignore the new element causing collision

Solution

1. Step 1: Understand collision in hash tables

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

2. Step 2: How chaining handles collision

   Chaining stores all collided elements in a linked list at that index, allowing multiple elements.

3. Final Answer:

   Store collided elements in a linked list at the same index -> Option C

4. Quick Check:

   Chaining = linked list at index [OK]

Hint: Chaining means linked list at one index for collisions [OK]

Common Mistakes:

• Thinking collision replaces old element
• Assuming resizing happens immediately on collision
• Ignoring collided elements

2. Which of the following is the correct way to declare a hash table with chaining in Java using LinkedList?

easy

A. LinkedList<Integer> table = new LinkedList<>();

B. LinkedList<Integer>[] table = new LinkedList[10];

C. LinkedList<Integer>[] table = new LinkedList<>[10];

D. LinkedList<Integer> table = new LinkedList[10];

Solution

1. Step 1: Understand array of linked lists declaration

   We need an array of LinkedList objects, so use LinkedList<Integer>[].

2. Step 2: Correct Java syntax for array of generic linked lists

   Java allows new LinkedList[10] but not new LinkedList<>[10], so LinkedList<Integer>[] table = new LinkedList[10]; is correct.

3. Final Answer:

   LinkedList<Integer>[] table = new LinkedList[10]; -> Option B

4. Quick Check:

   Array of LinkedList = LinkedList[] table [OK]

Hint: Array of LinkedList uses LinkedList<Type>[] [OK]

Common Mistakes:

• Trying to use new LinkedList<>[size]
• Declaring LinkedList without array
• Wrong generic syntax in array creation

3. Consider the following Java code snippet for a hash table with chaining:

import java.util.LinkedList;

public class HashTable {
    LinkedList<Integer>[] table;
    int size = 5;

    public HashTable() {
        table = new LinkedList[size];
        for (int i = 0; i < size; i++) {
            table[i] = new LinkedList<>();
        }
    }

    public void insert(int key) {
        int index = key % size;
        table[index].add(key);
    }

    public void printTable() {
        for (int i = 0; i < size; i++) {
            System.out.print(i + ": ");
            for (int val : table[i]) {
                System.out.print(val + " -> ");
            }
            System.out.println("null");
        }
    }

    public static void main(String[] args) {
        HashTable ht = new HashTable();
        ht.insert(7);
        ht.insert(12);
        ht.insert(17);
        ht.printTable();
    }
}

What is the output of this program?

medium

A. 0: null
1: null
2: null
3: 7 -> 12 -> 17 -> null
4: null

B. 0: 7 -> 12 -> 17 -> null
1: null
2: null
3: null
4: null

C. 0: 12 -> null
1: null
2: 7 -> 17 -> null
3: null
4: null

D. 0: null
1: null
2: 7 -> 12 -> 17 -> null
3: null
4: null

Solution

1. Step 1: Calculate index for each inserted key

   Size is 5, so index = key % 5. 7 % 5 = 2, 12 % 5 = 2, 17 % 5 = 2.

2. Step 2: Insert keys at index 2 and print table

   All keys go to table[2]. So index 2 has 7 -> 12 -> 17 -> null, others are empty.

3. Final Answer:

   0: null 1: null 2: 7 -> 12 -> 17 -> null 3: null 4: null -> Option D

4. Quick Check:

   Keys mod 5 = 2, all at index 2 [OK]

Hint: Calculate key % size to find index [OK]

Common Mistakes:

• Miscomputing modulo operation
• Assuming keys go to different indices
• Confusing index with key value

4. The following code snippet tries to insert keys into a hash table with chaining but throws a NullPointerException. What is the error?

import java.util.LinkedList;

public class HashTable {
    LinkedList<Integer>[] table = new LinkedList[5];

    public void insert(int key) {
        int index = key % 5;
        table[index].add(key);
    }

    public static void main(String[] args) {
        HashTable ht = new HashTable();
        ht.insert(10);
    }
}

medium

A. The array of LinkedLists is not initialized with LinkedList objects

B. The modulo operation is incorrect

C. The insert method should return a value

D. The LinkedList should be replaced with ArrayList

Solution

1. Step 1: Identify cause of NullPointerException

   The array 'table' is created but each element is null because LinkedList objects are not initialized.

2. Step 2: Fix by initializing each LinkedList in the array

   Before inserting, each table[i] must be assigned new LinkedList<>() to avoid null pointer.

3. Final Answer:

   The array of LinkedLists is not initialized with LinkedList objects -> Option A

4. Quick Check:

   NullPointerException = uninitialized LinkedList array [OK]

Hint: Initialize each LinkedList before use [OK]

Common Mistakes:

• Ignoring initialization of linked lists
• Blaming modulo operation
• Thinking insert needs return value

5. You want to implement a hash table with chaining that supports insert and search operations. Given the following partial code, fill in the missing search method to return true if the key exists, otherwise false.

import java.util.LinkedList;

public class HashTable {
    LinkedList<Integer>[] table;
    int size = 7;

    public HashTable() {
        table = new LinkedList[size];
        for (int i = 0; i < size; i++) {
            table[i] = new LinkedList<>();
        }
    }

    public void insert(int key) {
        int index = key % size;
        table[index].add(key);
    }

    // Fill this method
    public boolean search(int key) {
        // ???
    }
}

Which of the following is the correct implementation of the search method?

hard

A. int index = key % size;
return table[index].contains(key);

B. int index = key % size;
return table[index].get(0) == key;

C. for (LinkedList<Integer> list : table) {
if (list.contains(key)) return true;
}
return false;

D. int index = key % size;
return table[index].indexOf(key) == -1;

Solution

1. Step 1: Calculate index using modulo

   Use key % size to find the correct linked list index.

2. Step 2: Check if linked list at index contains the key

   Use contains() method on linked list to check presence of key.

3. Final Answer:

   int index = key % size; return table[index].contains(key); -> Option A

4. Quick Check:

   Search = contains at index [OK]

Hint: Search key in linked list at key % size [OK]

Common Mistakes:

• Checking only first element in list
• Searching all lists instead of one
• Using indexOf == -1 incorrectly