C Data Structures: Hash Tables & Collision Resolution Masterclass

⚡ C (C17 / C23 Standard) 🟢 Lesson 51 📂 Phase 18: Data Structures in C 📅 2026 Comprehensive Master Edition

📌 Covered in this in-depth guide: Hash Functions · djb2 String Hash · Separate Chaining (Linked Lists) · Open Addressing Linear Probing · Load Factor & Rehashing · String → Value HashMap · O(1) Average Lookup

Welcome to Phase 18 (Chapter 51): C Data Structures — Hash Tables & Collision Resolution Masterclass! A Hash Table achieves O(1) average-case insert, lookup, and delete by computing a bucket index from a key using a hash function. This makes it the most powerful data structure for symbol tables, caches, dictionaries, and database indices.

1Hash Function Design & djb2 Algorithm

A hash function maps an arbitrary key (string, integer, etc.) to a bucket index in the array. A good hash function distributes keys uniformly with minimal collisions.

djb2 — Dan Bernstein's Fast String Hash:

hash = 5381;

for each char c: hash = ((hash << 5) + hash) + c; // hash * 33 + c

Simple, fast, excellent distribution for ASCII strings. Used by many real implementations.

2Complete Hash Map with Separate Chaining

C — String HashMap with Separate Chaining▶ Try in Compiler

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

#define TABLE_SIZE 64

typedef struct KVNode {
    char *key;
    int   value;
    struct KVNode *next;
} KVNode;

typedef struct { KVNode *buckets[TABLE_SIZE]; } HashMap;

static unsigned long djb2(const char *s) {
    unsigned long h = 5381;
    while (*s) h = ((h << 5) + h) + (unsigned char)*s++;
    return h % TABLE_SIZE;
}

void hmap_set(HashMap *m, const char *key, int value) {
    unsigned long idx = djb2(key);
    for (KVNode *n = m->buckets[idx]; n; n = n->next) {
        if (strcmp(n->key, key) == 0) { n->value = value; return; }
    }
    KVNode *n = malloc(sizeof(KVNode));
    n->key = strdup(key); n->value = value;
    n->next = m->buckets[idx];
    m->buckets[idx] = n;
}

int hmap_get(const HashMap *m, const char *key, int *out) {
    unsigned long idx = djb2(key);
    for (KVNode *n = m->buckets[idx]; n; n = n->next)
        if (strcmp(n->key, key) == 0) { *out = n->value; return 1; }
    return 0;
}

int main(void) {
    HashMap m = {0};
    hmap_set(&m, "ravi",   90);
    hmap_set(&m, "anitha", 95);
    hmap_set(&m, "kiran",  78);

    const char *names[] = {"ravi", "anitha", "kiran", "priya"};
    for (int i = 0; i < 4; i++) {
        int score;
        if (hmap_get(&m, names[i], &score))
            printf("%-8s → %d\n", names[i], score);
        else
            printf("%-8s → NOT FOUND\n", names[i]);
    }
    return 0;
}

3Technical FAQs

Q1: What is a hash collision?

A collision occurs when two different keys produce the same bucket index. Separate chaining handles this by storing a linked list at each bucket. Open addressing probes for an alternative empty slot.

Q2: What is the load factor and why does it matter?

Load factor = (number of entries) / (number of buckets). Above ~0.75 load factor, collision chains grow and performance degrades from O(1) toward O(n). Rehash by doubling bucket count.

Q3: What is linear probing?

Open addressing strategy: on collision, try bucket index+1, +2, +3... (wrapping around). Simpler than chaining but suffers from primary clustering — long runs of filled buckets.

Q4: Why is hash table lookup O(1) average but O(n) worst case?

Worst case occurs when all keys hash to the same bucket, creating a single chain of length n. In practice, good hash functions and low load factors make O(1) the expected case.

Q5: What makes a hash function cryptographically secure?

Cryptographic hash functions (SHA-256, Blake3) are additionally collision-resistant (hard to find two inputs with same hash), one-way (cannot reverse), and avalanche-sensitive. NOT needed for data structure use-cases.