Final Project: tiny key-value store

Challenge

Build a string-keyed, int-valued key-value store using a chained hash table.

Task

Implement the following API using a hash table with separate chaining (a linked list of entries per bucket).

typedef struct kv kv_t;
kv_t *kv_create(int n_buckets);
void  kv_set(kv_t *kv, const char *key, int value);
int   kv_get(kv_t *kv, const char *key, int *out_value);  /* 1=found, 0=missing */
int   kv_del(kv_t *kv, const char *key);                  /* 1=removed, 0=missing */
void  kv_destroy(kv_t *kv);

Input

• n_buckets: the number of hash buckets (> 0).
• key: a lowercase ASCII string, up to 64 bytes (the store keeps its own copy).
• value: the int to associate with the key.
• out_value: where kv_get writes the found value.
• Up to 10000 operations.

Output

• kv_set: nothing; inserts a new key or updates an existing one (no duplicates).
• kv_get: 1 and writes the value through out_value if found; 0 if missing.
• kv_del: 1 if a key was removed, 0 if it was not present.

Example

kv_create(4)
kv_set("foo", 42); kv_set("bar", 100)
kv_get("foo", &v)   ->   1, v == 42
kv_set("foo", 999)               (update, not a duplicate)
kv_get("foo", &v)   ->   1, v == 999
kv_del("bar")       ->   1
kv_get("bar", &v)   ->   0
kv_del("none")      ->   0

Edge cases

• Setting an existing key updates its value in place (no duplicate entry).
• Deleting or getting a missing key returns 0.

Rules

• Hash keys with FNV-1a or djb2 and resolve collisions with per-bucket linked-list chains. Free every strdup'd key on delete and destroy.

Why this matters

A key-value store is the universal data structure. Redis is a key-value store. Memcached is a key-value store. Browser localStorage is a key-value store. Building one from scratch reveals what hash maps actually buy you.

Input format

n_buckets > 0; lowercase ASCII keys up to 64 bytes; int values; up to 10000 ops.

Output format

See the API: get/del return 1/0; get writes through out_value.

Constraints

Use FNV-1a or djb2 for hashing. Use linked-list chains per bucket.

Starter code

typedef struct kv kv_t;
kv_t *kv_create(int n_buckets);
void  kv_set(kv_t *kv, const char *key, int value);
int   kv_get(kv_t *kv, const char *key, int *out_value);
int   kv_del(kv_t *kv, const char *key);
void  kv_destroy(kv_t *kv);

Common mistakes

Forgetting to update size on delete; comparing pointers instead of strcmp; not freeing key strdups on destroy.

Edge cases to handle

Set then set on same key (update, no duplicate). Delete of missing key. Get of missing key.

Complexity

Average O(1); worst-case O(n) with adversarial hash.

Background lessons

• Hashing — turning keys into table indices
• Linked lists