Hash Tables

A hash table maps a key to a value in roughly constant time by computing a hash of the key, using it to pick a "bucket," and resolving any collisions (two keys hashing to the same bucket) with a linked list at that bucket:

#define TABLE_SIZE 128

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

Entry *table[TABLE_SIZE];

unsigned int hash(const char *key) {
    unsigned int h = 0;
    for (int i = 0; key[i] != '\0'; i++) {
        h = h * 31 + key[i];
    }
    return h % TABLE_SIZE;
}

void put(const char *key, int value) {
    unsigned int index = hash(key);
    Entry *entry = malloc(sizeof(Entry));
    strcpy(entry->key, key);
    entry->value = value;
    entry->next = table[index]; // insert at the head of this bucket
    table[index] = entry;
}

This is a simplified version of what powers Map/HashMap/dict in every higher-level language you've likely used — building it once by hand makes the O(1)-on-average, worse-case-O(n) trade-off concrete rather than abstract.