Collision Handling Using Chaining in DSA Java - Build from Scratch

Collision Handling Using Chaining

📖 Scenario: Imagine you are building a simple phone book app that stores names and phone numbers. To keep the data organized and quickly find a number by name, you use a hash table. Sometimes, two names might get the same spot in the table. To handle this, you use chaining, which means you keep a small list of entries in that spot.

🎯 Goal: You will create a hash table using chaining to store and retrieve phone numbers by name. You will add entries, handle collisions by chaining, and finally print the contents of the hash table.

📋 What You'll Learn

Create a hash table with a fixed size array of linked lists

Add entries (name and phone number) to the hash table

Handle collisions by adding entries to the linked list at the hashed index

Print the full hash table showing all chains

💡 Why This Matters

🌍 Real World

Hash tables with chaining are used in many applications like phone books, databases, and caches to quickly find data even when collisions happen.

💼 Career

Understanding collision handling in hash tables is important for software engineers working on efficient data storage and retrieval systems.

1

Create the Hash Table Data Structure

Create a class called Entry with two String fields: name and phone. Then create a class called HashTable with a field table which is an array of LinkedList<Entry> of size 3. Initialize each element of table with a new LinkedList<>.

DSA Java

// Create Entry class and HashTable class with table array of LinkedList size 3
// Initialize each LinkedList in the array

Hint

Use an array of LinkedList with size 3. Initialize each element with new LinkedList<>().

2

Add a Hash Function and Insert Method

Inside the HashTable class, add a private method hash that takes a String name and returns an int index by calculating name.length() % 3. Then add a method insert that takes String name and String phone, creates an Entry, and adds it to the linked list at the index returned by hash(name).

DSA Java

import java.util.LinkedList;

class Entry {
    String name;
    String phone;

    Entry(String name, String phone) {
        this.name = name;
        this.phone = phone;
    }
}

class HashTable {
    LinkedList[] table;

    @SuppressWarnings("unchecked")
    HashTable() {
        table = new LinkedList[3];
        for (int i = 0; i ();
        }
    }

    // Add hash method and insert method below
    // Your code here
}

Hint

Hash function uses name length mod 3. Insert adds new Entry to linked list at hashed index.

3

Insert Sample Entries into the Hash Table

Create a public class Main with a main method. Inside main, create a HashTable object called phoneBook. Insert these entries using phoneBook.insert: ("Amy", "111-222"), ("Bob", "333-444"), ("Cathy", "555-666"), ("Dan", "777-888").

DSA Java

import java.util.LinkedList;

class Entry {
    String name;
    String phone;

    Entry(String name, String phone) {
        this.name = name;
        this.phone = phone;
    }
}

class HashTable {
    LinkedList[] table;

    @SuppressWarnings("unchecked")
    HashTable() {
        table = new LinkedList[3];
        for (int i = 0; i ();
        }
    }

    private int hash(String name) {
        return name.length() % 3;
    }

    void insert(String name, String phone) {
        int index = hash(name);
        Entry newEntry = new Entry(name, phone);
        table[index].add(newEntry);
    }
}

public class Main {
    public static void main(String[] args) {
        // Create HashTable and insert entries here
        // Your code here
    }
}

Hint

Create Main class with main method. Instantiate HashTable and insert the four entries exactly.

4

Print the Hash Table Contents Showing Chaining

In the main method, after inserting entries, add code to print the hash table contents. For each index from 0 to 2, print "Index i:" followed by each entry in the linked list at that index in the format "name -> phone". Separate entries with " -> ". End each index line with " -> null".

DSA Java

import java.util.LinkedList;

class Entry {
    String name;
    String phone;

    Entry(String name, String phone) {
        this.name = name;
        this.phone = phone;
    }
}

class HashTable {
    LinkedList[] table;

    @SuppressWarnings("unchecked")
    HashTable() {
        table = new LinkedList[3];
        for (int i = 0; i ();
        }
    }

    private int hash(String name) {
        return name.length() % 3;
    }

    void insert(String name, String phone) {
        int index = hash(name);
        Entry newEntry = new Entry(name, phone);
        table[index].add(newEntry);
    }
}

public class Main {
    public static void main(String[] args) {
        HashTable phoneBook = new HashTable();
        phoneBook.insert("Amy", "111-222");
        phoneBook.insert("Bob", "333-444");
        phoneBook.insert("Cathy", "555-666");
        phoneBook.insert("Dan", "777-888");

        // Print the hash table contents with chaining
        // Your code here
    }
}

Hint

Loop over each index. For each linked list, print entries as "name -> phone -> ". End with "null".

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