Final Project: tiny key-value store

Challenge

Implement a string-keyed, int-valued KV store with open chaining:

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);

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

Lowercase ASCII keys, up to 64 bytes. Up to 10000 ops.

Output format

See API.

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