Hash Table Concept and Hash Functions in DSA C#

Mental Model

A hash table stores data by turning keys into numbers to find values quickly. It uses a special function to decide where to put each item.

Analogy: Imagine a library where each book has a unique code. Instead of searching all shelves, you use the code to go directly to the right shelf and spot.

Hash Table:
[0] -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Hash Function: key % 5

Example: key=7 -> 7 % 5 = 2 -> store at index 2

Dry Run Walkthrough

Input: Insert keys 7, 12, 17 into a hash table of size 5 using hash function key % 5

Goal: Show how keys are placed in the hash table using the hash function

Step 1: Insert key 7: compute 7 % 5 = 2, place 7 at index 2

[0] -> null
[1] -> null
[2] -> 7 -> null
[3] -> null
[4] -> null

Why: We use the hash function to find the correct index to store key 7

Step 2: Insert key 12: compute 12 % 5 = 2, collision at index 2, add 12 after 7

[0] -> null
[1] -> null
[2] -> 7 -> 12 -> null
[3] -> null
[4] -> null

Why: Collision happens, so we link the new key after the existing one at index 2

Step 3: Insert key 17: compute 17 % 5 = 2, collision at index 2, add 17 after 12

[0] -> null
[1] -> null
[2] -> 7 -> 12 -> 17 -> null
[3] -> null
[4] -> null

Why: Another collision, so we add key 17 at the end of the chain at index 2

Result:

[0] -> null
[1] -> null
[2] -> 7 -> 12 -> 17 -> null
[3] -> null
[4] -> null

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class HashTable
{
    private readonly int size;
    private readonly LinkedList<int>[] table;

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

    private int HashFunction(int key)
    {
        return key % size; // compute index
    }

    public void Insert(int key)
    {
        int index = HashFunction(key); // find index
        table[index].AddLast(key); // add key to linked list at index
    }

    public void PrintTable()
    {
        for (int i = 0; i < size; i++)
        {
            Console.Write($"[{i}] -> ");
            foreach (var key in table[i])
            {
                Console.Write(key + " -> ");
            }
            Console.WriteLine("null");
        }
    }
}

class Program
{
    static void Main()
    {
        HashTable ht = new HashTable(5);
        ht.Insert(7);
        ht.Insert(12);
        ht.Insert(17);
        ht.PrintTable();
    }
}

return key % size; // compute index

calculate index using hash function

int index = HashFunction(key); // find index

get index for key insertion

table[index].AddLast(key); // add key to linked list at index

handle collisions by chaining keys in linked list

Output

[0] -> null

[1] -> null

[2] -> 7 -> 12 -> 17 -> null

[3] -> null

[4] -> null

Complexity Analysis

Time: O(1) average for insert because hash function gives direct index; O(n) worst if many collisions chain

Space: O(n) because we store all keys in the table and linked lists

vs Alternative: Compared to arrays or lists, hash tables provide faster average lookup and insert by avoiding full scans

Edge Cases

Inserting keys that all hash to the same index

All keys are stored in a linked list at that index, causing longer chains and slower operations

DSA C#

table[index].AddLast(key); // add key to linked list at index

Empty hash table with no keys inserted

Print shows all indices pointing to null, no keys stored

DSA C#

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

When to Use This Pattern

When you need fast lookup by key and can accept some collisions, use a hash table with a hash function to map keys to indexes.

Common Mistakes

Mistake: Not handling collisions, so new keys overwrite existing ones at the same index
Fix: Use chaining (linked lists) or open addressing to store multiple keys at the same index

Summary

Stores keys by converting them to indexes using a hash function for quick access.

Use when you want fast insert and search by key without scanning all data.

The hash function decides where to store keys, and collisions are handled by chaining keys together.

Practice

1. What is the main purpose of a hash function in a hash table?

easy

A. To encrypt the data stored in the table

B. To sort the keys in ascending order

C. To convert a key into an index for storing values

D. To count the number of elements in the table

Solution

1. Step 1: Understand the role of a hash function

   A hash function takes a key and converts it into a number called an index.

2. Step 2: Connect index to storage in hash table

   This index tells where to store or find the value in the hash table.

3. Final Answer:

   To convert a key into an index for storing values -> Option C

4. Quick Check:

   Hash function = key to index [OK]

Hint: Hash function maps keys to storage spots [OK]

Common Mistakes:

• Thinking hash function sorts keys
• Confusing hash function with encryption
• Believing hash function counts elements

2. Which of the following is the correct way to declare a hash table in C#?

easy

A. var table = new Hashtable();

B. var table = new HashTable();

C. var table = new hash_table();

D. var table = new hashTable();

Solution

1. Step 1: Recall correct class name in C#

   The correct class name is 'Hashtable' with capital H and T.

2. Step 2: Check syntax for creating instance

   Using 'new Hashtable()' with correct casing creates a hash table object.

3. Final Answer:

   var table = new Hashtable(); -> Option A

4. Quick Check:

   Correct class name and syntax [OK]

Hint: Remember C# is case-sensitive; use Hashtable exactly [OK]

Common Mistakes:

• Using wrong capitalization
• Adding underscores in class name
• Using lowercase letters incorrectly

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

var table = new Hashtable();
table["apple"] = 5;
table["banana"] = 3;
table["apple"] = 7;
Console.WriteLine(table["apple"]);

medium

A. 7

B. 3

C. Error

D. 5

Solution

1. Step 1: Understand key-value assignment in Hashtable

   Assigning table["apple"] = 5 stores 5 at key "apple".

2. Step 2: Overwriting value for the same key

   Later, table["apple"] = 7 replaces the old value 5 with 7.

3. Step 3: Print the current value for key "apple"

   Console.WriteLine outputs the latest value 7.

4. Final Answer:

   7 -> Option A

5. Quick Check:

   Last assigned value for key = output [OK]

Hint: Last value assigned to key is stored [OK]

Common Mistakes:

• Thinking values add up
• Expecting first value to print
• Assuming error on duplicate key

4. Identify the error in this C# code snippet using Hashtable:

var table = new Hashtable();
table.Add("key1", 10);
table.Add("key1", 20);
Console.WriteLine(table["key1"]);

medium

A. No error; output is 20

B. Runtime error due to duplicate key

C. Compile-time error due to Add method

D. Output is 10

Solution

1. Step 1: Understand Add method behavior

   Add throws an error if the key already exists in the Hashtable.

2. Step 2: Check duplicate key usage

   Adding "key1" twice causes a runtime exception on second Add.

3. Final Answer:

   Runtime error due to duplicate key -> Option B

4. Quick Check:

   Add fails on duplicate keys [OK]

Hint: Add method errors on duplicate keys; use indexer to overwrite [OK]

Common Mistakes:

• Assuming Add overwrites existing keys
• Expecting compile-time error
• Thinking output prints without error

5. Given a hash table with a simple hash function: hash(key) = key % 5, which of the following keys will cause a collision if inserted in order: 12, 8, 9, 22?

hard

A. 12 and 8

B. 8 and 9

C. 9 and 22

D. 12 and 22

Solution

1. Step 1: Calculate hash for each key

   12 % 5 = 2, 8 % 5 = 3, 9 % 5 = 4, 22 % 5 = 2.

2. Step 2: Identify keys with same hash index

   12 and 22 both hash to index 2. Others have unique indices.

3. Step 3: Check insertion order

   Insert 12 (index 2), 8 (3) no collision, 9 (4) no collision, 22 (2) causes collision with 12.

4. Final Answer:

   12 and 22 -> Option D

5. Quick Check:

   Keys with same hash cause collision [OK]

Hint: Calculate key % 5 to find collisions [OK]

Common Mistakes:

• Calculating wrong modulo
• Ignoring insertion order
• Assuming different hashes for close numbers