HashMap Implementation from Scratch in DSA C# - Deep Dive

Overview - HashMap Implementation from Scratch

What is it?

A HashMap is a data structure that stores key-value pairs. It allows you to quickly find, add, or remove values using a key. Internally, it uses a function called a hash function to decide where to store each pair. This makes searching very fast compared to looking through all items one by one.

Why it matters

Without HashMaps, programs would have to search through lists or arrays to find data, which can be very slow as data grows. HashMaps make data access almost instant, improving performance in many applications like databases, caches, and real-time systems. They help software run faster and handle more data efficiently.

Where it fits

Before learning HashMaps, you should understand arrays and basic data structures like lists. After mastering HashMaps, you can explore more advanced structures like Trees, Graphs, and specialized hash-based structures like HashSets or LRU caches.

Mental Model

Core Idea

A HashMap uses a hash function to turn keys into indexes, storing values in buckets for fast access.

Think of it like...

Imagine a library where books are stored by their unique code. Instead of searching every shelf, you use the code to find the exact shelf and spot quickly.

HashMap Structure:

[Key] --hash_function--> [Index]

Buckets Array:
+-------+-------+-------+-------+
| Bucket| Bucket| Bucket| Bucket|
|  0    |  1    |  2    |  3    |
+-------+-------+-------+-------+
   |        |       |       |
  List    List    List    List
  of      of      of      of
 Entries Entries Entries Entries
 (key,value) pairs stored here

Build-Up - 7 Steps

1

Foundation

Understanding Key-Value Storage

Concept: Learn what key-value pairs are and why they are useful.

A key-value pair stores two pieces of information together: a key (like a name) and a value (like a phone number). You can think of it like a dictionary where you look up a word (key) to find its meaning (value). This lets you find information quickly if you know the key.

Result

You understand how data can be organized as pairs for easy lookup.

Knowing key-value pairs is the base for all map-like data structures, making data retrieval intuitive and fast.

2

Foundation

What is a Hash Function?

Concept: Introduce the hash function that converts keys into numbers.

A hash function takes a key and turns it into a number called a hash code. This number helps decide where to store the value in an array. For example, the key 'apple' might become 123, and 'banana' might become 456. The hash function should spread keys evenly to avoid crowding.

Result

You see how keys become indexes to store values efficiently.

Understanding hashing is crucial because it transforms complex keys into simple numbers for quick access.

3

Intermediate

Handling Collisions with Buckets

🤔Before reading on: do you think two different keys can share the same storage spot? Commit to yes or no.

Concept: Learn how to handle cases when two keys produce the same hash index.

Sometimes, two different keys get the same hash code. This is called a collision. To handle collisions, each bucket in the array holds a list of entries. When adding a new key-value pair, if the bucket already has entries, we add the new pair to the list. When searching, we check each entry in the list for the matching key.

Result

You understand how collisions are managed to keep the HashMap working correctly.

Knowing collision handling prevents confusion about why multiple items can share one spot and how to still find the right one.

4

Intermediate

Implementing Basic HashMap Operations

🤔Before reading on: do you think adding a key that already exists replaces the old value or adds a new entry? Commit to your answer.

Concept: Learn how to add, get, and remove key-value pairs in the HashMap.

To add a pair, compute the hash index, go to the bucket, and check if the key exists. If yes, update the value; if no, add a new entry. To get a value, compute the hash index, search the bucket list for the key, and return the value. To remove, find the key in the bucket and delete it.

Result

You can perform all main operations on a HashMap correctly.

Understanding these operations builds the foundation for using and implementing efficient data storage.

5

Intermediate

Resizing the HashMap Dynamically

🤔Before reading on: do you think a fixed-size HashMap can handle unlimited data without performance loss? Commit to yes or no.

Concept: Learn why and how to increase the HashMap size when it gets full.

When many entries fill the HashMap, buckets get crowded, slowing down operations. To fix this, we create a bigger array and rehash all existing entries into it. This process is called resizing. It keeps the load factor (entries per bucket) low, maintaining fast access.

Result

You understand how resizing keeps the HashMap efficient as it grows.

Knowing resizing prevents performance degradation and explains why HashMaps sometimes take longer during insertions.

6

Advanced

Optimizing Hash Functions and Load Factor

🤔Before reading on: do you think any hash function works equally well for all key types? Commit to yes or no.

Concept: Explore how choosing a good hash function and load factor affects performance.

A good hash function spreads keys evenly to avoid collisions. Poor hash functions cause many collisions, slowing down the HashMap. The load factor is the ratio of entries to buckets; a lower load factor means fewer collisions but more memory use. Balancing these improves speed and memory efficiency.

Result

You see how hash function quality and load factor tuning impact HashMap behavior.

Understanding these optimizations helps build faster and more memory-friendly HashMaps.

7

Expert

Advanced Collision Resolution and Thread Safety

🤔Before reading on: do you think HashMaps are safe to use from multiple threads without extra care? Commit to yes or no.

Concept: Learn about alternative collision methods and making HashMaps safe for concurrent use.

Besides chaining (lists in buckets), collision can be handled by open addressing, which finds another empty bucket. Also, in multi-threaded programs, simultaneous access can cause errors. To fix this, synchronization or concurrent data structures are used. Some HashMaps use lock-free algorithms or segment locking for better performance.

Result

You understand advanced collision methods and concurrency concerns in HashMaps.

Knowing these internals prepares you for building or using HashMaps in complex, real-world systems.

Under the Hood

A HashMap uses a hash function to convert keys into integer indexes. These indexes point to buckets in an internal array. Each bucket holds a list of entries to handle collisions. When adding or searching, the hash function directs to the bucket, and the list is scanned for the key. When the array fills beyond a threshold, it resizes and rehashes all entries to maintain speed.

Why designed this way?

HashMaps were designed to provide average constant-time complexity for insertions, lookups, and deletions. Using arrays for direct access is fast, but collisions are inevitable, so chaining or open addressing solves this. Resizing balances memory use and speed. This design trades some memory for very fast access, which was a major improvement over linear searches.

+-------------------+
|   Hash Function   |
+---------+---------+
          |
          v
+-------------------+
|   Index (bucket)   |----> [Entry List] -> (key,value) -> next
+-------------------+
          |
          v
+-------------------+
|    Internal Array  |
+-------------------+
          |
          v
+-------------------+
|   Resize & Rehash  |
+-------------------+

Myth Busters - 4 Common Misconceptions

Quick: do you think HashMaps keep keys in the order they were added? Commit to yes or no.

Common Belief: HashMaps always keep the order of keys as they were inserted.

Reality: Standard HashMaps do not guarantee any order of keys; the order can change after resizing or rehashing.

Why it matters: Assuming order can cause bugs when order matters, leading to unexpected results or data loss.

Quick: do you think a perfect hash function exists for all key types? Commit to yes or no.

Common Belief: A perfect hash function can avoid all collisions for any set of keys.

Reality: Perfect hash functions exist only for fixed, known key sets. For general use, collisions are unavoidable.

Why it matters: Expecting perfect hashing leads to ignoring collision handling, causing errors and slowdowns.

Quick: do you think HashMaps are safe to use from multiple threads without locks? Commit to yes or no.

Common Belief: HashMaps can be safely used by multiple threads at the same time without extra synchronization.

Reality: Most HashMaps are not thread-safe and require locks or special concurrent versions to avoid data corruption.

Why it matters: Ignoring thread safety causes race conditions, crashes, or corrupted data in multi-threaded programs.

Quick: do you think resizing a HashMap happens every time you add a new item? Commit to yes or no.

Common Belief: HashMaps resize their internal array every time a new key-value pair is added.

Reality: Resizing happens only when the load factor threshold is exceeded, not on every insertion.

Why it matters: Misunderstanding resizing frequency can lead to inefficient implementations or performance surprises.

Expert Zone

1

The choice between chaining and open addressing affects cache performance and memory usage in subtle ways.

2

Load factor thresholds are often tuned based on expected usage patterns to balance speed and memory.

3

Concurrent HashMaps use complex locking or lock-free algorithms that trade off throughput and latency.

When NOT to use

HashMaps are not ideal when key order matters (use LinkedHashMap or TreeMap), when keys are mutable, or when memory is extremely limited (use arrays or tries). For concurrent access, use specialized concurrent maps instead of plain HashMaps.

Production Patterns

In production, HashMaps are used for caches, symbol tables, and indexing. They are often combined with eviction policies for memory control and wrapped with synchronization for thread safety. Hash functions are chosen or customized based on key types and distribution.

Connections

Trie (Prefix Tree)

Both store key-value pairs but use different structures; tries use tree paths, HashMaps use hashing.

Understanding HashMaps helps appreciate how tries optimize prefix searches, showing different trade-offs in key storage.

Database Indexing

HashMaps are a foundational concept behind hash-based database indexes for fast data retrieval.

Knowing HashMaps clarifies how databases quickly locate records without scanning entire tables.

Human Memory Recall

HashMaps mimic how the brain quickly recalls information by associating cues (keys) with memories (values).

This connection shows how computer science models natural processes to solve data retrieval efficiently.

Common Pitfalls

#1 Ignoring collision handling leads to lost or overwritten data.

Wrong approach:

Storing values directly at hash index without checking for existing entries or collisions.

Correct approach:

Use a list or another structure at each bucket to store multiple entries and check keys before adding.

Root cause:

Misunderstanding that different keys can produce the same hash index.

#2 Not resizing the HashMap causes slow operations as it fills up.

Wrong approach:

Fixed-size array without rehashing when load factor grows.

Correct approach:

Implement resizing by creating a larger array and rehashing all entries when threshold is reached.

Root cause:

Not realizing that performance depends on maintaining low load factor.

#3 Using mutable objects as keys without proper hash and equality methods causes incorrect behavior.

Wrong approach:

Using objects that change state as keys without overriding GetHashCode and Equals properly.

Correct approach:

Use immutable keys or correctly implement hash and equality methods to ensure consistent behavior.

Root cause:

Not understanding how keys are identified and stored internally.

Key Takeaways

HashMaps store data as key-value pairs using a hash function to find storage locations quickly.

Collisions happen when different keys map to the same spot; handling them correctly is essential for accuracy.

Resizing the internal array keeps operations fast as the number of entries grows.

Choosing good hash functions and managing load factor balance speed and memory use.

Thread safety and advanced collision methods are important for real-world, multi-threaded applications.

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