HashMap Implementation from Scratch in DSA C

Mental Model

A HashMap stores key-value pairs using a special function to find where to keep each pair quickly.

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 key-value pairs.

Dry Run Walkthrough

Input: Insert keys 1, 6, and 11 with values 'A', 'B', 'C' into a HashMap with 5 buckets.

Goal: Store key-value pairs so that keys 1, 6, and 11 are placed in correct buckets using hash function key % 5, handling collisions by chaining.

Step 1: Insert key=1, value='A'. Compute hash index = 1 % 5 = 1.

[0] -> null
[1] -> (1, 'A') -> null
[2] -> null
[3] -> null
[4] -> null

Why: We place the pair in bucket 1 because hash function gives index 1.

Step 2: Insert key=6, value='B'. Compute hash index = 6 % 5 = 1. Collision at bucket 1.

[0] -> null
[1] -> (6, 'B') -> (1, 'A') -> null
[2] -> null
[3] -> null
[4] -> null

Why: We add new pair at the head of linked list in bucket 1 to handle collision.

Step 3: Insert key=11, value='C'. Compute hash index = 11 % 5 = 1. Collision at bucket 1.

[0] -> null
[1] -> (11, 'C') -> (6, 'B') -> (1, 'A') -> null
[2] -> null
[3] -> null
[4] -> null

Why: We add new pair at the head of linked list in bucket 1 to handle collision.

Result:

[0] -> null
[1] -> (11, 'C') -> (6, 'B') -> (1, 'A') -> null
[2] -> null
[3] -> null
[4] -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BUCKET_COUNT 5

// Node for linked list in each bucket
typedef struct Node {
    int key;
    char value[10];
    struct Node* next;
} Node;

// HashMap structure
typedef struct HashMap {
    Node* buckets[BUCKET_COUNT];
} HashMap;

// Create a new node
Node* create_node(int key, const char* value) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->key = key;
    strcpy(new_node->value, value);
    new_node->next = NULL;
    return new_node;
}

// Initialize HashMap
void init_hashmap(HashMap* map) {
    for (int i = 0; i < BUCKET_COUNT; i++) {
        map->buckets[i] = NULL;
    }
}

// Hash function: key modulo bucket count
int hash_function(int key) {
    return key % BUCKET_COUNT;
}

// Insert key-value pair into HashMap
void hashmap_insert(HashMap* map, int key, const char* value) {
    int index = hash_function(key); // compute bucket index
    Node* head = map->buckets[index];

    // Check if key exists, update value if found
    Node* curr = head;
    while (curr != NULL) {
        if (curr->key == key) {
            strcpy(curr->value, value); // update existing value
            return;
        }
        curr = curr->next;
    }

    // Insert new node at head for collision chaining
    Node* new_node = create_node(key, value);
    new_node->next = head;
    map->buckets[index] = new_node;
}

// Print HashMap contents
void print_hashmap(HashMap* map) {
    for (int i = 0; i < BUCKET_COUNT; i++) {
        printf("[%d] -> ", i);
        Node* curr = map->buckets[i];
        while (curr != NULL) {
            printf("(%d, '%s') -> ", curr->key, curr->value);
            curr = curr->next;
        }
        printf("null\n");
    }
}

int main() {
    HashMap map;
    init_hashmap(&map);

    hashmap_insert(&map, 1, "A");
    hashmap_insert(&map, 6, "B");
    hashmap_insert(&map, 11, "C");

    print_hashmap(&map);
    return 0;
}

int index = hash_function(key); // compute bucket index

Calculate bucket index using hash function

while (curr != NULL) { if (curr->key == key) { strcpy(curr->value, value); return; } curr = curr->next; }

Check if key exists to update value instead of inserting duplicate

new_node->next = head; map->buckets[index] = new_node;

Insert new node at head of linked list to handle collisions

Output

[0] -> null

[1] -> (11, 'C') -> (6, 'B') -> (1, 'A') -> null

[2] -> null

[3] -> null

[4] -> null

Complexity Analysis

Time: O(n/k) on average, where n is number of keys and k is bucket count, because each bucket holds about n/k nodes; worst case O(n) if all keys collide.

Space: O(n) because we store each key-value pair in a node.

vs Alternative: Compared to a simple array search O(n), HashMap insertion and lookup are faster on average due to direct bucket access and chaining.

Edge Cases

Inserting duplicate key

Value is updated in existing node instead of adding new node.

DSA C

if (curr->key == key) { strcpy(curr->value, value); return; }

Empty HashMap

Buckets are initialized to NULL, no nodes present.

DSA C

for (int i = 0; i < BUCKET_COUNT; i++) { map->buckets[i] = NULL; }

All keys collide to same bucket

All nodes form a linked list in one bucket, performance degrades to O(n).

DSA C

new_node->next = head; map->buckets[index] = new_node;

When to Use This Pattern

When you need fast key-value storage with quick insert and lookup, and see problems mentioning hashing or collisions, reach for HashMap implementation with chaining.

Common Mistakes

Mistake: Not handling collisions, overwriting existing bucket pointer losing previous nodes.
Fix: Insert new nodes at head of linked list to preserve existing nodes.

Mistake: Not checking for existing key before inserting, causing duplicates.
Fix: Traverse bucket list to update value if key exists before inserting new node.

Summary

Stores key-value pairs using a hash function and linked lists to handle collisions.

Use when you want fast insert and lookup by key with average constant time.

The key insight is using a hash function to find a bucket and chaining to handle collisions.