Hash Table

Data Structures O(1) average O(n)

Maps keys to buckets with a hash function; collisions are chained as linked lists inside each bucket.

∅

Pick an operation to walk through the code.

InvariantEvery key sits in bucket hash(key), so a lookup scans one chain instead of the whole table.

hash-table.c

#define BUCKETS 8
 
typedef struct Entry {
    int key;
    struct Entry *next;
} Entry;
 
Entry *table[BUCKETS];
 
int hash(int key) {
    return ((key % BUCKETS) + BUCKETS) % BUCKETS;
}
 
void insert(int key) {
    int b = hash(key);
    Entry *e = malloc(sizeof(Entry));
    e->key = key;
    e->next = table[b];   /* chain on collision */
    table[b] = e;
}
 
int contains(int key) {
    for (Entry *e = table[hash(key)]; e; e = e->next)
        if (e->key == key) return 1;
    return 0;
}

How Hash Table works

A hash function maps each key to one of a few buckets. Lookups jump straight to the right bucket and only walk its (short) chain of colliding keys.

Best case

Even spread — chains of length ~1: O(1) per operation.

Worst case

All keys collide into one bucket: O(n) chain walk.

When to use it

The default dictionary/set: constant-time lookups when order doesn't matter.