Collision Handling Using Chaining in DSA C# - Build from Scratch

Collision Handling Using Chaining

📖 Scenario: Imagine you are building a simple phone book app. You want to store names and phone numbers so you can find a number quickly by name. But sometimes two names might hash to the same spot in your storage. To handle this, you will use chaining, which means storing multiple entries in a list at the same spot.

🎯 Goal: You will create a hash table using chaining to handle collisions. You will add some entries, then find and print the phone number for a given name.

📋 What You'll Learn

Create a hash table with chaining using an array of lists

Add entries with names and phone numbers to the hash table

Use a simple hash function to find the index

Handle collisions by adding entries to the list at the index

Search for a phone number by name in the hash table

Print the found phone number or a message if not found

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding collision handling is important for software developers working with data storage, search engines, and performance optimization.

1

Create the hash table with chaining

Create a class called Entry with two public string fields: Name and PhoneNumber. Then create a List<Entry>[] array called hashTable with size 5. Initialize each element of hashTable with a new empty List<Entry>.

DSA C#

// Your code here

Hint

Think of hashTable as an array where each slot holds a list of entries. Initialize each slot with an empty list.

2

Add a simple hash function

Add a static method called HashFunction that takes a string name and returns an int. The method should return the sum of the ASCII values of the characters in name modulo 5.

DSA C#

using System;
using System.Collections.Generic;

class Entry
{
    public string Name;
    public string PhoneNumber;

    public Entry(string name, string phoneNumber)
    {
        Name = name;
        PhoneNumber = phoneNumber;
    }
}

class Program
{
    static int HashFunction(string name)
    {
        // Your code here
    }

    static void Main()
    {
        List[] hashTable = new List[5];
        for (int i = 0; i ();
        }
    }
}

Hint

Sum the ASCII codes of each character in the name, then use modulo 5 to get an index between 0 and 4.

3

Add entries to the hash table using chaining

Inside Main, add these entries to hashTable using chaining: ("Alice", "12345"), ("Bob", "67890"), ("Charlie", "54321"), ("David", "98765"). Use HashFunction to find the index, then add a new Entry to the list at that index.

DSA C#

using System;
using System.Collections.Generic;

class Entry
{
    public string Name;
    public string PhoneNumber;

    public Entry(string name, string phoneNumber)
    {
        Name = name;
        PhoneNumber = phoneNumber;
    }
}

class Program
{
    static int HashFunction(string name)
    {
        int sum = 0;
        foreach (char c in name)
        {
            sum += c;
        }
        return sum % 5;
    }

    static void Main()
    {
        List[] hashTable = new List[5];
        for (int i = 0; i ();
        }

        // Your code here
    }
}

Hint

Use a loop to add each name and phone number to the list at the index given by HashFunction.

4

Search and print a phone number by name

Add code inside Main to search for the phone number of "Charlie". Use HashFunction to find the index, then loop through the list at that index to find the Entry with Name equal to "Charlie". Print the phone number if found, otherwise print "Not found".

DSA C#

using System;
using System.Collections.Generic;

class Entry
{
    public string Name;
    public string PhoneNumber;

    public Entry(string name, string phoneNumber)
    {
        Name = name;
        PhoneNumber = phoneNumber;
    }
}

class Program
{
    static int HashFunction(string name)
    {
        int sum = 0;
        foreach (char c in name)
        {
            sum += c;
        }
        return sum % 5;
    }

    static void Main()
    {
        List[] hashTable = new List[5];
        for (int i = 0; i ();
        }

        string[] names = { "Alice", "Bob", "Charlie", "David" };
        string[] phones = { "12345", "67890", "54321", "98765" };

        for (int i = 0; i < names.Length; i++)
        {
            int index = HashFunction(names[i]);
            hashTable[index].Add(new Entry(names[i], phones[i]));
        }

        // Search for Charlie's phone number and print it
        // Your code here
    }
}

Hint

Use the hash function to find the list, then check each entry's name to find "Charlie". Print the phone number if found.

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 when collision occurs

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 happens.

2. Step 2: How chaining handles collisions

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

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 [OK]

Common Mistakes:

• Thinking chaining replaces old elements
• Confusing chaining with open addressing
• Assuming collisions are ignored

2. Which of the following is the correct way to declare a hash table with chaining in C# using List<T> for chaining?

easy

A. Dictionary hashTable = new Dictionary();

B. Dictionary hashTable = new Dictionary();

C. List hashTable = new List();

D. Dictionary hashTable = new Dictionary();

Solution

1. Step 1: Understand chaining data structure

   Chaining uses a list to store multiple values per key index.

2. Step 2: Correct C# syntax for dictionary with list values

   Dictionary means keys are int, values are lists of strings.

3. Final Answer:

   Dictionary hashTable = new Dictionary(); -> Option D

4. Quick Check:

   Dictionary with List values = Dictionary hashTable = new Dictionary(); [OK]

Hint: Use Dictionary with List as value for chaining [OK]

Common Mistakes:

• Using List with two generic types (invalid)
• Using Dictionary with simple string values only
• Confusing key and value types

3. What will be the output of the following C# code snippet using chaining?

var hashTable = new Dictionary();
int key = 2;
if (!hashTable.ContainsKey(key))
    hashTable[key] = new List<string>();
hashTable[key].Add("apple");
hashTable[key].Add("banana");

foreach(var item in hashTable[key])
    Console.Write(item + " ");

medium

A. No output

B. apple banana

C. apple

D. banana apple

Solution

1. Step 1: Initialize dictionary and add list for key 2

   Since key 2 is not present, a new list is created and assigned.

2. Step 2: Add "apple" and "banana" to list at key 2

   Both strings are added in order: "apple", then "banana".

3. Step 3: Print all items in list at key 2

   Loop prints "apple " then "banana " in order.

4. Final Answer:

   apple banana -> Option B

5. Quick Check:

   List order preserved = apple banana [OK]

Hint: Items print in insertion order in chaining list [OK]

Common Mistakes:

• Assuming reversed order output
• Forgetting to initialize list before adding
• Expecting no output if key missing

4. Identify the error in this C# code snippet implementing chaining:

var hashTable = new Dictionary();
int key = 5;
hashTable[key].Add("orange");

medium

A. Key does not exist; list not initialized before Add

B. Dictionary cannot have List as value type

C. Add method does not exist for List

D. Key must be string, not int

Solution

1. Step 1: Check if key 5 exists in dictionary

   Key 5 is not added yet, so hashTable[key] is null.

2. Step 2: Adding to null list causes runtime error

   Cannot call Add on null; list must be initialized first.

3. Final Answer:

   Key does not exist; list not initialized before Add -> Option A

4. Quick Check:

   Initialize list before Add [OK]

Hint: Always initialize list before adding elements [OK]

Common Mistakes:

• Assuming dictionary auto-creates lists
• Confusing key types
• Thinking Add method is invalid

5. You want to implement a hash table with chaining in C# that stores multiple values per key and supports removing a specific value from the chain. Which approach correctly supports this feature?

hard

A. Use Dictionary and call Remove(value) on the list at the key

B. Use Dictionary and overwrite value to remove

C. Use Dictionary but clear entire list to remove one value

D. Use Dictionary but do not implement removal

Solution

1. Step 1: Understand chaining with multiple values per key

   Chaining uses a list to hold multiple values at one key.

2. Step 2: Removing a specific value requires list's Remove method

   List<string> supports Remove(value) to delete one item without affecting others.

3. Step 3: Other options either overwrite or clear all values, not specific removal

   Overwriting loses all values; clearing removes all; ignoring removal is incomplete.

4. Final Answer:

   Use Dictionary and call Remove(value) on the list at the key -> Option A

5. Quick Check:

   List Remove supports specific value deletion [OK]

Hint: Use List and Remove(value) to delete specific chained item [OK]

Common Mistakes:

• Overwriting value instead of removing one
• Clearing entire list to remove one item
• Ignoring removal feature