Hash tables

Overview

What a hash table is

Imagine you have a phone book and you want the number for "Maria". With an unsorted array you would scan every entry — that is O(n). With a sorted array and binary search it is O(log n). A hash table does something cleverer: it computes where "Maria" should live from the letters in her name, then jumps straight there. On average that jump is O(1) — constant time, no matter how many entries the table holds.

A hash table is an array (called the bucket array) plus a hash function. The hash function takes a key — a string, an integer, anything — and produces a large integer. You then reduce that integer to a valid array index with the modulo operator:

index = hash(key) % capacity;

hash(key) mixes the bytes of the key into a number; % capacity folds that number into the range 0 .. capacity-1 so it is a legal subscript.

Where it connects to what you already know

This lesson builds directly on Arrays — the bucket array is a plain C array, and the whole point is to compute an index into it instead of scanning. It also builds on Structs: each stored entry is a struct holding the key, the value, and (for chaining) a pointer to the next entry in the same bucket. If you understood how a struct groups related fields and how an array gives O(1) indexed access, you already have both halves of a hash table — the new idea is the function that decides which index a key belongs to.

Why hash tables are everywhere

Dictionaries, sets, caches, symbol tables in compilers, database indexes, and the Map/dict/HashMap types in nearly every high-level language are all hash tables underneath. When you need "look something up by name, fast", a hash table is usually the answer.

Terminology you will see

• Key: the thing you look up by (e.g. a username).
• Value: the data stored under that key (e.g. a user ID).
• Bucket / slot: one cell of the array.
• Collision: two different keys that map to the same index.
• Load factor: count / capacity — how full the table is.
• Rehash / resize: growing the array and recomputing every index.

Why it matters

Why this matters in real software

The difference between O(1) and O(n) is the difference between a program that scales and one that grinds to a halt. A spell checker holding 100,000 words, a web server caching 1,000,000 sessions, or a compiler tracking every variable name relies on lookups being near-instant. If those were linear scans, each lookup would touch every entry and the system would slow down in proportion to its own success.

Hash tables are also a correctness tool, not just a speed tool. A set (membership testing — "have I seen this value before?") is a hash table where you only care about the keys. De-duplicating a stream, detecting cycles, counting word frequencies, and joining two datasets on a shared key are all hash-table problems.

Finally, understanding hash tables makes you a better user of them. Knowing about load factors explains why a language's dictionary occasionally pauses (it is resizing). Knowing about collisions explains why a bad hash function can turn an O(1) structure into an O(n) one — a fact attackers have exploited (hash-flooding denial-of-service), which is why production libraries seed their hash functions with a random value.

Core concepts

1. The hash function

Definition. A hash function maps a key of any size to a fixed-size integer (the hash code).

Plain language. It scrambles the bytes of the key so that even similar keys ("cat" and "car") land in very different places. A good hash spreads keys evenly across the whole array.

How it works internally. A common string hash is djb2: start with a seed, then for each byte multiply the running value and add the byte. The multiply-and-add mixes every character into the result.

unsigned long hash = 5381;
for each byte c in key:
    hash = hash * 33 + c;   /* 33 is a constant that mixes bits well */

For integer keys, Knuth's multiplicative hash works well:

index = ((uint32_t)k * 2654435761u) % cap;

When to use which. Match the hash to the key type. Strings need a function that reads every byte; integers can use a single multiply. Do not use the raw key (key % cap) — sequential or patterned keys then cluster.

Pitfall. A hash function that ignores part of the key (e.g. only the first character) collides constantly. Always consume the whole key.

Knowledge check (explain in your own words): Why does hash(key) % capacity rather than hash(key) give a valid array index?

2. Collisions

Definition. A collision is when two distinct keys produce the same index.

Plain language. Even a perfect hash cannot avoid this: you are squeezing a huge space of possible keys into a small array, so two keys must sometimes share a slot (the pigeonhole principle). The table must store both without losing either.

3. Separate chaining

Definition. Each bucket holds a linked list of entries; colliding keys are appended to the list for that bucket.

Structure (text diagram).

buckets[]      linked lists
+-----+
|  0  | --> ["sky":7] --> NULL
+-----+
|  1  | --> NULL
+-----+
|  2  | --> ["cat":3] --> ["dog":9] --> NULL   <- two keys collided here
+-----+
|  3  | --> ["sun":1] --> NULL
+-----+

How it works. To insert, compute the index, then walk the list: if the key already exists, update it; otherwise add a new node at the head. To look up, walk the list comparing keys. Average list length is the load factor, so with load factor near 1 each operation touches roughly one node.

When to use / not use. Use chaining when entries are large, deletions are frequent, or you cannot predict the number of keys (lists grow gracefully). Avoid it when you want maximum cache locality — each node is a separate malloc, so traversal jumps around memory.

Pitfall. Forgetting to free every node in every list on cleanup leaks memory.

4. Open addressing (linear probing)

Definition. All entries live directly in the array. On a collision you probe — check the next slot, then the next — until you find a free one.

Structure (text diagram).

Insert "dog" -> hash gives index 2, but slot 2 is taken by "cat",
so probe forward to slot 3.

index:  0      1      2        3        4
      [ . ] [ . ] ["cat"] ["dog"] [ . ]
                     ^        ^
                  hashed   placed after probing

How it works. Lookup repeats the same probe sequence and stops at either the key (found) or an empty slot (not found). Deletion is tricky: you cannot just blank a slot, because that empty cell would break the probe chain for keys placed after it. The fix is a tombstone — a special "was deleted" marker that lookups skip over but inserts may reuse.

When to use / not use. Use open addressing for small fixed-size values and great cache performance (everything is in one contiguous array). Avoid it when the table gets very full — probe sequences lengthen sharply above ~0.7 load factor.

Pitfall. Blanking a deleted slot instead of using a tombstone makes later lookups return "not found" for keys that are actually present.

Knowledge check (predict the output): Keys A, B, C all hash to index 5 in a linear-probing table of capacity 8. In what slots do they end up after inserting A, then B, then C (assuming 6 and 7 are free)?

5. Load factor and resizing

Definition. Load factor = count / capacity. It measures fullness.

How it works. As the load factor rises, collisions multiply and operations slow down. When it crosses a threshold (commonly ~0.7), you resize: allocate a larger array (usually double the capacity) and rehash — reinsert every existing entry, because index = hash(key) % capacity changes when capacity changes. Resizing is O(n), but it happens rarely, which is why the amortised cost per insert stays O(1).

Pitfall. Copying buckets to the new array without recomputing indices. The old indices are meaningless under the new capacity; you must rehash each key.

Knowledge check (find the bug): A teammate resizes by memcpy-ing the old bucket array into a bigger one and freeing the old array. Lookups now fail for many keys. What did they forget?

Syntax notes

The pieces in C

#include <stdint.h>   /* uint32_t, fixed-width integers          */
#include <string.h>   /* strcmp, strlen for string keys          */

/* One stored entry; ->next links collisions in the same bucket. */
typedef struct Entry {
    char         *key;     /* owned copy of the key string        */
    int           value;
    struct Entry *next;     /* NULL = end of this bucket's chain   */
} Entry;

typedef struct {
    Entry **buckets;       /* array of 'capacity' list heads       */
    size_t  capacity;      /* number of buckets                    */
    size_t  count;         /* entries stored (for load factor)     */
} HashTable;

/* djb2 string hash, reduced to a valid index. */
static size_t hash_index(const char *key, size_t cap) {
    unsigned long h = 5381;
    for (const unsigned char *p = (const unsigned char *)key; *p; p++)
        h = h * 33u + *p;          /* mix every byte of the key   */
    return (size_t)(h % cap);      /* fold into 0 .. cap-1        */
}

Key points: the entry owns its key (we strdup it on insert and free it on removal), buckets is an array of pointers (each a list head), and count lets us compute the load factor without scanning.

Lesson

What a hash table is

A hash table stores entries in an array. Each entry's position is decided by its key.

To find the slot for a key, you compute:

index = hash(key) % capacity;

Here hash(key) turns the key into a number, and % capacity keeps that number inside the array bounds.

Handling collisions

A collision happens when two different keys map to the same slot. You need a way to store both. Two common strategies:

• Chaining: each slot (bucket) holds a linked list. Colliding entries are appended to that list.
• Open addressing: if a slot is taken, probe (search) for the next free slot and store the entry there.

Choosing a hash function

Pick a hash function that suits your key type.

For integer keys, Knuth's multiplicative hash is fast and good enough for most uses:

index = ((uint32_t)k * 2654435761u) % cap;

Code examples

Complete example: a string-to-int hash table (separate chaining)

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

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

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

static size_t hash_index(const char *key, size_t cap) {
    unsigned long h = 5381;
    for (const unsigned char *p = (const unsigned char *)key; *p; p++)
        h = h * 33u + *p;
    return (size_t)(h % cap);
}

/* Create a table; returns NULL if allocation fails. */
HashTable *ht_create(size_t capacity) {
    if (capacity == 0) capacity = 8;
    HashTable *t = malloc(sizeof *t);
    if (!t) return NULL;
    t->buckets = calloc(capacity, sizeof *t->buckets); /* all NULL */
    if (!t->buckets) { free(t); return NULL; }
    t->capacity = capacity;
    t->count    = 0;
    return t;
}

/* Grow and rehash when the load factor gets high. */
static int ht_resize(HashTable *t, size_t new_cap) {
    Entry **nb = calloc(new_cap, sizeof *nb);
    if (!nb) return 0;                       /* keep old table intact */
    for (size_t i = 0; i < t->capacity; i++) {
        Entry *e = t->buckets[i];
        while (e) {
            Entry *next = e->next;           /* save before relinking */
            size_t j = hash_index(e->key, new_cap); /* recompute index */
            e->next  = nb[j];                /* push onto new bucket  */
            nb[j]    = e;
            e        = next;
        }
    }
    free(t->buckets);
    t->buckets  = nb;
    t->capacity = new_cap;
    return 1;
}

/* Insert or update key -> value. Returns 1 on success, 0 on failure. */
int ht_put(HashTable *t, const char *key, int value) {
    if ((double)(t->count + 1) / t->capacity > 0.7)
        ht_resize(t, t->capacity * 2);       /* best-effort grow */

    size_t i = hash_index(key, t->capacity);
    for (Entry *e = t->buckets[i]; e; e = e->next)
        if (strcmp(e->key, key) == 0) { e->value = value; return 1; } /* update */

    Entry *e = malloc(sizeof *e);
    if (!e) return 0;
    e->key = strdup(key);                    /* own our own copy */
    if (!e->key) { free(e); return 0; }
    e->value      = value;
    e->next       = t->buckets[i];           /* prepend to chain */
    t->buckets[i] = e;
    t->count++;
    return 1;
}

/* Look up key. Writes the value through out and returns 1 if found. */
int ht_get(const HashTable *t, const char *key, int *out) {
    size_t i = hash_index(key, t->capacity);
    for (Entry *e = t->buckets[i]; e; e = e->next)
        if (strcmp(e->key, key) == 0) { *out = e->value; return 1; }
    return 0;
}

/* Remove key. Returns 1 if it was present. */
int ht_remove(HashTable *t, const char *key) {
    size_t i = hash_index(key, t->capacity);
    Entry **link = &t->buckets[i];           /* pointer to the link to fix */
    while (*link) {
        Entry *e = *link;
        if (strcmp(e->key, key) == 0) {
            *link = e->next;                 /* unlink */
            free(e->key);
            free(e);
            t->count--;
            return 1;
        }
        link = &e->next;
    }
    return 0;
}

/* Free every node, every key, and the table itself. */
void ht_free(HashTable *t) {
    if (!t) return;
    for (size_t i = 0; i < t->capacity; i++) {
        Entry *e = t->buckets[i];
        while (e) { Entry *n = e->next; free(e->key); free(e); e = n; }
    }
    free(t->buckets);
    free(t);
}

int main(void) {
    HashTable *t = ht_create(4);
    if (!t) { fprintf(stderr, "out of memory\n"); return 1; }

    ht_put(t, "apples",  3);
    ht_put(t, "bananas", 5);
    ht_put(t, "apples",  10);   /* updates existing key */

    int v;
    if (ht_get(t, "apples",  &v)) printf("apples  = %d\n", v);
    if (ht_get(t, "bananas", &v)) printf("bananas = %d\n", v);
    if (!ht_get(t, "cherries", &v)) printf("cherries not found\n");

    ht_remove(t, "apples");
    if (!ht_get(t, "apples", &v)) printf("apples removed\n");

    ht_free(t);   /* no leaks */
    return 0;
}

What it does. It builds a table mapping fruit names to counts, demonstrates insert, update, lookup (hit and miss), deletion, and a complete cleanup.

Expected output:

apples  = 10
bananas = 5
cherries not found
apples removed

Edge cases handled: allocation failure at every malloc/calloc/strdup; updating an existing key instead of duplicating it; resizing before the load factor exceeds 0.7; and ht_free(NULL) being safe. Compile with cc -std=c11 -Wall -Wextra -fsanitize=address,undefined ht.c to catch leaks and undefined behaviour. (strdup is POSIX; if your toolchain rejects it, add #define _POSIX_C_SOURCE 200809L at the top or write a tiny copy helper.)

Line by line

Walkthrough of the key operations

hash_index("apples", 4) — start h = 5381, then fold in each byte: h = h*33 + 'a', then + 'p', and so on for all six characters. The final h % 4 yields a number in 0..3. The whole string is consumed, so "apples" and "apricot" land in different chains.

ht_put(t, "apples", 3) with capacity 4:

ht_put(t, "apples", 10) — same index 1. The scan loop finds the existing node (strcmp == 0), so it sets e->value = 10 and returns without allocating. This is why duplicate keys never accumulate.

ht_get(t, "apples", &v) — recompute the index (1), walk the chain, match on strcmp, copy 10 into *v, return 1. The caller prints apples = 10.

ht_get(t, "cherries", &v) — compute its index, walk that chain, no strcmp matches, reach the end (NULL), return 0. The caller prints the "not found" branch.

ht_remove(t, "apples") — the link variable is a pointer to a pointer: it points at the slot or next field that currently references the node. When we find the node, *link = e->next splices it out in one assignment regardless of whether it was the list head or in the middle. Then free(e->key) and free(e) release both allocations and count drops.

Why resize is correct. In ht_resize, each node is re-hashed with the new capacity (hash_index(e->key, new_cap)) and pushed onto the new bucket array. We save e->next before overwriting it, or we would lose the rest of the chain. Only after all nodes move do we free the old array.

Common mistakes

Realistic mistakes and their fixes

1. Using the raw key as the index

/* WRONG */
size_t i = key_int % cap;   /* no mixing at all */

Why it is wrong: patterned keys (1, 2, 3, ... or all multiples of cap) cluster into a few buckets, turning O(1) into O(n).

/* CORRECT */
size_t i = (size_t)((uint32_t)key_int * 2654435761u) % cap;

Recognise it when lookups slow down as the table grows even though the load factor is low — the keys are colliding because they are not being mixed.

2. Storing the caller's string pointer instead of copying it

/* WRONG */
e->key = (char *)key;   /* caller may free or reuse this buffer */

Why it is wrong: the table now points at memory it does not own; if the caller frees or overwrites it, later lookups read garbage (a dangling pointer / use-after-free).

/* CORRECT */
e->key = strdup(key);
if (!e->key) { free(e); return 0; }

3. Blanking a slot on delete in open addressing

In a linear-probing table, setting a deleted slot back to "empty" cuts the probe chain, so keys inserted after it become unreachable. The fix is a tombstone marker that lookups skip but inserts can overwrite.

4. Forgetting to rehash on resize

Copying buckets verbatim into a bigger array leaves every entry at an index computed for the old capacity. Lookups recompute with the new capacity and miss. Always reinsert (rehash) each entry, as ht_resize does.

5. Leaking the chains

/* WRONG */
void ht_free(HashTable *t) { free(t->buckets); free(t); }

This frees the array of list heads but not the nodes or their strdup'd keys. Walk and free every node first (see the full ht_free).

Debugging tips

When it does not work

Compiler errors.

• implicit declaration of function 'strdup': add #define _POSIX_C_SOURCE 200809L before the includes, or supply your own copy helper.
• comparison of integer expressions of different signedness: prefer size_t for capacities and indices to silence -Wextra warnings and avoid surprises.
• incompatible pointer type on calloc(cap, sizeof *t->buckets): make sure buckets is declared Entry **.

Runtime errors.

• Segfault on lookup: usually a NULL buckets (allocation failed and you did not check) or dereferencing past the end of a chain. Run under AddressSanitizer (-fsanitize=address) — it pinpoints the bad access.
• Leaks reported by leaks/Valgrind/ASan: you freed nodes but not e->key, or you freed the table but not the chains.

Logic errors.

• Lookup returns wrong value: you are comparing keys with == (pointer identity) instead of strcmp (content). For strings always use strcmp.
• Duplicates appear: the insert path does not scan for an existing key before allocating.
• Performance degrades: print the load factor and the longest chain length. A long chain with a low load factor means a weak hash function.

Questions to ask: Did every allocation get checked? Am I mixing the whole key? Do insert, lookup, and resize all use the same hash_index with the same capacity? Did I save next before relinking during resize?

Memory safety

Memory safety and undefined behaviour for this topic

• Ownership of keys. The table must own its key strings. strdup makes a copy; free it exactly once in ht_remove and ht_free. Storing the caller's pointer risks use-after-free; freeing it twice is a double-free.
• Always check allocations. malloc, calloc, and strdup can return NULL. Dereferencing a NULL buckets or key is undefined behaviour (typically a crash). The example checks every one and unwinds partial allocations.
• Bounds. The index must come from % capacity. If capacity is ever 0, the modulo is undefined behaviour (division by zero); the constructor forces a minimum of 8.
• Lifetime during resize. Save e->next before you overwrite e->next, or you orphan the rest of the chain — a memory leak, and the entries vanish from the table.
• Integer overflow in the hash. h = h*33 + c on an unsigned long wraps around by definition — for unsigned types this is well-defined modular arithmetic, which is exactly what we want. Doing the same on a signed type would be undefined behaviour, so keep the accumulator unsigned.
• Verification. Build with -fsanitize=address,undefined and run your tests; on macOS the leaks tool and Valgrind elsewhere confirm a clean teardown.

Real-world uses

Real-world uses

• Language runtimes. Python dict, Java HashMap, JavaScript objects, Go map, and C++ unordered_map are all hash tables. When you write users[name], you are using one.
• Databases. Hash indexes and in-memory hash joins match rows by key in O(1) average time.
• Caches. An LRU cache pairs a hash table (key -> node) with a doubly linked list, giving O(1) lookup and eviction.
• Compilers and interpreters. Symbol tables map identifiers to their types and addresses; the hash table is consulted on every name reference.
• Networking and security. Routing tables, connection trackers, and de-duplication filters use hashing. Production hashes are seeded with a random value to prevent hash-flooding denial-of-service, where an attacker crafts many keys that collide and degrade the table to O(n).

Professional best practices

Beginner rules:

• Mix the whole key; never use raw key % cap.
• Check every allocation and free everything you allocate.
• Use strcmp for string keys, not ==.
• Keep one hash_index function so insert, lookup, and resize stay consistent.

Advanced rules:

• Track the load factor and resize (double capacity) around ~0.7 to amortise cost.
• Prefer powers-of-two capacities with a strong hash so you can replace % cap with a faster mask, or use a prime capacity to tame weak hashes.
• Seed the hash function with a random value in security-sensitive contexts.
• For open addressing, use tombstones and periodically rehash to reclaim them.
• Benchmark with your real key distribution; the "best" strategy depends on key size, deletion frequency, and cache behaviour.

Practice tasks

Practice

Beginner 1 — Word counter

Objective: count how many times each word appears in a fixed array of strings. Requirements: use the lesson's chaining table; for each word, ht_get it, add one (or insert with 1 if absent), then print every word with its count. Example: input {"a","b","a"} -> a=2, b=1 (order may vary). Hints: you only need ht_get and ht_put. Concepts: insert/update, lookup.

Beginner 2 — Contains / set membership

Objective: write int ht_contains(const HashTable *t, const char *key) returning 1 if the key exists, else 0. Requirements: reuse hash_index; do not modify the table; no value output needed. Constraints: O(1) average time. Hint: it is ht_get without the out parameter. Concepts: hashing, chain traversal.

Intermediate 1 — Print stats

Objective: add void ht_stats(const HashTable *t) that prints count, capacity, the load factor, and the longest chain length. Requirements: walk every bucket; track the maximum chain length seen. Output example: count=12 capacity=16 load=0.75 longest_chain=3. Hints: a long chain at a low load factor signals a weak hash. Concepts: load factor, collisions.

Intermediate 2 — Shrink on demand

Objective: add void ht_compact(HashTable *t) that halves the capacity (rehashing) when the load factor drops below 0.2, but never below capacity 8. Requirements: reuse ht_resize; verify all keys are still findable afterwards. Constraints: must not lose entries. Hint: mirror the grow path in ht_put. Concepts: rehashing, load factor.

Challenge — Open-addressing version with tombstones

Objective: reimplement the table with linear probing instead of chaining. Requirements: store entries inline in the array; mark slots EMPTY, OCCUPIED, or TOMBSTONE; implement insert (reusing tombstones), lookup (skipping tombstones, stopping at EMPTY), delete (writing a tombstone), and resize (rehash, dropping tombstones). Constraints: resize at load factor 0.7 counting tombstones; never enter an infinite probe loop. Input/output: same behaviour as the chaining version's main. Hints: the probe sequence is (start + i) % cap; lookup must stop at the first EMPTY but continue past TOMBSTONE. Concepts: open addressing, probing, tombstones, rehashing.

Summary

Summary

• A hash table maps keys to array slots via index = hash(key) % capacity, giving amortised O(1) lookup, insert, and delete.
• The hash function must mix the whole key; never use raw key % cap. Strings use functions like djb2; integers use a multiplicative hash.
• Collisions are unavoidable. Resolve them with separate chaining (a linked list per bucket) or open addressing / linear probing (probe to the next free slot, and use tombstones for deletion).
• The load factor (count / capacity) drives performance; resize and rehash around ~0.7 to keep operations near O(1).
• Most important syntax: Entry **buckets, hash_index(key, cap), strdup for owned keys, strcmp for comparison, and a full free of every node and key.
• Common mistakes: raw-key indexing, storing the caller's pointer, blanking deleted open-addressing slots, copying buckets without rehashing, and leaking chains.
• Remember: the array gives O(1) indexing (from Arrays), the struct groups each entry (from Structs), and the hash function decides which index — that is the whole idea.

Practice with these exercises

• Find a free slot (linear probing)
• Lookup with linear probing