By now, you've handled structs and pointers, but putting them together into a useful data structure is where things get interesting. A key-value store is essentially a dictionary: you give it a string (the key), and it gives you back a piece of data (the value). In C, we don't have a built-in std::map or dict, so we have to build one from scratch using a hash table.

How do I actually turn a string key into an array index?

You can't just use the string itself as an index; you need a hash function. A hash function takes a string of any length and crushes it down into a large unsigned integer. Then, you use the modulo operator (%) to fit that integer into the size of your array.

I usually recommend the djb2 algorithm for simple projects. It's incredibly short but surprisingly effective at distributing keys evenly, which prevents your store from slowing down.

unsigned long hash_function(char *str) {
    unsigned long hash = 5381;
    int c;

    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }
    return hash;
}

// Usage:
// int index = hash_function("user_123") % TABLE_SIZE;

What happens when two different keys end up at the same index?

This is called a collision, and it's guaranteed to happen eventually. If you just overwrite the previous value, you've built a broken store. The most straightforward fix is "separate chaining." Instead of storing the value directly in the array, each array slot points to a linked list of entries.

If two keys hash to the same index, you just append the new one to the list. When you go to retrieve a value, you jump to the index and then traverse the list, comparing the actual strings until you find the match.

typedef struct Entry {
    char *key;
    char *value;
    struct Entry *next;
} Entry;

Entry *table[TABLE_SIZE];

void kv_put(char *key, char *value) {
    unsigned long index = hash_function(key) % TABLE_SIZE;
    
    // First, check if the key already exists to update it
    Entry *curr = table[index];
    while (curr) {
        if (strcmp(curr->key, key) == 0) {
            free(curr->value);
            curr->value = strdup(value);
            return;
        }
        curr = curr->next;
    }

    // Otherwise, create a new entry at the head of the list
    Entry *new_entry = malloc(sizeof(Entry));
    new_entry->key = strdup(key);
    new_entry->value = strdup(value);
    new_entry->next = table[index];
    table[index] = new_entry;
}

How do I retrieve a value without scanning the entire table?

The beauty of the hash table is that you only ever scan the small linked list at one specific index. You don't touch the other thousands of slots. I've seen beginners try to loop through the entire table array to find a key—don't do that. That defeats the whole purpose of hashing.

You hash the key, go straight to the bucket, and walk the chain. If you hit NULL, the key doesn't exist.

char* kv_get(char *key) {
    unsigned long index = hash_function(key) % TABLE_SIZE;
    Entry *curr = table[index];

    while (curr) {
        if (strcmp(curr->key, key) == 0) {
            return curr->value;
        }
        curr = curr->next;
    }
    return NULL; // Not found
}

📋 Practical Task

Implementing Key Deletion and Memory Cleanup for the KV Store

Now that you have a working put and get, your store has one major flaw: you can't remove anything, and you'll leak memory when the program exits. Your task is to implement two specific functions to complete the system:

• void kv_delete(char *key): This must find the entry, unhook it from the linked list (carefully patching the next pointers of the previous node), and free the memory for the key, the value, and the entry struct itself.
• void kv_destroy(): This must iterate through every single bucket in the table and free all entries in every linked list to ensure a clean exit.

Test your implementation by adding five keys, deleting two of them, and then running your program through Valgrind to ensure there are zero memory leaks.