Hash Table — Open Addressing (C)
Topics: hash table, open addressing, linear probing, tombstones
Problem
Implement a fixed-capacity hash map of int -> int using open addressing
(all entries live in one flat slot array — no buckets, no allocation). The caller
owns the Slot storage[cap] array and zero-initializes it, so state 0 means an
empty slot.
enum { SLOT_EMPTY = 0, SLOT_USED = 1, SLOT_TOMB = 2 };
typedef struct { int key, val; int state; } Slot;
typedef struct { Slot *slots; size_t cap; size_t count; } HashMap;
void hm_init(HashMap *m, Slot *storage, size_t cap);
bool hm_get(HashMap *m, int key, int *out); // true + *out if present
bool hm_put(HashMap *m, int key, int val); // insert/update; false if full
bool hm_del(HashMap *m, int key); // true if removed
size_t hm_len(const HashMap *m); // live entries
- Probe with linear probing: compute a home slot
hash(key) % cap, then walk
forward (wrapping) until you find the key, an empty slot, or you've scanned the
whole table.
hm_get / hm_del: stop at the first EMPTY slot — that ends the chain, so
the key is absent.hm_del leaves a tombstone: mark the slot SLOT_TOMB, not SLOT_EMPTY.
Clearing it to empty would cut the probe chain and hide later keys.hm_put: update in place if the key exists; otherwise insert at the first
tombstone or empty slot in the probe sequence. Return false if the table is
full of live entries.
Key concepts
- Why tombstones: with linear probing, a key sits somewhere in the contiguous
run after its home slot. Deleting by emptying a middle slot would make a probe
for a later key stop early and report it missing. A tombstone keeps the chain
walkable while freeing the slot for reuse.
- Reusing slots: an insert should prefer the first tombstone it passed, but
must keep scanning to confirm the key isn't already present further along.
- Fixed capacity: no resize — once every slot is live, a new key is rejected.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/hashmap && /tmp/hashmap
Sign in to submit your solution.