Hash Table Concept and Hash Functions in DSA C

Mental Model

A hash table stores data so you can find it very fast by turning the data into a number called a hash.

Analogy: Imagine a library where each book has a special code that tells you exactly which shelf and spot to find it quickly without searching all shelves.

Hash Table:
[0] -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Hash Function: key -> index (0 to 4)

Dry Run Walkthrough

Input: Insert keys 12, 22, 32 into a hash table of size 5 using hash function key % 5

Goal: Store keys so they can be found quickly by their hash index

Step 1: Calculate hash for key 12: 12 % 5 = 2, insert 12 at index 2

[0] -> null
[1] -> null
[2] -> 12 -> null
[3] -> null
[4] -> null

Why: We use the hash function to find the correct index to store key 12

Step 2: Calculate hash for key 22: 22 % 5 = 2, insert 22 at index 2 using chaining

[0] -> null
[1] -> null
[2] -> 22 -> 12 -> null
[3] -> null
[4] -> null

Why: Collision happens at index 2, so we add 22 in a linked list at that index

Step 3: Calculate hash for key 32: 32 % 5 = 2, insert 32 at index 2 using chaining

[0] -> null
[1] -> null
[2] -> 32 -> 22 -> 12 -> null
[3] -> null
[4] -> null

Why: Another collision at index 2, so we add 32 at the front of the linked list

Result:

[0] -> null
[1] -> null
[2] -> 32 -> 22 -> 12 -> null
[3] -> null
[4] -> null

Annotated Code

DSA C

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

#define TABLE_SIZE 5

// Node for chaining
typedef struct Node {
    int key;
    struct Node* next;
} Node;

// Hash table with chaining
Node* hashTable[TABLE_SIZE];

// Hash function: key modulo table size
int hashFunction(int key) {
    return key % TABLE_SIZE;
}

// Insert key into hash table
void insert(int key) {
    int index = hashFunction(key); // get index
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->next = hashTable[index]; // insert at head
    hashTable[index] = newNode;
}

// Print hash table
void printTable() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        printf("[%d] -> ", i);
        Node* curr = hashTable[i];
        while (curr != NULL) {
            printf("%d -> ", curr->key);
            curr = curr->next;
        }
        printf("null\n");
    }
}

int main() {
    // Initialize hash table
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable[i] = NULL;
    }

    // Insert keys
    insert(12);
    insert(22);
    insert(32);

    // Print final table
    printTable();
    return 0;
}

int index = hashFunction(key);

Calculate hash index for the key

newNode->next = hashTable[index];

Insert new node at the head of the linked list at index

hashTable[index] = newNode;

Update head pointer to new node

while (curr != NULL) { printf("%d -> ", curr->key); curr = curr->next; }

Traverse linked list to print all keys at index

Output

[0] -> null

[1] -> null

[2] -> 32 -> 22 -> 12 -> null

[3] -> null

[4] -> null

Complexity Analysis

Time: O(1) average for insert and search because hash function gives direct index; O(n) worst if many collisions form long chains

Space: O(n) because we store all keys in the table and linked lists

vs Alternative: Compared to arrays or lists, hash tables provide faster average lookup by avoiding full scans, but need extra space for chaining

Edge Cases

Inserting keys that all hash to the same index

All keys form a linked list at one index, slowing down search to O(n)

DSA C

newNode->next = hashTable[index];

Empty hash table before any insertions

All indices point to null, no keys stored

DSA C

for (int i = 0; i < TABLE_SIZE; i++) { hashTable[i] = NULL; }

When to Use This Pattern

When you need very fast lookup or insertion by key and can accept some extra memory, use a hash table with a hash function to jump directly to data location.

Common Mistakes

Mistake: Not handling collisions, overwriting existing data at the same index
Fix: Use chaining or open addressing to store multiple keys at the same index

Mistake: Using a poor hash function that causes many collisions
Fix: Choose or design a hash function that distributes keys evenly across indices

Summary

Stores data using a hash function to find an index quickly.

Use when you want fast insert and search by key.

The key insight is turning keys into indices to avoid scanning all data.