Hash Tables
A hash table gives you average O(1) lookup, insertion, and deletion — the workhorse data structure of nearly every program you'll ever write. Implementing one in C is a three-for-one deal: hashing, collision handling, and heap juggling, all in the same exercise.
How Hash Tables Work
- Hash the key. The hash, modulo your bucket count, becomes an index.
- Store the key-value pair in that bucket.
- Handle collisions for the inevitable case where two different keys map to the same slot.
A Simple Hash Function
DJB2 is the Daniel J. Bernstein hash that everyone reaches for when they want something quick and decent on strings:
unsigned long hash(const char *str) { const unsigned char *s = (const unsigned char *)str; unsigned long h = 5381; int c; while ((c = *s++)) { h = ((h << 5) + h) + c; // h * 33 + c } return h;}Reading through unsigned char matters. Plain char is signed on x86 and unsigned on most Arm targets, so a key with bytes above 127 (any accented or non-Latin text in UTF-8) would hash to a different bucket on each without it.
Separate Chaining
Easiest collision strategy ever invented: each bucket holds a linked list, and colliding entries just join the chain.
#define TABLE_SIZE 256
typedef struct Entry { char *key; char *value; struct Entry *next;} Entry;
typedef struct { Entry *buckets[TABLE_SIZE];} HashTable;Before writing the insert code, watch chaining happen. The explorer below uses DJB2 with only 8 buckets so collisions come quickly. Type a handful of keys (try apple, banana, cherry, date, elder, fig) and watch which chains grow. Then switch to the sum-of-characters hash and add listen and silent: anagrams have the same byte sum, so they always collide.
Hash Table Explorer
The explorer does its arithmetic in 32 bits and the C version above in 64, but with a power-of-two bucket count only the low bits of the hash pick the bucket, and those agree. With a bucket count that isn't a power of two, such as 7, they can drift apart.
Inserting a Value
int ht_set(HashTable *ht, const char *key, const char *value) { unsigned long idx = hash(key) % TABLE_SIZE; char *v = strdup(value); // allocate first: if it fails, nothing has changed if (v == NULL) return -1;
// Check if key already exists Entry *e = ht->buckets[idx]; while (e) { if (strcmp(e->key, key) == 0) { free(e->value); e->value = v; return 0; } e = e->next; }
// Create new entry Entry *new_entry = malloc(sizeof(Entry)); char *k = strdup(key); if (new_entry == NULL || k == NULL) { free(new_entry); // free(NULL) is a no-op, so this is safe free(k); free(v); return -1; } new_entry->key = k; new_entry->value = v; new_entry->next = ht->buckets[idx]; ht->buckets[idx] = new_entry; return 0;}strdup mallocs a fresh buffer and copies the string in. Each call therefore plants a new heap allocation that someone has to free later. Building any nontrivial C data structure means keeping a mental ledger of every malloc and strdup, then matching each one with a free when entries die or the whole table is torn down.
Looking Up a Value
char* ht_get(HashTable *ht, const char *key) { unsigned long idx = hash(key) % TABLE_SIZE; Entry *e = ht->buckets[idx]; while (e) { if (strcmp(e->key, key) == 0) return e->value; e = e->next; } return NULL;}Try It
Open the editor and implement DJB2 yourself, then check the output against a known reference value.
Once that works, there's a gap in the code above: nothing ever deletes an entry or frees the table. The runner below fills those in, then loads 1,000 keys and reports how long the worst chain got. Run it, then replace hash with a lazy one that just adds up the bytes and see what happens to the longest chain.
The runner keeps error handling short: on an allocation failure it just exits, which is fine for a demo but not for a library, where ht_set should report the failure the way the version above does.
Challenges
Implement a singly linked list with push_front, print, and free functions.