The Hash Table Core
Time to build the hash table. It's the engine room of the whole store.
The Hash Function
We'll use DJB2 — a wonderfully short string hash that punches well above its weight:
static unsigned long hash(const char *str) { unsigned long h = 5381; int c; while ((c = *str++)) { h = ((h << 5) + h) + c; // h * 33 + c } return h;}
static int bucket_index(const char *key) { return hash(key) % TABLE_SIZE;}Creating and Destroying
HashTable *ht_create(void) { HashTable *ht = calloc(1, sizeof(HashTable)); // calloc zeros all memory, so all buckets start as NULL return ht;}
void ht_destroy(HashTable *ht) { for (int i = 0; i < TABLE_SIZE; i++) { Entry *entry = ht->buckets[i]; while (entry) { Entry *next = entry->next; free(entry->key); free(entry->value); free(entry); entry = next; } } free(ht);}ht_destroy must walk every chain in every bucket and free each entry's key, value, and the entry itself. Missing any of these causes a memory leak. This is why ownership rules matter - you need to know exactly what to free.
SET Operation
int ht_set(HashTable *ht, const char *key, const char *value) { int idx = bucket_index(key);
// Check if key already exists Entry *entry = ht->buckets[idx]; while (entry) { if (strcmp(entry->key, key) == 0) { // Update existing value: copy first, so a failed strdup // leaves the old value intact char *copy = strdup(value); if (!copy) return -1; free(entry->value); entry->value = copy; return 0; } entry = entry->next; }
// Create new entry Entry *new_entry = malloc(sizeof(Entry)); if (!new_entry) return -1; new_entry->key = strdup(key); new_entry->value = strdup(value); if (!new_entry->key || !new_entry->value) { free(new_entry->key); // free(NULL) is a no-op free(new_entry->value); free(new_entry); return -1; } new_entry->next = ht->buckets[idx]; ht->buckets[idx] = new_entry; ht->count++; return 0;}Spot the prepend trick. New entries land at the head of the chain, which keeps insertion at O(1). Walking to the tail would be wasted work.
GET Operation
char *ht_get(HashTable *ht, const char *key) { int idx = bucket_index(key); Entry *entry = ht->buckets[idx]; while (entry) { if (strcmp(entry->key, key) == 0) { return entry->value; } entry = entry->next; } return NULL;}DELETE Operation
Deletion in a singly-linked list means dragging the previous node along with you:
int ht_delete(HashTable *ht, const char *key) { int idx = bucket_index(key); Entry *entry = ht->buckets[idx]; Entry *prev = NULL;
while (entry) { if (strcmp(entry->key, key) == 0) { if (prev) { prev->next = entry->next; } else { ht->buckets[idx] = entry->next; } free(entry->key); free(entry->value); free(entry); ht->count--; return 0; } prev = entry; entry = entry->next; } return -1; // key not found}Testing
Always exercise the data structure before piling more layers on top:
int main() { HashTable *ht = ht_create(); ht_set(ht, "name", "Alice"); ht_set(ht, "age", "30"); printf("%s\n", ht_get(ht, "name")); // Alice printf("%s\n", ht_get(ht, "age")); // 30 ht_delete(ht, "name"); printf("%s\n", ht_get(ht, "name") ? ht_get(ht, "name") : "(nil)"); // (nil) ht_destroy(ht); return 0;}Here's everything from this lesson stitched together with the structs from the design lesson, so you can run the test as it stands.