Why Hash Map Exists and What Problem It Solves in DSA C - Why This Pattern

Mental Model

A hash map helps us find things quickly by using a special code to jump directly to where the item is stored.

Analogy: Imagine a huge library where books are scattered randomly. Without a system, you search shelf by shelf. A hash map is like having a special code on each book that tells you exactly which shelf and spot to look at instantly.

Keys: [apple, banana, grape]
Hash Map Buckets:
[0] -> null
[1] -> banana -> null
[2] -> apple -> null
[3] -> grape -> null

Dry Run Walkthrough

Input: Store keys: apple, banana, grape; then find 'banana'

Goal: Show how hash map stores keys and finds 'banana' quickly without checking all keys

Step 1: Calculate hash for 'apple' and store it in bucket 2

Buckets:
[0] -> null
[1] -> null
[2] -> apple -> null
[3] -> null

Why: We use the hash to decide where to put 'apple' so we can find it fast later

Step 2: Calculate hash for 'banana' and store it in bucket 1

Buckets:
[0] -> null
[1] -> banana -> null
[2] -> apple -> null
[3] -> null

Why: Each key gets its own bucket based on hash to avoid searching all keys

Step 3: Calculate hash for 'grape' and store it in bucket 3

Buckets:
[0] -> null
[1] -> banana -> null
[2] -> apple -> null
[3] -> grape -> null

Why: Storing keys in different buckets keeps lookups fast

Step 4: To find 'banana', calculate its hash to get bucket 1 and check keys there

Buckets:
[0] -> null
[1] -> [search banana] -> null
[2] -> apple -> null
[3] -> grape -> null

Why: We jump directly to bucket 1 instead of checking all buckets

Step 5: Find 'banana' in bucket 1 and return it

Buckets:
[0] -> null
[1] -> banana -> null
[2] -> apple -> null
[3] -> grape -> null

Why: Found the key quickly without searching other buckets

Result:

Buckets:
[0] -> null
[1] -> banana -> null
[2] -> apple -> null
[3] -> grape -> null
Found key: banana

Annotated Code

DSA C

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

#define SIZE 4

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

// Hash Map with buckets
Node* hashMap[SIZE];

// Simple hash function: sum of chars mod SIZE
unsigned int hash(char* key) {
    unsigned int sum = 0;
    for (int i = 0; key[i] != '\0'; i++) {
        sum += key[i];
    }
    return sum % SIZE;
}

// Insert key into hash map
void insert(char* key) {
    unsigned int index = hash(key); // get bucket index
    Node* newNode = malloc(sizeof(Node));
    strcpy(newNode->key, key);
    newNode->next = hashMap[index]; // insert at head
    hashMap[index] = newNode;
}

// Search key in hash map
Node* search(char* key) {
    unsigned int index = hash(key); // get bucket index
    Node* curr = hashMap[index];
    while (curr != NULL) {
        if (strcmp(curr->key, key) == 0) {
            return curr; // found key
        }
        curr = curr->next; // check next node
    }
    return NULL; // not found
}

// Print hash map state
void printHashMap() {
    for (int i = 0; i < SIZE; i++) {
        printf("[%d] -> ", i);
        Node* curr = hashMap[i];
        while (curr != NULL) {
            printf("%s -> ", curr->key);
            curr = curr->next;
        }
        printf("null\n");
    }
}

int main() {
    // Initialize buckets
    for (int i = 0; i < SIZE; i++) {
        hashMap[i] = NULL;
    }

    // Insert keys
    insert("apple");
    insert("banana");
    insert("grape");

    // Print state after inserts
    printHashMap();

    // Search for 'banana'
    Node* found = search("banana");
    if (found != NULL) {
        printf("Found key: %s\n", found->key);
    } else {
        printf("Key not found\n");
    }

    return 0;
}

unsigned int index = hash(key); // get bucket index

calculate bucket index using hash function

newNode->next = hashMap[index]; // insert at head

insert new key at the start of the bucket list

Node* curr = hashMap[index];

start searching from the bucket's head

if (strcmp(curr->key, key) == 0) { return curr; }

check if current node key matches search key

curr = curr->next; // check next node

move to next node if not found

Output

[0] -> null

[1] -> banana -> null

[2] -> apple -> null

[3] -> grape -> null

Found key: banana

Complexity Analysis

Time: O(1) average because hash function jumps directly to bucket; worst O(n) if many keys collide in one bucket

Space: O(n) because we store all keys in buckets

vs Alternative: Compared to searching all keys one by one (O(n)), hash map reduces average search time to O(1) by using hashing

Edge Cases

Empty hash map

Search returns not found immediately because buckets are empty

DSA C

while (curr != NULL) { ... }

Multiple keys hashing to same bucket (collision)

Keys are stored in linked list in that bucket; search checks each node

DSA C

curr = curr->next; // check next node

Searching for a key not present

Search traverses bucket list and returns NULL

DSA C

return NULL; // not found

When to Use This Pattern

When you need to store and find items quickly by key without scanning all items, reach for the hash map pattern because it uses hashing to jump directly to the data location.

Common Mistakes

Mistake: Not handling collisions, assuming each bucket holds only one key
Fix: Use a linked list or another structure in each bucket to store multiple keys

Mistake: Using a poor hash function causing many collisions
Fix: Use a hash function that distributes keys evenly across buckets

Summary

Hash map stores keys using a hash function to find them quickly.

Use hash maps when you want fast lookup, insert, and delete by key.

The key insight is hashing lets you jump directly to where the data is stored, avoiding slow searches.