C Mastery / Hash Tables and Hash Maps
Part 8 — Data Structures and Algorithms in C

Hash Tables and Hash Maps

This chapter implements a hash table (and hash map) in C: hashing, collision resolution, load factor, and rehashing.

Why This Matters

Hash tables give O(1) average lookup, insert, and delete — the fastest general key-value structure. They are the foundation of dictionaries, caches, symbol tables, and countless systems.

Prerequisites

Core Concept

A hash table maps keys to values by:

1. Hashing the key to an integer. 2. Mapping that integer to a bucket index (e.g., hash % capacity). 3. Resolving collisions when two keys map to the same bucket.

Two common collision strategies:

double hashing).

The load factor is size / capacity. When it exceeds a threshold, the table rehashes into a larger capacity to keep operations O(1).

Examples

Chaining hash table (string keys)

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

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

typedef struct {
    Entry **buckets;
    size_t capacity;
    size_t size;
} HashTable;

static size_t hash_str(const char *s, size_t cap)
{
    size_t h = 5381;
    while (*s) h = h * 33 + (unsigned char)*s++;
    return h % cap;
}

The djb2 hash (h = 5381, h = h*33 + c) is simple and effective for strings.

Insert (chaining)

int ht_put(HashTable *t, const char *key, int value)
{
    size_t i = hash_str(key, t->capacity);
    for (Entry *e = t->buckets[i]; e; e = e->next) {
        if (strcmp(e->key, key) == 0) { e->value = value; return 0; }
    }
    Entry *e = malloc(sizeof *e);
    if (!e) return -1;
    e->key = strdup(key);
    e->value = value;
    e->next = t->buckets[i];
    t->buckets[i] = e;
    t->size++;
    return 0;
}

How It Works

A good hash function spreads keys uniformly across buckets, so the average chain/probe length is small. Rehashing to roughly double the capacity when the load factor passes (say) 0.75 keeps operations near O(1).

Variations

Open addressing

Stores entries directly in the array and probes on collision. Better cache locality than chaining, but deletion is trickier (tombstones).

Intrusive hash maps

In kernels/embedded code, entries are embedded in the caller's struct, avoiding separate allocation (like intrusive lists).

Common Mistakes

Undefined Behavior

Portability

allocate + memcpy.

Under the Hood

A chaining table is an array of pointers; cache behavior depends on the chain length. Open addressing is more cache-friendly. Rehashing is an O(n) operation amortized over inserts.

Practical Usage

Exercises

1. Implement ht_get, ht_put, ht_del, and ht_free. 2. Add rehashing when the load factor exceeds 0.75. 3. Implement an open-addressing variant with linear probing. 4. Write a small string-to-int dictionary and test it.

Deep Challenge

Implement an open-addressing hash map with robin-hood hashing (minimize probe distance), and explain why it has better cache behavior and lower variance than linear probing.

References

Verification

verified.`

Progress

Concept checkboxes

Mastery levels

ConceptCurrent level (0–8)Target level
c.ds.hashtable06
c.ds.hashmap06
← PrevNext →