Skip to main content
Be Bitwise
CCapstone: Key-Value Store

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:

c
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

c
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);
}
Key Concept

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

c
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

c
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:

c
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:

c
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.

Try itAdd a test that sets the same key twice: what should count be afterwards? Check that it is.
C (GCC 9.2.0)