📈 Algorithms & Complexity

Hash tables: the O(1) dictionary

⏱ 15 min · free interactive lesson · quizzes, visualizations & a real compiler

Every structure so far finds things by position (index 3) or by searching (O(n) scan, O(log n) binary search). But the lookup you actually want most is by name — a key: "what's the value stored under "dog"?" — and you want it in O(1), no matter if there are ten keys or ten million. That structure is the hash table, and it powers Python dicts, JavaScript objects, the indexes that make databases fast, and the way your terminal finds each command you type.

The big idea: compute where things live

An array gives O(1) access if you know the index. So… what if we could calculate an index from the key itself? That calculator is a hash function: it chews the bytes of the key and spits out a number. Same key in, same number out, every time. A beloved classic is djb2 (Daniel J. Bernstein, 1991):

#include <stdio.h>

unsigned long djb2(const char *s) {
    unsigned long h = 5381;            /* magic seed        */
    while (*s)
        h = h * 33 + (unsigned char)*s++;   /* mix each byte */
    return h;
}

int main(void) {
    const char *w[] = {"ant","bee","cat","cow","dog","emu","owl"};
    for (int i = 0; i < 7; i++)
        printf("%-3s -> %10lu %% 8 = bucket %lu\n",
               w[i], djb2(w[i]), djb2(w[i]) % 8);
    return 0;
}

$ gcc djb2.c -o djb2 && ./djb2
ant ->  193486376 % 8 = bucket 0
bee ->  193487153 % 8 = bucket 1
cat ->  193488125 % 8 = bucket 5
cow ->  193488590 % 8 = bucket 6
dog ->  193489663 % 8 = bucket 7
emu ->  193490700 % 8 = bucket 4
owl ->  193501911 % 8 = bucket 7   # <- same as dog. collision!

Why h * 33 + c? Honestly: nobody fully knows — it's empirical magic that mixes bits cheaply and spreads real-world strings well. (33 = 32 + 1, so compilers do it as a shift and an add.) The unsigned overflow that happens on long strings is fine — unsigned wraparound is well-defined in C, and hashing wants the scrambling.

Buckets: hash, then modulo

A hash is a huge number; the table has, say, 8 slots. hash % 8 maps every key to a bucket. Here are those seven animals landing in an 8-bucket table:

▶ This spot has an interactive memgrid widget — open the interactive lesson to play with it.

Collisions are not a bug — they're a certainty

Notice dog and owl both landed in bucket 7. Inevitable: there are infinitely many possible strings and only 8 buckets — by the pigeonhole principle, some keys must share. A hash table isn't defined by avoiding collisions but by surviving them. The classic survival strategy is chaining: each bucket holds a linked list of everything that landed there.

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

#define NBUCKETS 8

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

typedef struct { Entry *bucket[NBUCKETS]; } Map;

static unsigned long djb2(const char *s) {
    unsigned long h = 5381;
    while (*s) h = h * 33 + (unsigned char)*s++;
    return h;
}

void map_put(Map *m, const char *key, int value) {
    unsigned long b = djb2(key) % NBUCKETS;
    for (Entry *e = m->bucket[b]; e; e = e->next)
        if (strcmp(e->key, key) == 0) { e->value = value; return; }
    Entry *e = malloc(sizeof *e);           /* new entry:     */
    e->key = malloc(strlen(key) + 1);       /* own copy of    */
    strcpy(e->key, key);                    /*   the key      */
    e->value = value;
    e->next = m->bucket[b];                 /* push onto the  */
    m->bucket[b] = e;                       /*   chain: O(1)  */
}

int *map_get(Map *m, const char *key) {
    for (Entry *e = m->bucket[djb2(key) % NBUCKETS]; e; e = e->next)
        if (strcmp(e->key, key) == 0) return &e->value;
    return NULL;                            /* absent         */
}

void map_free(Map *m) {
    for (int b = 0; b < NBUCKETS; b++)
        for (Entry *e = m->bucket[b]; e; ) {
            Entry *next = e->next;
            free(e->key); free(e);
            e = next;
        }
}

int main(void) {
    Map m = {0};                 /* all buckets start NULL */
    map_put(&m, "dog", 4);
    map_put(&m, "owl", 2);       /* bucket 7 too — chained! */
    map_put(&m, "cat", 9);
    map_put(&m, "dog", 5);       /* update, not duplicate  */

    int *v = map_get(&m, "dog");
    printf("dog -> %d\n", v ? *v : -1);
    printf("owl -> %d\n", *map_get(&m, "owl"));
    printf("fox -> %s\n", map_get(&m, "fox") ? "found" : "not found");

    map_free(&m);
    return 0;
}

$ gcc map.c -o map && ./map
dog -> 5
owl -> 2
fox -> not found
# "dog" was inserted then UPDATED in place — still one entry.
# valgrind reports 0 leaks: every malloc has its free.

Read map_put carefully: it first walks the chain to update an existing key (a real map has no duplicate keys), and only then pushes a new entry onto the front of the bucket's list — O(1). Lookup hashes to the right bucket, then walks a chain that is, on average, tiny.

Load factor: how full is too full?

The load factor is entries ÷ buckets. With a good hash and load factor around 1, the average chain has ~1 link — lookups are O(1) on average. Let the table overfill (load factor 10, 100…) and chains stretch — performance slides toward O(n). Real implementations watch the load factor and resize: allocate ~double the buckets and re-insert every key (positions change because % nbuckets changed!). One expensive O(n) rehash, amortized over all the O(1) inserts that preceded it — the same doubling trick as the dynamic array from the Big-O lesson.

▶ This spot has an interactive bigo widget — open the interactive lesson to play with it.

Why doesn't C just have one built in?

Because C has no generics, no standard allocator policy hooks, and a fierce "you don't pay for what you don't use" culture — a one-size-fits-all hash table would fit nobody well. (POSIX does offer the crusty hsearch; almost nobody uses it.) In practice C programmers either write a small one per project, tuned to its keys — like we just did — or grab a library: uthash (a delightfully evil header of macros that hangs a hash handle inside your struct), or GLib's GHashTable. Either way, now you know exactly what's under the hood.

▶ This spot has an interactive editor widget — open the interactive lesson to play with it.

And that's the algorithms toolkit! You can now reason about cost, search, sort, and structure data — next we descend into the machinery that builds it all: the compiler and its toolchain.