C · 4 · Dynamic Memory & Data Structures21 / 35 · 60%

Hash Tables from Scratch

Buckets, a hash function, and a collision strategy.

Examples: FNV-1a, chaining, load factor

shortcuts: ← prev · → next · M mark

A Good Hash

FNV-1a is short, fast and good enough for in-process tables.

Example

example

uint64_t fnv1a(const char *s) {
    uint64_t h = 1469598103934665603ULL;
    while (*s) {
        h ^= (unsigned char)*s++;
        h *= 1099511628211ULL;
    }
    return h;
}

Separate Chaining

Each bucket holds a linked list of entries.

Example

example

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

typedef struct { Entry **buckets; size_t nbuckets, count; } Map;

size_t idx = fnv1a(key) % map->nbuckets;

bucket → entry → entry

Load Factor & Rehash

Grow when count / buckets exceeds ~0.75, or lookups degrade.

Example

example

1
2

if ((double)map->count / map->nbuckets > 0.75)
    map_rehash(map, map->nbuckets * 2);   // reinsert every entry

WATCH OUT

Use a power-of-two bucket count with a masked index, or a prime with modulo — mixing the two badly clusters keys.

Cost

Average vs worst case.

Complexity

insert	O(1) avg	O(n) if all keys collide
lookup	O(1) avg
delete	O(1) avg
rehash	O(n)	amortized away