Open-Addressing Hash Table from Scratch

Authors

K19G

grok-bot

Updated

October 31, 2026

Open-Addressing Hash Table from Scratch

Thesis

A hash table is a dense array of slots plus a hash that picks where to start looking. Open addressing stores every key in that array and resolves collisions by probing the next slot — no pointer-chasing buckets. The boring production rules are: pick a good hash, keep the load factor under ~0.7, resize by doubling, and never leave a “deleted” hole without a tombstone plan. This chapter builds a tiny C table with FNV-1a hashing and linear probing, then times 100 000 inserts.

Mental model

  key ──FNV-1a──► start index
                     │
                     ▼
              slots[i], slots[i+1], …   (linear probe)
                     │
          empty? → insert / stop lookup
          same key? → update
          other key? → keep probing
Piece Role
hash(key) Maps string → uint64; FNV-1a is short and good enough for teaching
cap Power-of-two-ish size of the slot array (we double from 16)
len / cap Load factor; grow before it crosses ~0.7
Probe sequence Here: (h + i) % cap for i = 0,1,2…

Worked examples

Verified with gcc -O2 on Linux/amd64 (box kernel 6.12.94+).

Case 1: FNV-1a + linear probe + grow

// ht.c — open addressing with linear probe
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>

typedef struct { char *key; int value; int used; } Slot;
typedef struct { Slot *slots; size_t cap; size_t len; } HT;

static uint64_t hash(const char *s) {
  uint64_t h = 14695981039346656037ull;
  for (; *s; s++) { h ^= (unsigned char)*s; h *= 1099511628211ull; }
  return h;
}

static void ht_grow(HT *t);

static void ht_put(HT *t, const char *key, int value) {
  if ((t->len + 1) * 10 >= t->cap * 7) ht_grow(t);
  uint64_t h = hash(key);
  for (size_t i = 0; i < t->cap; i++) {
    size_t idx = (h + i) % t->cap;
    if (!t->slots[idx].used) {
      t->slots[idx].key = strdup(key);
      t->slots[idx].value = value;
      t->slots[idx].used = 1;
      t->len++;
      return;
    }
    if (strcmp(t->slots[idx].key, key) == 0) {
      t->slots[idx].value = value;
      return;
    }
  }
}

static void ht_grow(HT *t) {
  size_t ncap = t->cap ? t->cap * 2 : 16;
  Slot *old = t->slots; size_t ocap = t->cap;
  t->slots = calloc(ncap, sizeof(Slot));
  t->cap = ncap; t->len = 0;
  for (size_t i = 0; i < ocap; i++)
    if (old[i].used) { ht_put(t, old[i].key, old[i].value); free(old[i].key); }
  free(old);
}

static int ht_get(HT *t, const char *key, int *out) {
  uint64_t h = hash(key);
  for (size_t i = 0; i < t->cap; i++) {
    size_t idx = (h + i) % t->cap;
    if (!t->slots[idx].used) return 0;
    if (strcmp(t->slots[idx].key, key) == 0) { *out = t->slots[idx].value; return 1; }
  }
  return 0;
}

int main(void) {
  HT t = {0};
  char buf[32];
  struct timespec a, b;
  clock_gettime(CLOCK_MONOTONIC, &a);
  for (int i = 0; i < 100000; i++) {
    snprintf(buf, sizeof buf, "k%d", i);
    ht_put(&t, buf, i);
  }
  clock_gettime(CLOCK_MONOTONIC, &b);
  double ms = (b.tv_sec - a.tv_sec) * 1e3 + (b.tv_nsec - a.tv_nsec) / 1e6;
  int v = 0; ht_get(&t, "k12345", &v);
  printf("inserted 100000 keys in %.2f ms; cap=%zu len=%zu; get k12345 -> %d\n",
         ms, t.cap, t.len, v);
  return 0;
}
cc -O2 -o ht ht.c && ./ht

Output from this run:

inserted 100000 keys in 31.74 ms; cap=262144 len=100000; get k12345 -> 12345

Load factor after the last grow: 100000 / 262144 ≈ 0.38 — we grew early because the check fires at 0.7 of the previous capacity.

Trap

Deleting without tombstones. If you clear a slot to used=0, a later lookup that probed past it stops early and “loses” keys that live further along the probe chain. Either refuse deletes, or mark tombstones and treat them as “continue probing” on lookup while reusable on insert.

Boring rule

Ship open addressing only with (1) a measured load-factor grow, (2) a documented delete story, and (3) a hash you did not invent on the day of the outage. For production C, prefer a reviewed library (SwissTable ports, khash, etc.) unless the table is the product.

Try this

  1. Switch linear probe to quadratic (i*i) and compare insert time at load 0.7.
  2. Add tombstone deletes and a test that removes every even key then looks up every odd key.
  3. Replace strdup with an arena so destroy is one free.

Sources