Collision Handling Using Chaining in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of inserting keys in a chained hash table

Consider a hash table with 5 buckets using chaining for collision handling. The hash function is key % 5. Insert keys 7, 12, 17, 22 in this order. What is the printed state of the hash table after all insertions?

DSA Java

class Node {
    int key;
    Node next;
    Node(int key) { this.key = key; this.next = null; }
}

class HashTable {
    Node[] table = new Node[5];

    void insert(int key) {
        int index = key % 5;
        Node newNode = new Node(key);
        if (table[index] == null) {
            table[index] = newNode;
        } else {
            newNode.next = table[index];
            table[index] = newNode;
        }
    }

    void printTable() {
        for (int i = 0; i < table.length; i++) {
            System.out.print(i + ": ");
            Node current = table[i];
            while (current != null) {
                System.out.print(current.key + " -> ");
                current = current.next;
            }
            System.out.println("null");
        }
    }
}

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

A

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

B

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

C

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

D

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

💡 Hint

Remember the hash function is key % 5, and new nodes are inserted at the head of the chain.

All keys 7, 12, 17, and 22 have hash index 2 (since 7%5=2, 12%5=2, etc.). Each new key is inserted at the head of the linked list at index 2, so the order is last inserted first: 22 -> 17 -> 12 -> 7 -> null.

🧠 Conceptual

intermediate

Number of elements in a chained bucket after insertions

A hash table has 7 buckets and uses chaining. The hash function is key % 7. If keys 14, 21, 28, 35, 42 are inserted, how many elements will be in the bucket at index 0?

A 0

B 7

C 1

D 5

💡 Hint

Calculate the hash index for each key using key % 7.

All keys are multiples of 7, so key % 7 = 0 for all. Therefore, all 5 keys go into bucket 0.

🔧 Debug

advanced

Identify the error in chaining insertion code

What error will occur when running this chaining insertion code snippet?

DSA Java

class Node {
    int key;
    Node next;
    Node(int key) { this.key = key; this.next = null; }
}

class HashTable {
    Node[] table = new Node[3];

    void insert(int key) {
        int index = key % 3;
        Node newNode = new Node(key);
        if (table[index] != null) {
            newNode.next = table[index];
            table[index] = newNode;
        } else {
            table[index] = newNode;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        HashTable ht = new HashTable();
        ht.insert(1);
        ht.insert(4);
        ht.insert(7);
        System.out.println("Insertion done");
    }
}

A No error, prints 'Insertion done'

B NullPointerException at insert

C ArrayIndexOutOfBoundsException at insert

D Compilation error due to missing semicolon

💡 Hint

Check the insert method logic and array initialization.

The insert method correctly handles null and non-null buckets. The array size is 3, and keys 1,4,7 hash to indices 1,1,1 respectively, all valid. No exceptions occur.

❓ Predict Output

advanced

Output after deleting a key from chained hash table

Given a chained hash table with 3 buckets and hash function key % 3, keys 3, 6, 9 are inserted. Then key 6 is deleted. What is the printed state of the hash table?

DSA Java

class Node {
    int key;
    Node next;
    Node(int key) { this.key = key; this.next = null; }
}

class HashTable {
    Node[] table = new Node[3];

    void insert(int key) {
        int index = key % 3;
        Node newNode = new Node(key);
        newNode.next = table[index];
        table[index] = newNode;
    }

    void delete(int key) {
        int index = key % 3;
        Node current = table[index];
        Node prev = null;
        while (current != null) {
            if (current.key == key) {
                if (prev == null) {
                    table[index] = current.next;
                } else {
                    prev.next = current.next;
                }
                return;
            }
            prev = current;
            current = current.next;
        }
    }

    void printTable() {
        for (int i = 0; i < table.length; i++) {
            System.out.print(i + ": ");
            Node current = table[i];
            while (current != null) {
                System.out.print(current.key + " -> ");
                current = current.next;
            }
            System.out.println("null");
        }
    }
}

public class Main {
    public static void main(String[] args) {
        HashTable ht = new HashTable();
        ht.insert(3);
        ht.insert(6);
        ht.insert(9);
        ht.delete(6);
        ht.printTable();
    }
}

A

0: 3 -> 9 -> null
1: null
2: null

B

0: null
1: null
2: null

C

0: 9 -> 3 -> null
1: null
2: null

D

0: 9 -> null
1: null
2: null

💡 Hint

Remember insertion adds new nodes at the head. Deletion removes the node with key 6.

Keys 3,6,9 all hash to index 0 (3%3=0, 6%3=0, 9%3=0). Insertions add at head, so list is 9 -> 6 -> 3 -> null. Deleting 6 removes the middle node, resulting in 9 -> 3 -> null at index 0. The printed output shows index 0 with 9 -> 3 -> null, others null.

🧠 Conceptual

expert

Load factor impact on chaining performance

In a hash table using chaining, if the load factor (number of elements / number of buckets) increases significantly, what is the most likely effect on the average time complexity for search operations?

A Average search time remains constant (O(1))

B Average search time increases towards O(n)

C Average search time becomes unpredictable

D Average search time decreases (faster searches)

💡 Hint

Think about how longer chains affect search time.

As load factor increases, chains get longer, so searching requires traversing more nodes, making average search time approach O(n) where n is number of elements.

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