HashMap Implementation from Scratch in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this HashMap put and get operations?

Consider a simple HashMap implemented with separate chaining. After inserting keys and values, what will be the output of the get operation?

DSA C#

var map = new SimpleHashMap();
map.Put("apple", 10);
map.Put("banana", 20);
map.Put("apple", 30);
var result = map.Get("apple");
Console.WriteLine(result);

class SimpleHashMap
{
    private readonly int size = 5;
    private LinkedList<KeyValuePair<string, int>>[] buckets;

    public SimpleHashMap()
    {
        buckets = new LinkedList<KeyValuePair<string, int>>[size];
        for (int i = 0; i < size; i++)
            buckets[i] = new LinkedList<KeyValuePair<string, int>>();
    }

    private int GetBucketIndex(string key)
    {
        return Math.Abs(key.GetHashCode()) % size;
    }

    public void Put(string key, int value)
    {
        int index = GetBucketIndex(key);
        var bucket = buckets[index];
        foreach (var pair in bucket)
        {
            if (pair.Key == key)
            {
                bucket.Remove(pair);
                break;
            }
        }
        bucket.AddLast(new KeyValuePair<string, int>(key, value));
    }

    public int Get(string key)
    {
        int index = GetBucketIndex(key);
        var bucket = buckets[index];
        foreach (var pair in bucket)
        {
            if (pair.Key == key)
                return pair.Value;
        }
        return -1; // Not found
    }
}

A 20

B 10

C -1

D 30

💡 Hint

When inserting a key that already exists, the old value is replaced.

The key "apple" is first inserted with value 10, then updated to 30. The get returns the latest value 30.

❓ Predict Output

intermediate

What is the size of the HashMap after these operations?

Given the following sequence of put and remove operations on a HashMap, what is the final number of key-value pairs stored?

DSA C#

var map = new SimpleHashMap();
map.Put("cat", 1);
map.Put("dog", 2);
map.Put("bird", 3);
map.Remove("dog");
map.Put("cat", 4);
map.Put("fish", 5);
int size = map.Size();
Console.WriteLine(size);

class SimpleHashMap
{
    private readonly int size = 5;
    private LinkedList<KeyValuePair<string, int>>[] buckets;

    public SimpleHashMap()
    {
        buckets = new LinkedList<KeyValuePair<string, int>>[size];
        for (int i = 0; i < size; i++)
            buckets[i] = new LinkedList<KeyValuePair<string, int>>();
    }

    private int GetBucketIndex(string key)
    {
        return Math.Abs(key.GetHashCode()) % size;
    }

    public void Put(string key, int value)
    {
        int index = GetBucketIndex(key);
        var bucket = buckets[index];
        foreach (var pair in bucket)
        {
            if (pair.Key == key)
            {
                bucket.Remove(pair);
                break;
            }
        }
        bucket.AddLast(new KeyValuePair<string, int>(key, value));
    }

    public void Remove(string key)
    {
        int index = GetBucketIndex(key);
        var bucket = buckets[index];
        KeyValuePair<string, int>? toRemove = null;
        foreach (var pair in bucket)
        {
            if (pair.Key == key)
            {
                toRemove = pair;
                break;
            }
        }
        if (toRemove != null)
            bucket.Remove(toRemove.Value);
    }

    public int Size()
    {
        int count = 0;
        foreach (var bucket in buckets)
            count += bucket.Count;
        return count;
    }
}

A 2

B 4

C 3

D 5

💡 Hint

Remember that updating a key does not increase size, and removing a key decreases size.

Keys after operations: "cat" (updated), "bird", "fish". "dog" was removed. So total 3 keys.

🔧 Debug

advanced

Why does this HashMap implementation cause a runtime error?

Examine the code below. When calling Get for a key not present, it throws an exception. What is the cause?

DSA C#

public int Get(string key)
{
    int index = GetBucketIndex(key);
    var bucket = buckets[index];
    foreach (var pair in bucket)
    {
        if (pair.Key == key)
            return pair.Value;
    }
    return bucket.First.Value; // Problematic line
}

A Returns wrong value because bucket.First is always the last inserted pair

B Throws InvalidOperationException when bucket is empty because bucket.First is null

C Causes infinite loop because bucket is modified during iteration

D Returns -1 but should throw KeyNotFoundException

💡 Hint

What happens if the bucket has no elements?

If the bucket is empty, bucket.First is null and accessing .Value throws InvalidOperationException.

🧠 Conceptual

advanced

What is the main advantage of using separate chaining in HashMap?

Separate chaining is a collision resolution technique in HashMaps. What is its main advantage compared to open addressing?

A It handles collisions by storing multiple elements in a linked list, allowing unlimited collisions without rehashing

B It uses less memory because it stores only one element per bucket

C It guarantees O(1) lookup time even in worst case

D It avoids the need for hash functions

💡 Hint

Think about how collisions are stored in separate chaining.

Separate chaining stores collided elements in linked lists, so buckets can hold multiple items, avoiding immediate rehashing.

🚀 Application

expert

What is the output after these complex HashMap operations?

Given the following sequence of operations on a HashMap implemented with separate chaining, what will be printed?

DSA C#

var map = new SimpleHashMap();
map.Put("a", 1);
map.Put("b", 2);
map.Put("c", 3);
map.Put("d", 4);
map.Remove("b");
map.Put("e", 5);
map.Put("a", 10);
map.Remove("f");

var keys = map.GetAllKeys();
Console.WriteLine(string.Join(",", keys));

class SimpleHashMap
{
    private readonly int size = 3;
    private LinkedList<KeyValuePair<string, int>>[] buckets;

    public SimpleHashMap()
    {
        buckets = new LinkedList<KeyValuePair<string, int>>[size];
        for (int i = 0; i < size; i++)
            buckets[i] = new LinkedList<KeyValuePair<string, int>>();
    }

    private int GetBucketIndex(string key)
    {
        return Math.Abs(key.GetHashCode()) % size;
    }

    public void Put(string key, int value)
    {
        int index = GetBucketIndex(key);
        var bucket = buckets[index];
        foreach (var pair in bucket)
        {
            if (pair.Key == key)
            {
                bucket.Remove(pair);
                break;
            }
        }
        bucket.AddLast(new KeyValuePair<string, int>(key, value));
    }

    public void Remove(string key)
    {
        int index = GetBucketIndex(key);
        var bucket = buckets[index];
        KeyValuePair<string, int>? toRemove = null;
        foreach (var pair in bucket)
        {
            if (pair.Key == key)
            {
                toRemove = pair;
                break;
            }
        }
        if (toRemove != null)
            bucket.Remove(toRemove.Value);
    }

    public List<string> GetAllKeys()
    {
        var keys = new List<string>();
        foreach (var bucket in buckets)
        {
            foreach (var pair in bucket)
                keys.Add(pair.Key);
        }
        return keys;
    }
}

A a,c,d,e

B c,d,e,a

C a,d,e,c

D d,c,e,a

💡 Hint

Check bucket indices and insertion order carefully.

Keys stored after operations are "a", "c", "d", "e" in that order by bucket traversal.

Practice

1. What is the main purpose of a HashMap in data structures?

easy

A. To store data sequentially like a list

B. To store key-value pairs for fast data retrieval

C. To store data in a sorted order

D. To perform mathematical calculations

Solution

1. Step 1: Understand the role of HashMap

   A HashMap stores data as key-value pairs, allowing quick access to values using keys.

2. Step 2: Compare with other data structures

   Unlike lists or arrays, HashMaps do not store data sequentially or sorted but focus on fast lookup.

3. Final Answer:

   To store key-value pairs for fast data retrieval -> Option B

4. Quick Check:

   HashMap = key-value fast access [OK]

Hint: HashMap = fast key to value lookup [OK]

Common Mistakes:

• Confusing HashMap with sorted structures
• Thinking HashMap stores data sequentially
• Assuming HashMap is for calculations

2. Which of the following is the correct way to declare a simple HashMap in C# using generics?

easy

A. Hashtable map = new Hashtable();

B. HashMap map = new HashMap();

C. Map map = new Map();

D. Dictionary map = new Dictionary();

Solution

1. Step 1: Recall C# standard HashMap equivalent

   In C#, Dictionary<K,V> is the built-in generic collection similar to HashMap.

2. Step 2: Check syntax correctness

   Dictionary map = new Dictionary(); correctly declares a Dictionary with int keys and string values.

3. Final Answer:

   Dictionary map = new Dictionary(); -> Option D

4. Quick Check:

   C# HashMap = Dictionary [OK]

Hint: Use Dictionary for HashMap in C# [OK]

Common Mistakes:

• Using non-existent HashMap class in C#
• Confusing Hashtable with generic Dictionary
• Wrong generic syntax

3. Consider this simple HashMap implementation snippet in C#:

class SimpleHashMap {
  private int[] keys = new int[5];
  private string[] values = new string[5];

  public void Put(int key, string value) {
    int index = key % 5;
    keys[index] = key;
    values[index] = value;
  }

  public string Get(int key) {
    int index = key % 5;
    if (keys[index] == key) return values[index];
    return null;
  }
}

SimpleHashMap map = new SimpleHashMap();
map.Put(1, "One");
map.Put(6, "Six");
string result = map.Get(1);

What is the value of result after this code runs?

medium

A. null

B. "One"

C. "Six"

D. Runtime error

Solution

1. Step 1: Calculate index for key 1

   Index = 1 % 5 = 1. So keys[1] = 1, values[1] = "One".

2. Step 2: Calculate index for key 6

   Index = 6 % 5 = 1. This overwrites keys[1] = 6, values[1] = "Six".

3. Step 3: Get value for key 1

   Index = 1 % 5 = 1. keys[1] is now 6, not 1, so Get returns null.

4. Final Answer:

   null -> Option A

5. Quick Check:

   Collision overwrites key 1, so Get(1) = null [OK]

Hint: Check key collision and overwrite in simple hash arrays [OK]

Common Mistakes:

• Ignoring key collision overwrite
• Assuming values are stored separately
• Expecting 'One' despite collision

4. Identify the bug in this simple HashMap Put method and choose the correct fix:

public void Put(int key, string value) {
  int index = key % 5;
  if (keys[index] != key) {
    keys[index] = key;
    values[index] = value;
  }
}

medium

A. Change modulus to key % 10 for bigger array

B. Remove the if check to always overwrite key and value

C. Add linear probing to handle collisions

D. Use keys[index] == key instead of != in if condition

Solution

1. Step 1: Understand current behavior

   The if (keys[index] != key) inserts only if the existing key differs: overwrites on collisions (data loss for previous keys) and skips updates for matching keys.

2. Step 2: Identify collision handling

   Without collision handling like linear probing, new keys that hash to occupied slots overwrite existing data.

3. Step 3: Fix by adding linear probing

   Linear probing searches next slots to find an empty or matching key slot, preventing overwrites.

4. Final Answer:

   Add linear probing to handle collisions -> Option C

5. Quick Check:

   Collision fix = linear probing [OK]

Hint: Handle collisions with probing, not just overwrite [OK]

Common Mistakes:

• Removing if causes overwrites
• Changing modulus without resizing array
• Wrong if condition logic

5. You want to implement a HashMap from scratch in C# that supports storing string keys and integer values. Which approach correctly handles collisions and allows retrieval of values?

class MyHashMap {
  private List>[] buckets;
  private int size = 10;

  public MyHashMap() {
    buckets = new List>[size];
    for (int i = 0; i < size; i++) buckets[i] = new List>();
  }

  private int GetBucketIndex(string key) {
    return Math.Abs(key.GetHashCode()) % size;
  }

  public void Put(string key, int value) {
    int index = GetBucketIndex(key);
    var bucket = buckets[index];
    for (int i = 0; i < bucket.Count; i++) {
      if (bucket[i].Key == key) {
        bucket[i] = new KeyValuePair(key, value);
        return;
      }
    }
    bucket.Add(new KeyValuePair(key, value));
  }

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

MyHashMap map = new MyHashMap();
map.Put("apple", 5);
map.Put("banana", 3);
map.Put("apple", 10);
int? val = map.Get("apple");

What is the value of val after this code runs?

hard

A. 10

B. 5

C. 3

D. null

Solution

1. Step 1: Understand Put method behavior

   When inserting "apple" the second time, the code finds the existing key and updates its value to 10.

2. Step 2: Understand Get method behavior

   Get("apple") searches the bucket and returns the updated value 10.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Updated value for "apple" = 10 [OK]

Hint: Update existing key value, else add new pair [OK]

Common Mistakes:

• Returning old value instead of updated
• Ignoring collision handling with buckets
• Returning null if key exists