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 fast access, insertion, and deletion of values based on their keys. Internally, it uses a function called a hash function to convert keys into indexes in an array. This way, it can quickly find where to store or look up data.

Why it matters

Without HashMaps, programs would need to search through lists or arrays one by one to find data, which is slow. HashMaps make data retrieval almost instant, even with large amounts of data. 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 basic data structures like lists. After mastering HashMaps, you can explore more complex structures like Trees, Graphs, and advanced hashing techniques.

Mental Model

Core Idea

A HashMap uses a hash function to turn keys into array positions, storing values so they can be found quickly without searching the whole collection.

Think of it like...

Imagine a library where each book has a unique code. Instead of searching every shelf, you use the code to go directly to the right shelf and spot. The hash function is like the code translator, and the array is the shelves.

HashMap Structure:

[Array]
  ├─ Index 0: Bucket (Linked List or Tree)
  ├─ Index 1: Bucket
  ├─ Index 2: Bucket
  ├─ ...
  └─ Index N: Bucket

Key --hash_function--> Index

Each bucket holds entries with keys that hash to the same index.

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 linked pieces of data: a key (like a name) and a value (like a phone number). For example, in a phonebook, the name is the key and the phone number is the value. This lets you find the phone number by knowing the name.

Result

You understand that data can be organized by unique keys to quickly find related values.

Knowing key-value pairs is the base for all map-like data structures, including HashMaps.

2

Foundation

Arrays as Storage Backbones

Concept: Learn how arrays store data in fixed positions accessible by index.

An array is a list of items stored in order, each with a number called an index. You can quickly get or set an item by its index. For example, array[0] gets the first item. Arrays are fast but need a way to convert keys to indexes.

Result

You see how arrays provide fast access by position but need a method to map keys to these positions.

Understanding arrays helps grasp why HashMaps use them as the main storage for quick access.

3

Intermediate

Hash Functions: Keys to Indexes

🤔Before reading on: do you think a hash function always gives a unique index for every key? Commit to yes or no.

Concept: Introduce hash functions that convert keys into array indexes.

A hash function takes a key and returns a number (hash code). This number is then turned into an array index by using modulo operation with the array size. For example, hash(key) % array_size gives the index. This lets us store values at that index.

Result

You learn how keys are transformed into positions in the array for storage and lookup.

Knowing hash functions explains how HashMaps achieve fast access without searching.

4

Intermediate

Handling Collisions with Buckets

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

Concept: Learn about collisions and how to store multiple items in one array slot using buckets.

Sometimes, different keys produce the same index; this is called a collision. To handle this, each array slot holds a bucket, often a linked list, where all entries with that index are stored. When looking up a key, we check the bucket for the matching key.

Result

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

Handling collisions is essential to maintain correctness and performance in HashMaps.

5

Intermediate

Basic HashMap Operations

🤔Before reading on: do you think adding a new key-value pair always increases the array size? Commit to yes or no.

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

To add a pair, compute the index from the key, then add the pair to the bucket at that index. To get a value, compute the index and search the bucket for the key. To remove, find the key in the bucket and delete it. The array size stays fixed until resizing.

Result

You can perform the main operations of a HashMap using hashing and buckets.

Understanding these operations shows how HashMaps provide fast data access.

6

Advanced

Resizing and Rehashing the Map

🤔Before reading on: do you think a HashMap's array size changes automatically? Commit to yes or no.

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

When many items are added, buckets get longer, slowing lookups. To fix this, the HashMap creates a bigger array and re-inserts all items using their hash codes again (rehashing). This keeps buckets short and operations fast.

Result

You understand how HashMaps maintain speed by resizing and rehashing.

Knowing resizing prevents performance degradation in large HashMaps.

7

Expert

Optimizing Collisions with Trees

🤔Before reading on: do you think linked lists are always the best way to handle collisions? Commit to yes or no.

Concept: Learn how some HashMaps use balanced trees instead of lists for buckets with many collisions.

When a bucket gets very long, searching it becomes slow. Some HashMaps switch from linked lists to balanced trees (like red-black trees) for that bucket. Trees keep search time low even with many collisions, improving worst-case performance.

Result

You see how advanced HashMaps optimize collision handling for better speed.

Understanding this optimization reveals how production HashMaps avoid slowdowns in bad cases.

Under the Hood

A HashMap stores data in an array where each position is a bucket. The hash function converts keys into integers, which are then mapped to array indexes using modulo. When collisions occur, entries are stored in a linked list or tree at that index. On insertion, retrieval, or deletion, the hash function directs to the bucket, and the bucket is searched linearly or via tree traversal. When the load factor (items/array size) exceeds a threshold, the array is resized and all entries are rehashed to new positions.

Why designed this way?

HashMaps were designed to provide average constant-time operations by combining arrays and hashing. Arrays offer fast index access, but keys are not numeric indexes, so hashing maps keys to indexes. Collisions are inevitable due to limited array size, so buckets handle them. Resizing balances memory use and speed. Alternatives like balanced trees alone are slower on average, so HashMaps blend speed and flexibility.

HashMap Internal Flow:

[Key] --hash_function--> [Hash Code] --mod array_size--> [Index]

Array:
┌─────────────┐
│ Index 0     │──> Bucket (Linked List / Tree)
│ Index 1     │──> Bucket
│ Index 2     │──> Bucket
│ ...         │
│ Index N     │──> Bucket
└─────────────┘

Operations:
Insert/Get/Delete
  ↓
Compute index
  ↓
Access bucket
  ↓
Search bucket for key
  ↓
Perform operation

Myth Busters - 4 Common Misconceptions

Quick: does a hash function guarantee unique indexes for different keys? Commit to yes or no.

Common Belief: A hash function always gives 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 correctness.

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

Common Belief: The HashMap resizes its array every time a new key-value pair is added.

Reality: Resizing happens only when the load factor exceeds a threshold to balance speed and memory.

Why it matters: Resizing too often wastes resources; too rarely causes slow lookups due to long buckets.

Quick: do you think linked lists are always the best way to handle collisions? Commit to yes or no.

Common Belief: Linked lists are the only way to handle collisions in HashMaps.

Reality: Some HashMaps use balanced trees for buckets with many collisions to improve worst-case performance.

Why it matters: Using only linked lists can cause slow lookups in worst cases, hurting performance.

Quick: do you think the order of items in a HashMap is always the same as insertion order? Commit to yes or no.

Common Belief: HashMaps keep items in the order they were added.

Reality: HashMaps do not guarantee any order; items are stored based on hash codes and array indexes.

Why it matters: Assuming order can cause bugs when iterating or displaying data.

Expert Zone

1

The quality of the hash function greatly affects performance; poor hash functions cause many collisions and degrade speed.

2

Load factor tuning balances memory use and speed; a lower load factor means faster lookups but more memory.

3

Some implementations use open addressing (probing) instead of buckets, trading off memory and complexity.

When NOT to use

HashMaps are not ideal when order matters; use LinkedHashMap or Trees instead. For small datasets or when memory is very limited, simpler arrays or lists may be better. When keys are complex objects without good hash functions, consider other structures like balanced trees.

Production Patterns

In production, HashMaps are used for caches, symbol tables, and fast lookups. They often combine with concurrency controls for thread safety. Implementations optimize resizing, use high-quality hash functions, and switch bucket structures dynamically to maintain performance.

Connections

Balanced Trees

Alternative collision handling method

Understanding balanced trees helps grasp how some HashMaps optimize buckets for worst-case speed.

Cryptographic Hash Functions

Advanced hash function design

Knowing cryptographic hashes shows how hash functions can be designed for uniform distribution and security.

Cache Memory in Computer Architecture

Similar indexing and collision handling

Cache memory uses similar hashing and collision strategies to quickly find data, linking hardware and software concepts.

Common Pitfalls

#1 Ignoring collisions and overwriting existing entries.

Wrong approach:

void put(HashMap* map, Key key, Value value) {
int index = hash(key) % map->size;
map->array[index] = value; // overwrites without checking
}

Correct approach:

void put(HashMap* map, Key key, Value value) {
int index = hash(key) % map->size;
Bucket* bucket = map->array[index];
// Search bucket for key
// If found, update value
// Else, add new entry to bucket
}

Root cause:

Misunderstanding that multiple keys can map to the same index and need separate storage.

#2 Not resizing the HashMap leading to slow performance.

Wrong approach:

void put(HashMap* map, Key key, Value value) {
// No check for load factor or resizing
// Insert directly
}

Correct approach:

void put(HashMap* map, Key key, Value value) {
if ((float)map->count / map->size > LOAD_FACTOR_THRESHOLD) {
resize(map);
}
// Insert after resizing
}

Root cause:

Ignoring the need to maintain a low load factor for performance.

#3 Assuming iteration order matches insertion order.

Wrong approach:

for (int i = 0; i < map->size; i++) {
// Print entries assuming insertion order
}

Correct approach:

for (int i = 0; i < map->size; i++) {
// Print entries in bucket order, no order guarantee
}

Root cause:

Misunderstanding that HashMaps do not preserve order.

Key Takeaways

HashMaps store key-value pairs using a hash function to quickly find data without searching all items.

Collisions happen when different keys map to the same index; buckets like linked lists or trees handle them.

Resizing the underlying array and rehashing entries keeps HashMaps fast as they grow.

Advanced HashMaps optimize collision handling by switching bucket structures to maintain speed.

Understanding HashMaps is essential for efficient data storage and retrieval in many software systems.