HashMap Implementation from Scratch in DSA C# - Build from Scratch

HashMap Implementation from Scratch

📖 Scenario: Imagine you are building a simple phone book application. You want to store names and their phone numbers so you can quickly find a number by a name. To do this efficiently, you will create your own HashMap from scratch.

🎯 Goal: Build a basic HashMap class in C# that can store key-value pairs (name and phone number), add new entries, and retrieve phone numbers by name.

📋 What You'll Learn

Create a HashMap class with an internal array of buckets

Implement a simple hash function to convert keys to bucket indices

Add a method to insert key-value pairs

Add a method to retrieve values by key

Handle collisions using chaining (linked lists)

💡 Why This Matters

🌍 Real World

HashMaps are used in many applications like phone books, caches, and databases to quickly find data by keys.

💼 Career

Understanding how HashMaps work internally helps in optimizing code and solving problems efficiently in software development roles.

1

Create the HashMap class and internal buckets

Create a class called HashMap with a private array of LinkedList<KeyValuePair<string, string>> called buckets of size 5. Initialize the array in the constructor.

DSA C#

public class HashMap
{
    // Your code here
}

Hint

Use an array of linked lists to store entries. Initialize the array with size 5 in the constructor.

2

Add a hash function to map keys to bucket indices

Inside the HashMap class, add a private method called GetBucketIndex that takes a string key and returns an int. Use the built-in GetHashCode() method of the key, take its absolute value, and then modulo by the length of buckets to get the index.

DSA C#

using System.Collections.Generic;

public class HashMap
{
    private LinkedList>[] buckets;

    public HashMap()
    {
        buckets = new LinkedList>[5];
    }

    // Add GetBucketIndex method here
    // Your code here
}

Hint

Use GetHashCode() on the key and then use modulo with the buckets array length to find the index.

3

Implement the Add method to insert key-value pairs

Add a public method called Add in the HashMap class that takes string key and string value. Use GetBucketIndex to find the bucket. If the bucket is null, initialize it as a new LinkedList<KeyValuePair<string, string>>. Then add the new KeyValuePair<string, string> to the bucket.

DSA C#

using System.Collections.Generic;

public class HashMap
{
    private LinkedList>[] buckets;

    public HashMap()
    {
        buckets = new LinkedList>[5];
    }

    private int GetBucketIndex(string key)
    {
        int hash = key.GetHashCode();
        int index = System.Math.Abs(hash) % buckets.Length;
        return index;
    }

    // Add Add method here
    // Your code here
}

Hint

Check if the bucket is null before adding. Use AddLast to add the key-value pair to the linked list.

4

Implement the Get method to retrieve values by key

Add a public method called Get in the HashMap class that takes a string key and returns a string. Use GetBucketIndex to find the bucket. If the bucket is null, return null. Otherwise, iterate over the linked list in the bucket. If a KeyValuePair with the matching key is found, return its value. If not found, return null. Then, outside the class, create a HashMap object called phoneBook, add these entries: "Alice" with "12345", "Bob" with "67890", and print the result of phoneBook.Get("Alice").

DSA C#

using System;
using System.Collections.Generic;

public class HashMap
{
    private LinkedList>[] buckets;

    public HashMap()
    {
        buckets = new LinkedList>[5];
    }

    private int GetBucketIndex(string key)
    {
        int hash = key.GetHashCode();
        int index = System.Math.Abs(hash) % buckets.Length;
        return index;
    }

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

    // Add Get method here
    // Your code here
}

// Create phoneBook, add entries, and print Alice's number
// Your code here

Hint

Return null if bucket is empty. Loop through the linked list to find the key and return its value. Then create phoneBook, add entries, and print Alice's number.

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