Hash Tables

A hash table maps keys to values using a hash function that converts a key into an array index. Instead of scanning a list to find something (O(n)), you compute the index directly and jump straight to it — giving average-case O(1) lookup, insertion, and deletion. Hash tables back many real-world tools: dictionaries, caches, symbol tables in compilers, and database indexes.

The Core Idea

A hash function takes a key (e.g. a string) and produces an integer.
That integer is reduced (usually with % tableSize) to a valid array index — a bucket.
The value is stored in that bucket, so future lookups for the same key land in the same place.
Two different keys can hash to the same bucket — a collision — which must be handled.

A Simple Hash Function for Strings

A common approach for hashing strings sums (or multiplies) the character codes together, then reduces the result modulo the table size. This particular formula is a small variant of the well-known djb2 algorithm.

unsigned int hashString(const char *key, unsigned int tableSize) {
    unsigned long hash = 5381;
    int c;

    while ((c = *key++) != '\0') {
        hash = ((hash << 5) + hash) + (unsigned long)c; /* hash * 33 + c */
    }

    return (unsigned int)(hash % tableSize);
}

Handling Collisions with Chaining

The simplest way to deal with collisions is separate chaining: each bucket is not a single slot but the head of a linked list. If two keys hash to the same bucket, they simply both live in that bucket's list, and lookup walks the (usually very short) list to find the matching key.

Worked Example: A String-to-Int Hash Table

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

#define TABLE_SIZE 16

typedef struct Entry {
    char *key;
    int value;
    struct Entry *next; /* next entry in this bucket's chain */
} Entry;

typedef struct {
    Entry *buckets[TABLE_SIZE];
} HashTable;

void initTable(HashTable *table) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        table->buckets[i] = NULL;
    }
}

unsigned int hashString(const char *key) {
    unsigned long hash = 5381;
    int c;
    while ((c = *key++) != '\0') {
        hash = ((hash << 5) + hash) + (unsigned long)c;
    }
    return (unsigned int)(hash % TABLE_SIZE);
}

void tableSet(HashTable *table, const char *key, int value) {
    unsigned int index = hashString(key);
    Entry *entry = table->buckets[index];

    /* If the key already exists, update its value. */
    while (entry != NULL) {
        if (strcmp(entry->key, key) == 0) {
            entry->value = value;
            return;
        }
        entry = entry->next;
    }

    /* Otherwise, insert a new entry at the head of the chain. */
    Entry *newEntry = malloc(sizeof(Entry));
    newEntry->key = strdup(key);
    newEntry->value = value;
    newEntry->next = table->buckets[index];
    table->buckets[index] = newEntry;
}

int tableGet(HashTable *table, const char *key, int *outValue) {
    unsigned int index = hashString(key);
    Entry *entry = table->buckets[index];

    while (entry != NULL) {
        if (strcmp(entry->key, key) == 0) {
            *outValue = entry->value;
            return 1; /* found */
        }
        entry = entry->next;
    }
    return 0; /* not found */
}

void freeTable(HashTable *table) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        Entry *entry = table->buckets[i];
        while (entry != NULL) {
            Entry *next = entry->next;
            free(entry->key);
            free(entry);
            entry = next;
        }
    }
}

int main(void) {
    HashTable table;
    initTable(&table);

    tableSet(&table, "apples", 10);
    tableSet(&table, "bananas", 25);
    tableSet(&table, "cherries", 100);
    tableSet(&table, "apples", 15); /* updates the existing key */

    int value;
    if (tableGet(&table, "bananas", &value)) {
        printf("bananas -> %d\n", value);
    }
    if (tableGet(&table, "apples", &value)) {
        printf("apples -> %d\n", value);
    }
    if (!tableGet(&table, "grapes", &value)) {
        printf("grapes -> not found\n");
    }

    freeTable(&table);
    return 0;
}

Note

`strdup` (from `string.h` on POSIX systems, C23-standard elsewhere) allocates a copy of the string — the hash table owns its own copy of each key rather than pointing into caller-owned memory that might change or be freed later.

Why Average O(1)?

As long as the hash function spreads keys roughly evenly across buckets, and the table isn't overloaded (too many entries per bucket), each chain stays short — typically length 0 or 1 — so lookup is essentially a single hash computation plus a very short walk.

Chaining vs Open Addressing

Aspect	Separate chaining	Open addressing
Collision handling	Linked list per bucket	Probe for the next free slot in the array
Memory	Extra pointers per node	No extra pointers, but needs empty slots
Worst case	Degrades gracefully (longer chains)	Can degrade badly if the table fills up
Implementation	Simpler to reason about	More complex (probing, deletion tombstones)

Tip

A good hash function is the single biggest factor in hash table performance — a poor one that clusters keys into a few buckets turns your O(1) lookups into O(n) linked-list scans.

Warning

This example is a teaching implementation. A production-grade hash table also needs automatic resizing (rehashing) as the load factor grows, better collision resistance against adversarial input, and careful memory management — libraries like `glib`'s `GHashTable` or C++'s `std::unordered_map` handle all of that for you.