Hashing — turning keys into table indices

Overview

A hash table is the data structure behind almost every "look something up by name" feature you have ever used: a dictionary, a phone book, a cache, a symbol table. You give it a key (like the word "cat") and it hands back the value you stored under that key (like the definition) — and it does this in roughly constant time, no matter how many entries the table holds.

The magic ingredient is a hash function. Instead of scanning every stored key one by one (which is what the searching lesson taught with linear and binary search), a hash function takes the raw bytes of a key and mixes them into a single integer. That integer, squeezed into the range of an array, tells you exactly which slot to look in. No scan of the whole table — you jump straight to the right shelf.

This builds directly on two things you already know. From Arrays, you know that an array gives instant access to element arr[i] if you know the index i. From Structs, you know how to bundle a key and a value together into one record. A hash table combines them: the hash function computes the index i, the array holds "buckets," and each bucket stores structs (key/value records).

In plain language: a hash function is a repeatable way to turn any key into a number, and a hash table is an array you index with that number. The rest of this lesson is about doing that correctly — handling the inevitable cases where two different keys produce the same number, cleaning up memory, and keeping the table fast even when an attacker is deliberately trying to slow it down.

Why it matters

Hash tables are one of the most-used data structures in all of computing, and in C they are usually built by hand rather than pulled from a standard library, so understanding the mechanics matters.

Wherever a program maps keys to values, a hash table is almost certainly involved:

• Operating systems use them for page caches, file-descriptor tables, and network route lookups.
• The C runtime and linkers use them for symbol tables — resolving printf to an address.
• Every higher-level language (Python dict, JavaScript objects, Ruby hashes) is implemented in C or C++ and sits on top of a hash table.
• Databases and web servers use them for in-memory indexes and session stores.
• Compilers use them to track variable names in each scope.

Beyond raw usefulness, hashing teaches a mindset you will reuse constantly: taking messy, variable-sized input and reducing it to a compact, fixed-size fingerprint. That same idea powers checksums, deduplication, content-addressable storage, and — with cryptographic hashes — password storage and digital signatures. And because a poorly built hash table can be attacked (the HashDoS problem covered later), it is also your first taste of writing data structures that stay fast even when the input is hostile.

Core concepts

1. The hash function

Definition: A hash function takes a key (here, the bytes of a string) and returns a fixed-size integer called the hash value or digest. The same key always produces the same hash (it is deterministic), and good hash functions spread different keys evenly across the whole range of integers.

Plain-language explanation: Think of it as a meat grinder for data. Whatever you feed in — a 3-letter word or a 3,000-character URL — a single number comes out. Two different inputs usually give different numbers, and small changes in the input ("cat" vs "car") scatter to completely different outputs.

How it works internally: A typical non-cryptographic hash walks the bytes one at a time, folding each byte into a running accumulator using cheap operations — multiply, XOR, shift. FNV-1a, which we use below, starts from a fixed "offset basis," then for each byte does hash = (hash XOR byte) * prime. The multiplication by a large odd prime scrambles the bits so that the influence of each byte spreads across the whole word.

FNV-1a walking the key "Hi":

  start:  h = 2166136261
          |
  'H'(72):  h = (h XOR 72)  -> then h = h * 16777619
          |
  'i'(105): h = (h XOR 105) -> then h = h * 16777619
          |
  result: h = 0x... (a 32-bit fingerprint of "Hi")

When to use / when NOT to: Use a fast hash like FNV-1a or DJB2 for ordinary in-memory tables where the keys come from inside your program. Do NOT use them when the keys come from untrusted users over a network — an attacker who knows the algorithm can craft keys that all collide (see concept 5). And never use FNV-1a/DJB2 for passwords or security tokens; those need a cryptographic hash (SHA-256, or better, a password hash like Argon2).

Common pitfall: Forgetting to cast each byte to unsigned char before mixing it in. If char is signed on your platform, a byte like 0xE9 becomes a negative number, and the sign-extension corrupts the hash so it differs between platforms.

Knowledge check: In your own words, why must a hash function be deterministic? What would break in a hash table if hash("cat") returned a different number each time you called it?

2. From hash value to bucket index

Definition: The bucket index is the array position a key maps to. Because the hash value is a huge 32- or 64-bit number but your array only has, say, 16 slots, you must reduce the hash into the range 0 .. nbuckets-1.

Plain-language explanation: The hash gives you a giant ticket number; the bucket index is that ticket number wrapped around to fit the number of shelves you actually have.

How it works internally: The standard reduction is hash % nbuckets (remainder after division). If nbuckets is a power of two, the faster equivalent is hash & (nbuckets - 1), which just keeps the low bits.

hash = 0x9E3779B1 (a big number)
nbuckets = 8

hash % 8  ==  hash & 7  ==  keep low 3 bits  ->  bucket 1

 buckets:  [0][1][2][3][4][5][6][7]
               ^-- key lands here

When to use / when NOT to: Use the bit-mask form when you control the hash quality and size buckets as powers of two (common in high-performance tables). Do NOT use the bit-mask form with a weak hash whose low bits are poorly mixed — you throw away the good high bits and invite collisions.

Common pitfall: Taking hash % nbuckets when nbuckets is 0 — that is a divide-by-zero crash. Always create the table with a non-zero bucket count.

3. Collisions

Definition: A collision happens when two different keys map to the same bucket index. Because you are squeezing a near-infinite set of keys into a small array, collisions are not a bug — they are mathematically guaranteed (the pigeonhole principle).

Plain-language explanation: Two people whose names both start the table at shelf 3. The table is not broken; it just needs a rule for storing more than one item on a shelf.

"cat" hashes to bucket 3
"dog" also hashes to bucket 3   <-- collision!

 buckets:  [0][1][2][3][4][5]
                    |
                 [cat|9] -> [dog|4] -> NULL   (chaining)

When collisions matter: A few are fine and expected. Many collisions in one bucket destroy performance, turning an O(1) lookup back into an O(n) scan.

Common pitfall: Assuming a "good" hash means no collisions. Even a perfect hash produces collisions once you have more keys than buckets. The goal is few and evenly spread, not zero.

Knowledge check (predict the output): A table has 4 buckets. Keys "a", "b", "c", "d", "e" are inserted. What is the minimum number of buckets that must contain at least two keys? (Hint: pigeonhole — 5 keys, 4 buckets.)

4. Collision resolution: chaining vs open addressing

Definition: A collision resolution strategy is the rule for storing multiple keys that land in the same bucket.

Chaining keeps a linked list (a "chain") in each bucket; colliding entries are appended to the list. Open addressing stores everything in the array itself; on collision it probes other buckets by a fixed rule until it finds an empty slot.

CHAINING                          OPEN ADDRESSING (linear probe)

bucket[3] -> [cat] -> [dog] -> X   bucket[3] = cat
                                   bucket[4] = dog  (3 was full, try 4)
bucket[5] -> [fox] -> X            bucket[5] = fox

When to use / when NOT to: Reach for chaining when you are learning, when deletions are frequent, or when the entry count is unpredictable — it degrades gracefully. Reach for open addressing when raw speed and cache locality matter and you can keep the load factor low (say under 0.7). Do NOT use open addressing with a near-full table; it slows to a crawl as it probes long runs of occupied slots.

Common pitfall (chaining): Inserting a key that already exists as a new node instead of updating the existing one, so the table holds two entries for the same key and lookups return the stale one.

5. The security angle: HashDoS and load factor

Definition: HashDoS (hash denial-of-service) is an attack where a client deliberately sends many keys engineered to collide into the same bucket. Every insert and lookup then walks a giant chain, and O(1) collapses to O(n), freezing the server with modest traffic.

The load factor is entries / nbuckets — how full the table is on average. High load factor means longer chains and slower operations regardless of attacker involvement.

Plain-language explanation: If an attacker knows your hash function is FNV-1a with no secret, they can compute thousands of strings that all hash to bucket 0. Your "fast" table now has one bucket holding a 10,000-item linked list, and every request scans all 10,000.

The defensive fix: Use a keyed hash such as SipHash, seeded with a random secret chosen once per process. The attacker cannot predict which keys collide because they do not know the secret, so they cannot craft the attack. Additionally, monitor the load factor and rehash (allocate a bigger bucket array and re-insert everything) when it exceeds about 0.75.

Common pitfall: Using a fixed, hard-coded seed "for reproducibility." A constant seed is no seed at all — the attacker just includes it in their collision search. The seed must be random per process (e.g. from getrandom or /dev/urandom).

Knowledge check (explain-in-your-own-words): Why does a secret, random seed defeat HashDoS, while merely switching from FNV-1a to a "more complicated but public" hash does not?

Syntax notes

The core building blocks are a per-entry struct (from the Structs lesson) and an array of pointers to those structs (from the Arrays lesson):

#include <stdint.h>   /* uint32_t */
#include <stddef.h>   /* size_t   */

/* One key/value record; `next` links entries that collide in the same bucket. */
typedef struct entry {
    char          *key;   /* owned copy of the key string  */
    int            val;   /* the stored value              */
    struct entry  *next;  /* next entry in this bucket's chain, or NULL */
} entry_t;

/* The table itself: an array of chain heads plus bookkeeping. */
typedef struct {
    entry_t **buckets;    /* buckets[i] is the head of bucket i's chain */
    size_t    nbuckets;   /* array length (never 0)                     */
    size_t    count;      /* number of stored entries (for load factor) */
} table_t;

Key idea: buckets is an array of pointers. Each element is either NULL (empty bucket) or points to the first entry_t in that bucket's linked list. count / nbuckets is the load factor.

Lesson

A hash function maps a variable-length key to a fixed-size integer (the hash).

A hash table uses that integer, modulo the bucket count, to locate a slot.

Collisions are inevitable. Two ways to handle them:

• Chaining: a linked list per bucket.
• Open addressing: probe other buckets.

Code examples

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

typedef struct entry {
    char         *key;
    int           val;
    struct entry *next;
} entry_t;

typedef struct {
    entry_t **buckets;
    size_t    nbuckets;
    size_t    count;
} table_t;

/* FNV-1a 32-bit hash. Cast to unsigned char so high bytes never sign-extend. */
static uint32_t fnv1a(const char *s) {
    uint32_t h = 2166136261u;              /* FNV offset basis */
    while (*s) {
        h ^= (uint8_t)*s++;                /* fold in one byte */
        h *= 16777619u;                    /* scramble with the FNV prime */
    }
    return h;
}

static table_t *table_create(size_t nbuckets) {
    if (nbuckets == 0) return NULL;                    /* guard divide-by-zero */
    table_t *t = malloc(sizeof *t);
    if (!t) return NULL;
    t->buckets = calloc(nbuckets, sizeof *t->buckets); /* all heads start NULL */
    if (!t->buckets) { free(t); return NULL; }
    t->nbuckets = nbuckets;
    t->count = 0;
    return t;
}

/* Insert or update. Returns 1 on success, 0 on allocation failure. */
static int table_set(table_t *t, const char *key, int val) {
    size_t i = fnv1a(key) % t->nbuckets;
    for (entry_t *e = t->buckets[i]; e; e = e->next) {
        if (strcmp(e->key, key) == 0) {  /* key exists -> update, don't duplicate */
            e->val = val;
            return 1;
        }
    }
    entry_t *e = malloc(sizeof *e);
    if (!e) return 0;
    e->key = strdup(key);                /* own our own copy of the key */
    if (!e->key) { free(e); return 0; }
    e->val = val;
    e->next = t->buckets[i];             /* push onto front of the chain */
    t->buckets[i] = e;
    t->count++;
    return 1;
}

/* Look up. Returns 1 and writes *out if found, else 0. */
static int table_get(const table_t *t, const char *key, int *out) {
    size_t i = fnv1a(key) % t->nbuckets;
    for (entry_t *e = t->buckets[i]; e; e = e->next) {
        if (strcmp(e->key, key) == 0) { *out = e->val; return 1; }
    }
    return 0;
}

static void table_destroy(table_t *t) {
    if (!t) return;
    for (size_t i = 0; i < t->nbuckets; i++) {
        entry_t *e = t->buckets[i];
        while (e) {
            entry_t *next = e->next;     /* save before freeing */
            free(e->key);                /* free the strdup'd key */
            free(e);                     /* then the node itself  */
            e = next;
        }
    }
    free(t->buckets);
    free(t);
}

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

    table_set(t, "cat", 9);
    table_set(t, "dog", 4);
    table_set(t, "cat", 12);   /* updates, does not duplicate */

    int v;
    if (table_get(t, "cat", &v)) printf("cat = %d\n", v);
    if (table_get(t, "dog", &v)) printf("dog = %d\n", v);
    if (!table_get(t, "fish", &v)) printf("fish not found\n");

    printf("load factor = %.2f\n", (double)t->count / t->nbuckets);

    table_destroy(t);
    return 0;
}

What it does: Builds a small string-to-int hash table with 8 buckets and separate chaining. It stores cat=9 and dog=4, then re-sets cat to 12 (demonstrating update-in-place rather than duplicate insertion), looks three keys up, prints the load factor, and frees everything.

Expected output:

cat = 12
dog = 4
fish not found
load factor = 0.25

Key edge cases: A NULL return from table_create on zero buckets or allocation failure; table_set returning 0 if malloc/strdup fails (the caller should check in production); looking up a key that was never inserted (returns 0, leaves *out untouched); and re-setting an existing key, which must update the value in place.

Line by line

We trace the two most important operations: inserting cat, then re-setting cat.

1. table_create(8) allocates a table_t, then calloc(8, ...) gives an 8-element array of entry_t *, every element zeroed to NULL. nbuckets = 8, count = 0.
2. table_set(t, "cat", 9) computes fnv1a("cat"), a 32-bit number; % 8 reduces it to some bucket, say index 3.
3. The for loop scans buckets[3], which is NULL, so the loop body never runs — the key is new.
4. malloc creates a fresh entry_t. strdup("cat") allocates a private 4-byte copy of the string (c a t \0) so the table does not depend on the caller's buffer.
5. e->val = 9. Then e->next = buckets[3] (which is NULL), and buckets[3] = e. The node is now the head of bucket 3's chain. count becomes 1.
6. table_set(t, "dog", 4) similarly lands in whichever bucket fnv1a("dog") % 8 gives. If it differs from 3, it starts its own chain; count becomes 2.
7. table_set(t, "cat", 12) hashes to bucket 3 again. This time the for loop finds the existing node where strcmp(e->key, "cat") == 0 is true, so it runs e->val = 12 and returns without allocating. count stays 2 — no duplicate.

Memory picture just before the update returns:

buckets[3] --> [ key="cat" | val=12 | next=NULL ]
buckets[?] --> [ key="dog" | val=4  | next=NULL ]
count = 2, nbuckets = 8

8. table_get(t, "cat", &v) re-hashes "cat" to bucket 3, walks the one-node chain, matches, writes *out = 12, returns 1 — so printf shows cat = 12.
9. table_get(t, "fish", &v) hashes to some bucket whose chain does not contain "fish"; the loop ends, returns 0, and we print fish not found.
10. table_destroy walks each bucket, and for every node frees e->key (the strdup copy) then e — saving e->next first so we don't read freed memory. Finally it frees the buckets array and the table_t.

Common mistakes

Mistake 1 — signed char corrupting the hash.

/* WRONG: on platforms where char is signed, bytes >= 128 sign-extend */
h ^= *s++;               /* *s is 'char'; 0xE9 becomes negative */

Why it is wrong: the negative value sign-extends to 0xFFFFFF...E9 before the XOR, so identical strings hash differently on signed vs unsigned platforms, and non-ASCII keys distribute badly. Fix: cast to unsigned char.

h ^= (uint8_t)*s++;      /* CORRECT */

Recognise it when: a table works on one machine but mis-lookups accented/UTF-8 keys on another.

Mistake 2 — inserting a duplicate instead of updating.

/* WRONG: always allocates, ignoring an existing key */
entry_t *e = malloc(sizeof *e);
e->key = strdup(key); e->val = val;
e->next = t->buckets[i]; t->buckets[i] = e;

Why it is wrong: after set("cat",9) then set("cat",12), bucket 3 holds two cat nodes. get("cat") returns whichever is first (12), but memory now leaks the older intent and count overstates size, skewing the load factor. Fix: scan the chain first and update in place if the key is found (as the lesson code does).

Mistake 3 — not copying the key.

/* WRONG: stores the caller's pointer, not a copy */
e->key = (char *)key;

Why it is wrong: if the caller passed a stack buffer or later frees/overwrites that string, the table now points at garbage — a dangling pointer and wrong lookups. Fix: e->key = strdup(key); and free it in table_destroy.

Mistake 4 — power-of-two size with the low bits of a weak hash.

size_t i = weak_hash(key) & (nbuckets - 1);  /* keeps only low bits */

Why it is wrong: if weak_hash barely mixes its low bits, many keys share the same low bits and pile into a few buckets. Fix: use a well-mixing hash (FNV-1a mixes across the whole word) or mix the high bits down before masking. Recognise it by measuring chain lengths — one bucket far longer than the rest.

Debugging tips

Compiler errors

• implicit declaration of strdup: strdup is POSIX, not ISO C. Compile with -D_POSIX_C_SOURCE=200809L or -std=gnu11, or write your own my_strdup with malloc+memcpy.
• uint32_t/size_t unknown: include <stdint.h> and <stddef.h>.

Runtime errors

• Segfault on lookup: usually t or t->buckets is NULL because you didn't check table_create's return, or you dereferenced a bucket after table_destroy.
• Divide-by-zero / floating point exception: nbuckets is 0. Guard it at creation time.
• Crash in table_destroy: you freed e before reading e->next. Always save next first.
• Run under valgrind ./a.out (or -fsanitize=address,undefined) to catch leaks, use-after-free, and the signed-char UB.

Logic errors

• Every key lands in the same bucket: your hash returns a constant, or you reduced with a broken modulus. Print fnv1a(key) and fnv1a(key) % nbuckets for several keys and confirm they differ.
• A key you inserted "isn't there": you compared pointers (e->key == key) instead of contents (strcmp). Two equal strings can live at different addresses.
• Load factor climbs but lookups slow down: chains are long — time to rehash.

Questions to ask when it doesn't work: Did table_create succeed? Is nbuckets non-zero? Am I comparing with strcmp, not ==? Did I strdup the key? For every malloc/strdup, is there exactly one matching free?

Memory safety

Hashing in C is an ownership exercise: the table owns copies of every key and every node, and must free each exactly once.

• Initialisation: calloc (not malloc) for the bucket array so every head starts NULL; an uninitialised bucket pointer walked as a chain is undefined behaviour.
• Ownership & lifetime: Store a strdup copy of each key, never the caller's pointer, so the entry outlives the caller's buffer. Free that copy in table_destroy.
• Double-free / use-after-free: In the destroy loop, save e->next before free(e). Freeing e then reading e->next is use-after-free. After destroy, set t = NULL in the caller to avoid touching freed memory.
• Bounds & overflow: Reduce the hash with % nbuckets (or a mask) so the index is always in range; never index buckets[hash] directly. count / nbuckets is fine, but guard nbuckets != 0.
• Every allocation checked: malloc, calloc, and strdup can return NULL. The lesson code checks each and unwinds partial allocations (free the node if its strdup fails).

Security note (HashDoS): Although this lesson's category is not "security," the same table becomes a denial-of-service vulnerability the moment its keys come from untrusted input. Vulnerability: a public FNV-1a lets an attacker precompute thousands of colliding keys, forcing one enormous chain and O(n) lookups. Defensive fix: for externally supplied keys use SipHash seeded with a per-process random secret (from getrandom//dev/urandom), and cap or rehash long chains. Never hard-code the seed — a constant seed is equivalent to no seed. And never use these table hashes for passwords; use a purpose-built password hash (Argon2/bcrypt).

Real-world uses

Concrete uses: getenv walks a hash-table-like environment; DNS resolvers cache name→address mappings in hash tables; language interpreters (CPython, Lua, Ruby) implement their core dict/table type as a C hash table; web servers hash request paths to route handlers and session IDs to session data; compilers keep a symbol table per scope; the Linux kernel hashes inodes, dentries, and network connections.

Professional best-practice habits

Beginner:

• Give the table a clear API (create, set, get, destroy) and keep hashing details private (static).
• Always copy keys, check every allocation, and pair every malloc with a free — run valgrind until it reports zero leaks.
• Name things for meaning (nbuckets, count, load_factor), and guard nbuckets != 0.

Advanced:

• Track the load factor and rehash to a larger array (typically doubling) above ~0.75 to keep chains short; amortised cost stays O(1).
• For untrusted keys, switch to a keyed hash (SipHash) with a random per-process seed to neutralise HashDoS.
• Consider open addressing with good probing (Robin Hood, quadratic) when cache performance dominates and deletions are rare, and benchmark against real key distributions rather than guessing.
• Keep the hash function and the reduction independent so you can swap either without rewriting the table.

Practice tasks

1. (Beginner) Implement and test FNV-1a. Write uint32_t fnv1a(const char *s) exactly as in the lesson. Print the hash of "cat", "car", and "cat" again.

• Requirements: identical inputs must print identical numbers; "cat" and "car" must differ widely.
• Constraint: cast each byte to unsigned char.
• Concepts: hash function, determinism.

2. (Beginner) Bucket distribution histogram. Given nbuckets = 8 and the words apple banana cherry date egg fig grape, print each word's bucket index (fnv1a(word) % 8) and a count of how many words land in each bucket.

• Example output line: banana -> bucket 5.
• Concept: reduction to a bucket index, observing collisions.

3. (Intermediate) String→int table with chaining. Build table_create/set/get/destroy as in the lesson. Insert 6 key/value pairs (including one repeated key to test update-in-place), look them all up, and confirm valgrind reports no leaks.

• Requirement: set must update, not duplicate, an existing key.
• Concepts: chaining, ownership, cleanup.

4. (Intermediate) Word-frequency counter. Read words from standard input (scanf("%255s", buf)), and for each word increment its count in the table (start at 0 if new). At EOF, print each word and its count.

• Input example: the cat sat on the mat → the 2, others 1.
• Concepts: get-then-set pattern, dynamic key insertion.

5. (Challenge) Auto-rehashing table. Extend task 3 so that after each insert, if count / nbuckets > 0.75, you allocate a new bucket array of double the size, re-insert every existing entry into it (recomputing each bucket index), free the old array, and update nbuckets.

• Requirements: no entry lost or duplicated; keys keep their strdup copies (move the nodes, don't re-strdup); valgrind clean.
• Hint: iterate the old buckets, unlink each node, and push it onto the correct new bucket.
• Concepts: load factor, rehashing, pointer surgery without leaks.

Summary

A hash table is three parts working together: a hash function that turns a key into a fixed-size integer, a bucket array you index with that integer, and a collision-resolution strategy for keys that share a bucket. The essential syntax is an entry_t struct with a next pointer and an array of chain heads (entry_t **buckets); the essential operations are fnv1a(key) % nbuckets to find the bucket and a strcmp walk down the chain to find the key.

Use FNV-1a or DJB2 for trusted, internal keys; use SipHash with a random per-process seed for untrusted keys to defeat HashDoS; never use table hashes for passwords. Choose chaining for simplicity and easy deletion, open addressing for cache speed at low load factors.

The most common mistakes are forgetting (unsigned char) casts, storing the caller's key pointer instead of a strdup copy, inserting duplicates instead of updating, and leaking nodes or keys on destroy. Remember to track the load factor and rehash above ~0.75, guard against a zero bucket count, and free every key and node exactly once. Master this and you understand the data structure that underpins nearly every dictionary in modern software — and the next lesson, Hash tables, builds a complete one on this foundation.

Practice with these exercises

• djb2 string hash
• Map a hash to a bucket
• Int→int hash table (open addressing)
• Final Project: tiny key-value store
• Are two strings anagrams of each other?