Hash Table Concept and Hash Functions in DSA C# - Build from Scratch

Hash Table Concept and Hash Functions

📖 Scenario: Imagine you are managing a small library. You want to quickly find books by their unique ID numbers. A hash table helps you store and find these books fast by using a special function called a hash function.

🎯 Goal: You will create a simple hash table using an array and a hash function. You will store book IDs and their titles, then retrieve a book title using its ID.

📋 What You'll Learn

Create an array to represent the hash table with a fixed size

Create a hash function that converts a book ID to an index in the array

Store book titles in the hash table using the hash function

Retrieve and print a book title by its ID using the hash function

💡 Why This Matters

🌍 Real World

Hash tables are used in many applications like databases, caches, and dictionaries to quickly find data using keys.

💼 Career

Understanding hash tables and hash functions is important for software developers to write efficient code for searching and storing data.

1

Create the hash table array

Create a string array called hashTable with size 10 to store book titles.

DSA C#

// Create a string array called hashTable with size 10
// Your code here

Hint

Use string[] hashTable = new string[10]; to create the array.

2

Create the hash function

Create a function called HashFunction that takes an int bookId and returns bookId % 10 as the index.

DSA C#

string[] hashTable = new string[10];
// Create HashFunction method below
// Your code here

Hint

The hash function returns the remainder when bookId is divided by 10.

3

Store book titles using the hash function

Use the HashFunction to find the index for book ID 123 and store the title "C# Basics" at that index in hashTable.

DSA C#

string[] hashTable = new string[10];

int HashFunction(int bookId)
{
    return bookId % 10;
}

// Store "C# Basics" at the index for book ID 123
// Your code here

Hint

Call HashFunction(123) and assign the result to index. Then store the title at hashTable[index].

4

Retrieve and print the book title

Use the HashFunction to find the index for book ID 123 and print the book title stored at that index in hashTable.

DSA C#

string[] hashTable = new string[10];

int HashFunction(int bookId)
{
    return bookId % 10;
}

int index = HashFunction(123);
hashTable[index] = "C# Basics";

// Print the book title at the index for book ID 123
// Your code here

Hint

Use Console.WriteLine(hashTable[retrieveIndex]); to print the stored title.

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