Hash Table Concept and Hash Functions in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this hash function simulation?

Consider a simple hash function that calculates the sum of ASCII values of characters in a string and then takes modulo 10. What is the output index for the key "cat"?

DSA C#

string key = "cat";
int hash = 0;
foreach (char c in key) {
    hash += (int)c;
}
int index = hash % 10;
Console.WriteLine(index);

A 2

B 5

C 8

D 7

💡 Hint

Calculate ASCII values: 'c' = 99, 'a' = 97, 't' = 116.

Sum of ASCII values: 'c' (99) + 'a' (97) + 't' (116) = 312. Then 312 % 10 = 2. The output is 2.

❓ Predict Output

intermediate

What is the output of this hash table insertion simulation?

Given a hash table of size 5 and a hash function h(key) = key % 5, what is the final state of the table after inserting keys 7, 12, 17 using linear probing for collision resolution?

DSA C#

int size = 5;
int[] table = new int[size];
for (int i = 0; i < size; i++) table[i] = -1;
int[] keys = {7, 12, 17};
foreach (int key in keys) {
    int index = key % size;
    while (table[index] != -1) {
        index = (index + 1) % size;
    }
    table[index] = key;
}
Console.WriteLine("[" + string.Join(", ", table) + "]");

A [7, 12, 17, -1, -1]

B [-1, -1, 7, 12, 17]

C [7, -1, -1, 12, 17]

D [7, 17, 12, -1, -1]

💡 Hint

Calculate initial indices and resolve collisions by moving to next empty slot.

7 % 5 = 2, insert at index 2.
12 % 5 = 2 (collision), probe to index 3.
17 % 5 = 2 (collisions at 2 and 3), probe to index 4.
Final table: [-1, -1, 7, 12, 17].

🔧 Debug

advanced

What error does this hash function code raise?

Identify the error raised by this C# hash function code snippet.

DSA C#

string key = null;
int hash = 0;
foreach (char c in key) {
    hash += (int)c;
}
int index = hash % 10;
Console.WriteLine(index);

A ArgumentNullException

B IndexOutOfRangeException

C No error, outputs 0

D NullReferenceException

💡 Hint

What happens when you try to loop over a null string?

Since 'key' is null, trying to iterate over it causes a NullReferenceException.

🧠 Conceptual

advanced

Which property is NOT essential for a good hash function?

Select the property that is NOT essential for a good hash function used in hash tables.

A Ability to reverse the hash to original input

B Deterministic output for the same input

C Uniform distribution of hash values

D Fast computation time

💡 Hint

Think about what a hash function is used for in hash tables.

A good hash function must be deterministic, fast, and distribute keys uniformly.

Reversing the hash is not required and usually impossible.

🚀 Application

expert

What is the final linked list at bucket 3 after these insertions?

A hash table uses chaining with linked lists for collisions. The hash function is h(key) = key % 4. Insert keys 3, 7, 11, 15 in order. What is the linked list at bucket 3 after all insertions?

DSA C#

int size = 4;
List<int>[] table = new List<int>[size];
for (int i = 0; i < size; i++) table[i] = new List<int>();
int[] keys = {3, 7, 11, 15};
foreach (int key in keys) {
    int index = key % size;
    table[index].Add(key);
}
Console.WriteLine(string.Join(" -> ", table[3]) + " -> null");

A 7 -> 3 -> 11 -> 15 -> null

B 3 -> 11 -> 7 -> 15 -> null

C 3 -> 7 -> 11 -> 15 -> null

D 15 -> 11 -> 7 -> 3 -> null

💡 Hint

Calculate key % 4 for each key and add to corresponding bucket list in order.

All keys 3,7,11,15 % 4 = 3, so all go to bucket 3.

They are inserted in order: 3, then 7, then 11, then 15.

Final linked list: 3 -> 7 -> 11 -> 15 -> null.

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