HashMap Implementation from Scratch in DSA C#

Mental Model

A HashMap stores key-value pairs by turning keys into indexes to quickly find values.

Analogy: Imagine a library where each book has a special code that tells you exactly which shelf and spot to find it, so you don't have to search all shelves.

Buckets array: [0] -> null
               [1] -> null
               [2] -> null
               [3] -> null
               [4] -> null
Each bucket can hold a linked list of entries: key -> value -> next

Dry Run Walkthrough

Input: Insert key-value pairs: (apple, 5), (banana, 3), (grape, 7) into a HashMap with 5 buckets

Goal: Store these pairs so we can quickly find values by keys using hashing and handle collisions

Step 1: Compute hash for 'apple' and find bucket index 0; insert (apple,5) there

[0] -> (apple:5) -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Why: We place the first key-value pair in the bucket given by its hash index

Step 2: Compute hash for 'banana' and find bucket index 1; insert (banana,3) there

[0] -> (apple:5) -> null
[1] -> (banana:3) -> null
[2] -> null
[3] -> null
[4] -> null

Why: Different key hashes to a different bucket, so we add it there

Step 3: Compute hash for 'grape' and find bucket index 0; collision with 'apple', add (grape,7) at head

[0] -> (grape:7) -> (apple:5) -> null
[1] -> (banana:3) -> null
[2] -> null
[3] -> null
[4] -> null

Why: Collision handled by chaining: new entry added at the start of linked list

Result:

[0] -> (grape:7) -> (apple:5) -> null
[1] -> (banana:3) -> null
[2] -> null
[3] -> null
[4] -> null

Annotated Code

DSA C#

using System;

public class HashMap<K, V>
{
    private class Entry
    {
        public K Key;
        public V Value;
        public Entry Next;

        public Entry(K key, V value)
        {
            Key = key;
            Value = value;
            Next = null;
        }
    }

    private Entry[] buckets;
    private int capacity;

    public HashMap(int capacity = 5)
    {
        this.capacity = capacity;
        buckets = new Entry[capacity];
    }

    private int GetBucketIndex(K key)
    {
        int hash = key.GetHashCode();
        int index = Math.Abs(hash) % capacity;
        return index;
    }

    public void Put(K key, V value)
    {
        int index = GetBucketIndex(key);
        Entry head = buckets[index];

        // Check if key exists and update
        Entry curr = head;
        while (curr != null)
        {
            if (curr.Key.Equals(key))
            {
                curr.Value = value; // update existing key
                return;
            }
            curr = curr.Next;
        }

        // Insert new entry at head
        Entry newEntry = new Entry(key, value);
        newEntry.Next = head;
        buckets[index] = newEntry;
    }

    public V Get(K key)
    {
        int index = GetBucketIndex(key);
        Entry curr = buckets[index];
        while (curr != null)
        {
            if (curr.Key.Equals(key))
            {
                return curr.Value;
            }
            curr = curr.Next;
        }
        throw new Exception("Key not found");
    }

    public override string ToString()
    {
        System.Text.StringBuilder sb = new System.Text.StringBuilder();
        for (int i = 0; i < capacity; i++)
        {
            sb.Append("[" + i + "] -> ");
            Entry curr = buckets[i];
            while (curr != null)
            {
                sb.Append("(" + curr.Key + ":" + curr.Value + ") -> ");
                curr = curr.Next;
            }
            sb.Append("null\n");
        }
        return sb.ToString();
    }
}

class Program
{
    static void Main()
    {
        HashMap<string, int> map = new HashMap<string, int>(5);
        map.Put("apple", 5);
        map.Put("banana", 3);
        map.Put("grape", 7);
        Console.Write(map.ToString());
    }
}

int index = GetBucketIndex(key);

Calculate bucket index from key hash

Entry curr = head; while (curr != null) { if (curr.Key.Equals(key)) { curr.Value = value; // update existing key return; } curr = curr.Next; }

Traverse bucket list to find existing key and update value

Entry newEntry = new Entry(key, value); newEntry.Next = head; buckets[index] = newEntry;

Insert new entry at the head of the bucket's linked list

Entry curr = buckets[index]; while (curr != null) { if (curr.Key.Equals(key)) { return curr.Value; } curr = curr.Next; }

Search bucket linked list for key to retrieve value

Output

[0] -> (grape:7) -> (apple:5) -> null

[1] -> (banana:3) -> null

[2] -> null

[3] -> null

[4] -> null

Complexity Analysis

Time: O(n/k) average, where n is number of entries and k is buckets, because each bucket holds a short linked list; worst case O(n) if all keys collide

Space: O(n) because we store all key-value pairs in linked lists inside buckets

vs Alternative: Compared to a simple list that searches all entries O(n), HashMap reduces average search to O(1) by hashing keys to buckets

Edge Cases

Inserting duplicate key

Value is updated in existing entry instead of adding new node

DSA C#

if (curr.Key.Equals(key)) { curr.Value = value; return; }

Getting a key not present

Throws exception 'Key not found'

DSA C#

throw new Exception("Key not found");

Empty HashMap get

Throws exception because bucket is null and no entries found

DSA C#

while (curr != null) { ... } throw new Exception("Key not found");

When to Use This Pattern

When you need fast key-value lookup and see problems mentioning hashing or collisions, reach for HashMap implementation to organize data efficiently.

Common Mistakes

Mistake: Not handling collisions, overwriting entries in buckets
Fix: Use linked list chaining to store multiple entries in the same bucket

Mistake: Not updating value when inserting duplicate key
Fix: Check existing keys in bucket and update value instead of adding new node

Summary

Stores key-value pairs using hashing to quickly find values by keys.

Use when you want fast insert and lookup by key with many entries.

Hash keys to buckets and handle collisions by chaining entries in linked lists.

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