Hash Table Concept and Hash Functions in DSA C# - Time & Space Complexity

Time Complexity: Hash Table Concept and Hash Functions

O(1) average, O(n) worst

Understanding Time Complexity

We want to understand how fast a hash table can find or store data using a hash function.

How does the time to do these operations change as we add more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public class SimpleHashTable
{
    private readonly int size = 10;
    private readonly LinkedList<KeyValuePair<int, string>>[] buckets;

    public SimpleHashTable()
    {
        buckets = new LinkedList<KeyValuePair<int, string>>[size];
    }

    private int HashFunction(int key) => key % size;

    public void Add(int key, string value)
    {
        int index = HashFunction(key);
        if (buckets[index] == null)
            buckets[index] = new LinkedList<KeyValuePair<int, string>>();
        buckets[index].AddLast(new KeyValuePair<int, string>(key, value));
    }

    public string Get(int key)
    {
        int index = HashFunction(key);
        var bucket = buckets[index];
        if (bucket != null)
        {
            foreach (var pair in bucket)
            {
                if (pair.Key == key)
                    return pair.Value;
            }
        }
        return null;
    }
}
    

This code creates a simple hash table that stores and retrieves key-value pairs in buckets using a hash function.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing a bucket list (foreach loop in Get) after computing the hash index.
• How many times: The hash function runs once per operation; traversal length grows with collisions in the bucket.

How Execution Grows With Input

As we add more items, the number of collisions may increase, making linked lists longer.

Input Size (n)	Approx. Operations
10	About 1 operation per lookup (few collisions)
100	Operations grow as some buckets get longer lists
1000	More collisions cause longer lists, more operations per lookup

Pattern observation: Operations grow roughly linearly with input if collisions increase; otherwise, they stay close to constant.

Final Time Complexity

Time Complexity: O(1) on average, O(n) in worst case

This means usually adding or finding an item is very fast, but if many keys collide, it can slow down to checking many items.

Common Mistake

[X] Wrong: "Hash tables always work in constant time no matter what."

[OK] Correct: If many keys hash to the same bucket, operations slow down because we must check many items in that bucket.

Interview Connect

Understanding hash tables and their time complexity shows you know how data can be stored and found quickly in many real programs.

Self-Check

"What if we used a better hash function that spreads keys evenly? How would the time complexity change?"

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