Why Hash Table Concept and Hash Functions in DSA C#?

The Big Idea

What if you could find anything in a huge list instantly, without searching every item?

The Scenario

Imagine you have a huge phone book with thousands of names and numbers. You want to find a friend's number quickly, but you have to look through every page one by one.

The Problem

Searching manually through the phone book is slow and tiring. It takes a lot of time to find what you want, and you might make mistakes or lose your place.

The Solution

A hash table works like a super-smart phone book. It uses a special formula called a hash function to jump directly to the exact page where your friend's number is stored. This makes finding things very fast and easy.

Before vs After

✗ Before

for (int i = 0; i < phoneBook.Length; i++) {
    if (phoneBook[i].Name == searchName) {
        return phoneBook[i].Number;
    }
}

✓ After

int index = HashFunction(searchName);
return hashTable[index];

What It Enables

Hash tables let you find, add, or remove data almost instantly, even in huge collections.

Real Life Example

When you search for a contact on your phone, it uses a hash table behind the scenes to show the result immediately.

Key Takeaways

Manual searching is slow and error-prone.

Hash functions turn keys into quick access points.

Hash tables make data lookup very fast and efficient.

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