Hash Table Concept and Hash Functions in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a hash table?

A hash table is a data structure that stores key-value pairs. It uses a hash function to convert keys into an index where the value is stored, allowing fast data retrieval.

beginner

What is the role of a hash function in a hash table?

A hash function takes a key and computes an integer index. This index tells where to store or find the value in the hash table.

intermediate

What is a collision in a hash table?

A collision happens when two different keys produce the same index from the hash function. The hash table must handle collisions to store both values correctly.

intermediate

Name two common methods to handle collisions in hash tables.

1. Chaining: Store multiple items in a list at the same index. 2. Open Addressing: Find another empty slot using probing.

intermediate

Why should a hash function distribute keys uniformly?

Uniform distribution reduces collisions and keeps operations like search, insert, and delete fast by spreading keys evenly across the table.

What does a hash function do in a hash table?

A Stores values directly

B Sorts the keys alphabetically

C Converts a key into an index

D Deletes keys automatically

A hash function converts a key into an index to store or find the value.

What is a collision in a hash table?

A When a key is missing

B When a value is duplicated

C When the table is empty

D When two keys map to the same index

A collision occurs when two different keys produce the same index.

Which method stores multiple items at the same index to handle collisions?

A Chaining

B Open Addressing

C Sorting

D Hashing

Chaining stores multiple items in a list at the same index.

Why is uniform distribution important in a hash function?

A To reduce collisions

B To increase collisions

C To slow down search

D To delete keys

Uniform distribution reduces collisions and keeps operations fast.

Which of these is NOT a part of a hash table?

A Index

B Binary tree

C Key-value pairs

D Hash function

Binary tree is a different data structure, not part of a hash table.

Explain how a hash table stores and retrieves data using a hash function.

Think about how you find a book in a library using a catalog number.

Describe what a collision is in a hash table and two ways to handle it.

Imagine two letters arriving at the same mailbox.

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