Hash Table Concept and Hash Functions in DSA C# - Execution Trace

Concept Flow - Hash Table Concept and Hash Functions

Input Key

↓

Apply Hash Function

↓

Get Index in Array

↓

Store or Retrieve Value at Index

↓

Handle Collisions if Needed

↓

Return Value or Inserted Status

The hash table uses a hash function to convert a key into an index, then stores or retrieves the value at that index, handling collisions if they occur.

Execution Sample

DSA C#

int HashFunction(string key, int size) {
    int hash = 0;
    foreach (char c in key) {
        hash += c;
    }
    return hash % size;
}

This simple hash function sums ASCII values of characters in the key and returns the remainder when divided by the table size.

Execution Table

Step	Operation	Key	Hash Value	Index (Hash % Size)	Array State (Index: Value)	Collision Handling
1	Calculate hash for 'cat'	cat	99 + 97 + 116 = 312	312 % 10 = 2	[]	No collision, insert at index 2
2	Insert 'cat' with value 5	cat	312	2	[2: (cat,5)]	N/A
3	Calculate hash for 'dog'	dog	100 + 111 + 103 = 314	314 % 10 = 4	[2: (cat,5)]	No collision, insert at index 4
4	Insert 'dog' with value 7	dog	314	4	[2: (cat,5), 4: (dog,7)]	N/A
5	Calculate hash for 'tac'	tac	116 + 97 + 99 = 312	312 % 10 = 2	[2: (cat,5), 4: (dog,7)]	Collision at index 2
6	Handle collision for 'tac'	tac	312	2	[2: (cat,5) -> (tac,3), 4: (dog,7)]	Use chaining to add (tac,3) at index 2
7	Retrieve value for 'cat'	cat	312	2	[2: (cat,5) -> (tac,3), 4: (dog,7)]	Found at index 2, first node
8	Retrieve value for 'tac'	tac	312	2	[2: (cat,5) -> (tac,3), 4: (dog,7)]	Found at index 2, second node in chain
9	Retrieve value for 'dog'	dog	314	4	[2: (cat,5) -> (tac,3), 4: (dog,7)]	Found at index 4
10	End of operations				[2: (cat,5) -> (tac,3), 4: (dog,7)]	All operations complete

💡 All keys processed and stored/retrieved with collision handled by chaining.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 6	Final
hash	0	312 (cat)	314 (dog)	312 (tac)	312 (tac)	312 (tac)
index	N/A	2	4	2	2	2
array	Empty	[2: (cat,5)]	[2: (cat,5), 4: (dog,7)]	[2: (cat,5), 4: (dog,7)]	[2: (cat,5) -> (tac,3), 4: (dog,7)]	[2: (cat,5) -> (tac,3), 4: (dog,7)]

Key Moments - 3 Insights

Why do 'cat' and 'tac' cause a collision even though they are different keys?

Because the hash function sums character codes and both 'cat' and 'tac' sum to 312, they produce the same index 2, causing a collision as shown in steps 5 and 6.

How does the hash table store multiple values at the same index?

It uses chaining, which means storing a linked list of key-value pairs at that index, as seen in step 6 where (tac,3) is added after (cat,5).

Why is the modulo operation used in the hash function?

Modulo ensures the hash value fits within the array size, mapping any large hash to a valid index, e.g., 312 % 10 = 2 in step 1.

Visual Quiz - 3 Questions

Look at the execution table, what is the index for the key 'dog' after hashing?

A 2

B 4

C 6

D 0

💡 Hint

Check step 3 in the execution_table where 'dog' is hashed.

At which step does the collision occur for the key 'tac'?

A Step 7

B Step 4

C Step 5

D Step 2

💡 Hint

Look at the 'Collision Handling' column in the execution_table.

If the hash function changed to multiply each char code by 2 before summing, what would happen to the index for 'cat'?

A It would be unpredictable without calculation

B It would definitely increase

C It would remain the same

D It would definitely decrease

💡 Hint

You need to recalculate the sum and modulo to know the new index.

Concept Snapshot

Hash Table stores key-value pairs using an array.
A hash function converts keys to array indices.
Collisions happen when different keys map to the same index.
Chaining or open addressing handles collisions.
Modulo operation keeps indices within array size.
Fast average lookup, insert, and delete operations.

Full Transcript

A hash table uses a hash function to convert a key into an index in an array. The example hash function sums ASCII codes of characters and uses modulo to fit the index within the array size. When inserting keys like 'cat' and 'dog', their hash values determine where they go in the array. If two keys like 'cat' and 'tac' produce the same index, a collision occurs. This is handled by chaining, which stores multiple key-value pairs in a linked list at that index. The execution table shows each step of hashing, inserting, and retrieving keys, including collision handling. Variables like hash, index, and the array state change as operations proceed. Key moments clarify why collisions happen, how chaining works, and why modulo is used. The visual quiz tests understanding of these steps and effects of changing the hash function. Overall, hash tables provide fast access by using a hash function to map keys to indices and handling collisions efficiently.

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