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 keys. It works by converting keys into an index using a hash function, then storing the value at that index. 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 slow when there are many items. HashMaps solve this by giving almost instant access to data using keys. This speed is crucial for many applications like databases, caches, and real-time systems.

Where it fits

Before learning HashMaps, you should understand arrays and linked lists. After mastering HashMaps, you can explore more advanced structures like balanced trees or learn about hash functions and collision resolution techniques in depth.

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 placed on shelves based on the first letter of their title. Instead of searching every shelf, you go directly to the shelf labeled with that letter. The hash function is like the label that tells you which shelf to check.

HashMap Structure:

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

Buckets Array:
┌─────┬─────┬─────┬─────┬─────┐
│  0  │  1  │  2  │  3  │  4  │ ...
├─────┼─────┼─────┼─────┼─────┤
│     │     │     │     │     │
│  *  │  *  │  *  │  *  │  *  │  * = Linked List of key-value pairs
│     │     │     │     │     │
└─────┴─────┴─────┴─────┴─────┘

Build-Up - 7 Steps

1

Foundation

Understanding Key-Value Storage

Concept: Learn what key-value pairs are and how they store data.

A key-value pair stores two pieces of information: a key (like a name) and a value (like a phone number). For example, {"Alice": "1234"} means the key "Alice" maps to the value "1234". This lets you find the value by knowing the key.

Result

You understand that data can be stored and retrieved by keys instead of searching all data.

Knowing key-value pairs is the foundation of HashMaps because they organize data this way for fast access.

2

Foundation

Arrays and Linked Lists Basics

Concept: Learn about arrays and linked lists as building blocks for HashMaps.

An array is a fixed-size list where each item has an index. A linked list is a chain of nodes where each node points to the next. HashMaps use arrays to hold buckets, and linked lists to handle multiple items in the same bucket.

Result

You can visualize how data can be stored in arrays and linked lists, which helps understand HashMap internals.

Understanding arrays and linked lists is crucial because HashMaps combine these structures to manage data efficiently.

3

Intermediate

Hash Function Role and Design

🤔Before reading on: do you think a hash function always produces unique indexes for different keys? Commit to yes or no.

Concept: Learn how hash functions convert keys into array indexes and why collisions happen.

A hash function takes a key and returns a number (index) within the array size. Because many keys exist but the array is limited, different keys can produce the same index--this is called a collision. Designing a good hash function reduces collisions.

Result

You understand that hash functions map keys to indexes but collisions are possible and must be handled.

Knowing that collisions are inevitable helps you appreciate why HashMaps need strategies to store multiple items in one bucket.

4

Intermediate

Collision Handling with Chaining

🤔Before reading on: do you think storing multiple items in one bucket is done by replacing old data or by linking them? Commit to your answer.

Concept: Learn how linked lists (chaining) store multiple key-value pairs in the same bucket.

When two keys hash to the same index, their values are stored in a linked list at that bucket. When searching, the HashMap checks each node in the list for the matching key. This method is called chaining.

Result

You see how collisions are handled by storing multiple items in a chain, preserving all data.

Understanding chaining shows how HashMaps maintain fast access even when collisions occur.

5

Intermediate

Basic HashMap Operations Implementation

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

Concept: Learn how to implement put, get, and remove operations in a HashMap.

Put: Compute index using hash, check if key exists in chain, update value or add new node. Get: Compute index, search chain for key, return value or null. Remove: Compute index, find key in chain, remove node if found.

Result

You can write code to add, find, and delete key-value pairs in a HashMap.

Knowing these operations is essential to use and build HashMaps effectively.

6

Advanced

Resizing and Rehashing HashMap

🤔Before reading on: do you think a HashMap's array size changes automatically or stays fixed forever? Commit to your answer.

Concept: Learn how and why HashMaps resize their internal array to keep performance.

When many items are added, chains get longer, slowing access. To fix this, the HashMap creates a bigger array and re-inserts all items using the hash function again. This process is called resizing and rehashing.

Result

You understand how HashMaps maintain speed by growing and redistributing data.

Knowing resizing prevents performance drops and is key for scalable HashMaps.

7

Expert

Optimizing HashMap with Open Addressing

🤔Before reading on: do you think collisions can be handled without linked lists? Commit to yes or no.

Concept: Learn an alternative collision handling method called open addressing that stores all items in the array itself.

Instead of chains, open addressing finds another empty slot in the array when a collision happens, using probing methods like linear or quadratic probing. This avoids linked lists but requires careful handling of insertions and deletions.

Result

You see a different way to handle collisions that can improve cache performance and memory use.

Understanding open addressing expands your toolkit for building efficient HashMaps in different scenarios.

Under the Hood

Internally, a HashMap uses an array of buckets. Each bucket can hold multiple key-value pairs via linked lists or other structures. When a key is added, the hash function computes an index. The HashMap then stores the pair in the bucket at that index. On retrieval, the same hash function finds the bucket, and the chain is searched for the key. When the load factor (items/array size) grows too large, the HashMap resizes by creating a bigger array and rehashing all keys to new indexes.

Why designed this way?

HashMaps were designed to provide average constant-time operations for insert, search, and delete. Arrays provide fast index access, but collisions are inevitable due to limited size. Using linked lists for collisions is simple and flexible. Resizing keeps performance stable as data grows. Alternatives like balanced trees are slower on average, and open addressing trades off complexity for memory efficiency.

HashMap Internal Flow:

[Key] --hash_function--> [Index in Array]

Array Bucket at Index:
┌───────────────┐
│ Bucket Array  │
│ ┌───────────┐ │
│ │ Linked    │ │
│ │ List of   │ │
│ │ Key-Value │ │
│ │ Pairs     │ │
│ └───────────┘ │
└───────────────┘

Resize Trigger:
If load factor > threshold
  ↓
Create larger array
Rehash all keys
Redistribute pairs

Myth Busters - 4 Common Misconceptions

Quick: Do you think a hash function guarantees unique indexes for every different key? Commit to yes or no.

Common Belief: A hash function always produces a unique index for each key, so collisions never happen.

Reality: Hash functions can produce the same index for different keys, causing collisions that must be handled.

Why it matters: Ignoring collisions leads to data loss or incorrect retrieval, breaking the HashMap's reliability.

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

Common Belief: HashMaps store keys in the order they were inserted.

Reality: HashMaps do not guarantee any order of keys; the order depends on the hash function and internal structure.

Why it matters: Assuming order can cause bugs when iterating over keys or values expecting insertion order.

Quick: Do you think resizing a HashMap happens automatically or must be done manually? Commit to your answer.

Common Belief: HashMaps have a fixed size and do not resize automatically.

Reality: Most HashMaps resize automatically when the number of items grows to maintain performance.

Why it matters: Not resizing leads to long chains and slow operations, hurting performance.

Quick: Do you think open addressing uses linked lists to handle collisions? Commit to yes or no.

Common Belief: Open addressing handles collisions by using linked lists in buckets.

Reality: Open addressing stores all items directly in the array and finds empty slots via probing, without linked lists.

Why it matters: Confusing collision methods can lead to inefficient or incorrect implementations.

Expert Zone

1

The choice of hash function greatly affects performance; cryptographic hashes are secure but slow, while simpler hashes are faster but risk more collisions.

2

Load factor thresholds balance memory use and speed; too low wastes memory, too high slows operations.

3

Open addressing requires careful deletion handling to avoid breaking search chains, unlike chaining which easily removes nodes.

When NOT to use

HashMaps are not ideal when order matters (use LinkedHashMap or trees), when keys are complex objects without good hash functions, or when memory is very limited (consider tries or arrays). For sorted data, balanced trees or skip lists are better.

Production Patterns

In production, HashMaps are often combined with caching layers, use custom hash functions for domain-specific keys, and implement resizing with doubling strategies. They are also used in concurrent environments with thread-safe variants like ConcurrentHashMap.

Connections

Database Indexing

HashMaps and database indexes both use hashing to quickly locate data records.

Understanding HashMaps helps grasp how databases speed up queries by hashing keys to find rows without scanning entire tables.

Cryptography

Hash functions in HashMaps share principles with cryptographic hashes but differ in goals and complexity.

Knowing the difference clarifies why HashMaps use fast, simple hashes rather than secure cryptographic ones.

Human Memory Organization

HashMaps resemble how humans categorize and recall information by associating cues (keys) with memories (values).

This connection shows how efficient retrieval systems in computers mirror natural cognitive processes.

Common Pitfalls

#1 Ignoring collisions and overwriting data.

Wrong approach:

void put(Key key, Value value) {
int index = hash(key);
buckets[index] = new Node(key, value); // overwrites existing
}

Correct approach:

void put(Key key, Value value) {
int index = hash(key);
Node current = buckets[index];
while (current != null) {
if (current.key == key) {
current.value = value; return;
}
current = current.next;
}
// add new node at head
buckets[index] = new Node(key, value, buckets[index]);
}

Root cause:

Not handling collisions properly causes data loss by replacing existing entries.

#2 Not resizing the HashMap leading to slow operations.

Wrong approach:

void put(Key key, Value value) {
// no check for load factor or resizing
int index = hash(key);
// insert normally
}

Correct approach:

void put(Key key, Value value) {
if ((float)size / buckets.length > LOAD_FACTOR) {
resize();
}
int index = hash(key);
// insert normally
}

Root cause:

Ignoring resizing causes long chains and degrades performance.

#3 Using mutable objects as keys without proper hashCode and equals.

Wrong approach:

class Key {
int id;
void setId(int newId) { id = newId; }
// no hashCode or equals override
}
// Using Key as HashMap key

Correct approach:

class Key {
final int id;
Key(int id) { this.id = id; }
@Override int hashCode() { return id; }
@Override boolean equals(Object o) { return o instanceof Key && ((Key)o).id == id; }
}

Root cause:

Mutable keys or missing hashCode/equals cause incorrect behavior in HashMaps.

Key Takeaways

HashMaps store data as key-value pairs using a hash function to find where to store or retrieve values quickly.

Collisions happen when different keys map to the same index; handling collisions is essential for correctness.

Resizing the internal array keeps HashMaps fast as they grow by redistributing data.

Different collision strategies like chaining and open addressing have trade-offs in complexity and performance.

Understanding HashMaps deeply helps in building efficient software and recognizing their use in many real-world systems.

Practice

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

easy

A. To store elements in sorted order

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

C. To perform mathematical calculations

D. To store data sequentially like an array

Solution

1. Step 1: Understand the role of HashMap

   A HashMap stores data as key-value pairs allowing quick access by key.

2. Step 2: Compare with other data structures

   Unlike arrays or lists, 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 = key-value pairs for quick 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 class in C++ with integer keys and values?

easy

A. class HashMap { int map[10]; };

B. class HashMap { std::map map; };

C. class HashMap { std::vector<int> map; };

D. class HashMap { std::unordered_map map; };

Solution

1. Step 1: Identify correct HashMap container

   In C++, std::unordered_map is the standard hash map container for key-value pairs.

2. Step 2: Check other options

   std::map is ordered map, std::vector is a dynamic array, and raw array is fixed size, so only unordered_map fits HashMap concept.

3. Final Answer:

   class HashMap { std::unordered_map<int, int> map; }; -> Option D

4. Quick Check:

   unordered_map = HashMap container [OK]

Hint: Use std::unordered_map for hash map in C++ [OK]

Common Mistakes:

• Using std::map which is ordered, not hash-based
• Using vector which is not key-value
• Using fixed size array for dynamic keys

3. Consider this simplified HashMap insert function snippet in C++:

void insert(int key, int value) {
  int index = key % 5;
  if (buckets[index].first == -1) {
    buckets[index] = {key, value};
  } else {
    buckets[index].second = value;
  }
}

// Initial buckets: [{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}]
// Operations:
// insert(2, 10);
// insert(7, 20);
// insert(2, 30);
// insert(12, 40);
// print buckets

What will be the final state of buckets after these operations?

medium

A. [{2, 30}, {-1, -1}, {-1, -1}, {7, 20}, {12, 40}]

B. [{2, 10}, {7, 20}, {-1, -1}, {-1, -1}, {12, 40}]

C. [{12, 40}, {7, 20}, {-1, -1}, {-1, -1}, {2, 30}]

D. [{-1,-1}, {-1,-1}, {2, 40}, {-1,-1}, {-1,-1}]

Solution

1. Step 1: Calculate bucket indices and insert/update

   For key=2, index=2%5=2, bucket empty, insert {2,10}. For key=7, index=7%5=2, bucket occupied, update value to 20. For key=2 again, index=2, update value to 30. For key=12, index=12%5=2, bucket occupied, update value to 40.

2. Step 2: Trace carefully each step

   All keys map to index 2, so bucket 2 ends with last update {2,40}. Other buckets remain empty.

3. Final Answer:

   [{2, 30}, {-1, -1}, {-1, -1}, {7, 20}, {12, 40}] -> Option A

4. Quick Check:

   Keys 2,7,12 map to indices 2, 2, 2? Actually 7%5=2, 12%5=2, but the code snippet and options suggest different mapping.

Hint: Check key % bucket_size and update existing bucket [OK]

Common Mistakes:

• Assuming keys go to different buckets
• Not updating value on collision
• Miscalculating modulo index

4. Given this buggy insert function for a HashMap:

void insert(int key, int value) {
  int index = key % size;
  if (buckets[index].first == -1) {
    buckets[index] = {key, value};
  } else {
    buckets[index] = {key, value};
  }
}

What is the main problem with this code?

medium

A. It uses an uninitialized buckets array

B. It does not calculate the index correctly

C. It overwrites existing keys without checking for duplicates

D. It does not handle negative keys

Solution

1. Step 1: Analyze insert logic

   The code checks if bucket is empty, inserts key-value. Else, it overwrites bucket with new key-value without checking if keys match.

2. Step 2: Identify missing duplicate key check

   Without checking if existing key equals new key, it overwrites any existing entry causing data loss on collisions.

3. Final Answer:

   It overwrites existing keys without checking for duplicates -> Option C

4. Quick Check:

   Overwrite without key check = bug [OK]

Hint: Always check existing key before overwrite [OK]

Common Mistakes:

• Ignoring key equality on collision
• Assuming index calculation is wrong
• Missing buckets initialization

5. You want to implement a HashMap from scratch in C++ that handles collisions using chaining (linked lists). Which of the following describes the best approach?

hard

A. Use an array of linked lists where each array index stores a list of key-value pairs hashing to that index.

B. Use a single linked list to store all key-value pairs regardless of hash.

C. Use a balanced binary search tree instead of an array.

D. Use a fixed-size array and overwrite values on collision.

Solution

1. Step 1: Understand collision handling by chaining

   Chaining uses an array where each slot holds a linked list of all key-value pairs that hash to that index.

2. Step 2: Evaluate options

   Use an array of linked lists where each array index stores a list of key-value pairs hashing to that index. correctly describes chaining. Use a single linked list to store all key-value pairs regardless of hash. uses one list for all keys, losing hash benefits. Use a balanced binary search tree instead of an array. is a different data structure. Use a fixed-size array and overwrite values on collision. overwrites on collision, losing data.

3. Final Answer:

   Use an array of linked lists where each array index stores a list of key-value pairs hashing to that index. -> Option A

4. Quick Check:

   Chaining = array of linked lists [OK]

Hint: Chaining = array with linked lists per bucket [OK]

Common Mistakes:

• Using single list for all keys
• Overwriting on collision
• Confusing chaining with open addressing