A hash table maps keys to values in O(1) average time. C’s standard library doesn’t provide one, so you either use a third-party library or write your own. Writing one from scratch teaches you how hash functions, collision resolution, and load factors actually work — knowledge that makes you a better user of every hash table you’ll ever use.

The Core Idea

A hash table is an array of buckets. To insert a key-value pair:

  1. Hash the key to get an index into the array
  2. Handle collisions (when two keys hash to the same index)
  3. Store the key-value pair at that bucket

A Simple Hash Function

#include <stddef.h>
#include <string.h>

/* FNV-1a hash — fast, good distribution for strings */
size_t hash_string(const char *key, size_t capacity) {
    size_t hash = 2166136261U;   /* FNV offset basis */
    while (*key) {
        hash ^= (unsigned char)*key++;
        hash *= 16777619U;       /* FNV prime */
    }
    return hash % capacity;
}

Good hash functions distribute keys uniformly across buckets and are fast to compute. FNV-1a is a practical choice for string keys — simple to implement, good performance. Never use strlen % capacity — it hashes all strings of the same length to the same bucket.

Separate Chaining Implementation

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

#define INITIAL_CAPACITY 16
#define LOAD_FACTOR      0.75

typedef struct Entry {
    char        *key;
    int          value;
    struct Entry *next;   /* chain for collisions */
} Entry;

typedef struct {
    Entry  **buckets;
    size_t   count;
    size_t   capacity;
} HashMap;

HashMap *hashmap_new(void) {
    HashMap *map = malloc(sizeof(HashMap));
    map->capacity = INITIAL_CAPACITY;
    map->count    = 0;
    map->buckets  = calloc(INITIAL_CAPACITY, sizeof(Entry*));
    return map;
}

size_t hash_key(const char *key, size_t capacity) {
    size_t h = 2166136261U;
    while (*key) { h ^= (unsigned char)*key++; h *= 16777619U; }
    return h % capacity;
}

void hashmap_put(HashMap *map, const char *key, int value) {
    size_t idx = hash_key(key, map->capacity);
    Entry *e   = map->buckets[idx];

    /* Update if key exists */
    while (e) {
        if (strcmp(e->key, key) == 0) { e->value = value; return; }
        e = e->next;
    }

    /* Insert new entry at head of chain */
    Entry *new_entry  = malloc(sizeof(Entry));
    new_entry->key    = strdup(key);
    new_entry->value  = value;
    new_entry->next   = map->buckets[idx];
    map->buckets[idx] = new_entry;
    map->count++;
}

int hashmap_get(const HashMap *map, const char *key, int *out) {
    size_t idx = hash_key(key, map->capacity);
    Entry *e   = map->buckets[idx];
    while (e) {
        if (strcmp(e->key, key) == 0) { *out = e->value; return 1; }
        e = e->next;
    }
    return 0;  /* not found */
}

void hashmap_free(HashMap *map) {
    for (size_t i = 0; i < map->capacity; i++) {
        Entry *e = map->buckets[i];
        while (e) {
            Entry *next = e->next;
            free(e->key);
            free(e);
            e = next;
        }
    }
    free(map->buckets);
    free(map);
}

int main() {
    HashMap *map = hashmap_new();

    hashmap_put(map, "alice", 95);
    hashmap_put(map, "bob",   87);
    hashmap_put(map, "carol", 92);

    int score;
    if (hashmap_get(map, "bob", &score)) {
        printf("bob: %dn", score);   /* 87 */
    }

    hashmap_put(map, "bob", 99);  /* update */
    hashmap_get(map, "bob", &score);
    printf("bob updated: %dn", score);   /* 99 */

    hashmap_free(map);
    return 0;
}

Load Factor and Resizing

void hashmap_resize(HashMap *map) {
    size_t  new_cap     = map->capacity * 2;
    Entry **new_buckets = calloc(new_cap, sizeof(Entry*));

    /* Rehash all existing entries */
    for (size_t i = 0; i < map->capacity; i++) {
        Entry *e = map->buckets[i];
        while (e) {
            Entry *next  = e->next;
            size_t new_i = hash_key(e->key, new_cap);
            e->next      = new_buckets[new_i];
            new_buckets[new_i] = e;
            e = next;
        }
    }
    free(map->buckets);
    map->buckets  = new_buckets;
    map->capacity = new_cap;
}

/* Call this in hashmap_put after incrementing count: */
void maybe_resize(HashMap *map) {
    if ((double)map->count / map->capacity > LOAD_FACTOR) {
        hashmap_resize(map);
    }
}

When the load factor (count/capacity) exceeds ~0.75, chains get long and performance degrades to O(n). Resize by doubling the array and rehashing every key. This amortizes to O(1) per insertion over all insertions, just like dynamic arrays.

Open Addressing — The Alternative

Separate chaining uses linked lists for collision chains. Open addressing stores all entries in the array itself — on collision, probe to the next available slot (linear probing, quadratic probing, or double hashing). Open addressing has better cache performance but harder deletion. For a first implementation, separate chaining is simpler and more robust.

The malloc and calloc patterns matter here — use calloc for the bucket array (zero-initializes all pointers to NULL) and malloc for entries. Test the implementation in our c compiler online with a small capacity to force collisions and verify chaining works.

TL;DR

  • A hash table hashes keys to array indices; collisions are handled by chaining or open addressing
  • Use FNV-1a or similar proven hash functions — don’t write your own from scratch
  • Separate chaining: each bucket is a linked list; simple and robust
  • Resize when load factor exceeds 0.75 — double capacity and rehash all entries
  • Always store a copy of the key (strdup), not a pointer to the caller’s string
  • Free the key copy AND the entry node AND the bucket array when cleaning up
  • Open addressing has better cache locality; chaining is easier to implement correctly