在现代系统设计中，键值存储（Key-Value Store）因其结构简单、访问高效而广泛应用，尤其适合缓存和配置管理等场景。本文将探讨如何使用两种基础数据结构——顺序数组与哈希表，构建一个轻量级的KV存储引擎。

基于数组的存储实现

最直观的实现方式是使用动态数组来维护键值对集合。定义一个结构体用于表示单个键值项，并通过一个容器结构管理所有项：

typedef struct kvs_item {
    char *key;
    char *value;
} kvs_item_t;

typedef struct kvs_array {
    kvs_item_t *items;
    int count;
    int capacity;
} kvs_array_t;

// 全局实例
kvs_array_t g_store = {0};

初始化时分配固定大小的内存空间，确保后续操作安全：

int kvs_array_init(kvs_array_t *arr) {
    if (!arr) return -1;
    arr->items = (kvs_item_t*)calloc(KVS_ARRAY_SIZE, sizeof(kvs_item_t));
    if (!arr->items) return -1;
    arr->count = 0;
    arr->capacity = KVS_ARRAY_SIZE;
    return 0;
}

void kvs_array_free(kvs_array_t *arr) {
    if (!arr || !arr->items) return;
    for (int i = 0; i < arr->count; ++i) {
        free(arr->items[i].key);
        free(arr->items[i].value);
    }
    free(arr->items);
    arr->items = NULL;
}

查找操作通过遍历数组完成，比较键名是否匹配：

char* kvs_array_find(const kvs_array_t *arr, const char *key) {
    if (!arr || !key) return NULL;
    for (int i = 0; i < arr->count; ++i) {
        if (arr->items[i].key && strcmp(arr->items[i].key, key) == 0) {
            return arr->items[i].value;
        }
    }
    return NULL;
}

插入逻辑会先检查键是否存在，若不存在则复制键值并插入到第一个空位或末尾：

int kvs_array_insert(kvs_array_t *arr, const char *key, const char *value) {
    if (!arr || !key || !value || arr->count >= arr->capacity) return -1;

    // 检查重复
    if (kvs_array_find(arr, key)) return 1;

    // 分配新节点
    char *k = strdup(key);
    char *v = strdup(value);
    if (!k || !v) { free(k); free(v); return -2; }

    // 寻找空位
    for (int i = 0; i < arr->capacity; ++i) {
        if (!arr->items[i].key) {
            arr->items[i].key = k;
            arr->items[i].value = v;
            arr->count++;
            return 0;
        }
    }

    // 若无空位，追加至末尾（超出容量处理）
    return -1;
}

更新和删除操作也遵循类似流程：定位目标项后修改或释放其资源。

基于哈希表的高性能实现

为了提升查询效率，可采用哈希表结构。核心思想是利用哈希函数将键映射到索引位置，冲突时使用链表解决。

// 哈希节点
typedef struct hash_node {
    char *key;
    char *value;
    struct hash_node *next;
} hash_node_t;

// 哈希表
typedef struct kvs_hash {
    hash_node_t **buckets;
    int size;
    int count;
} kvs_hash_t;

哈希函数采用字符累加取模的方式：

static int hash_func(const char *key, int table_size) {
    if (!key) return -1;
    int sum = 0;
    while (*key) sum += *key++;
    return sum % table_size;
}

插入操作将新节点添加至对应桶的头部，避免遍历整个链表：

int kvs_hash_put(kvs_hash_t *hash, const char *key, const char *value) {
    if (!hash || !key || !value) return -1;

    int idx = hash_func(key, hash->size);
    hash_node_t *curr = hash->buckets[idx];

    // 检查是否已存在
    while (curr) {
        if (strcmp(curr->key, key) == 0) return 1; // 已存在
        curr = curr->next;
    }

    // 创建新节点
    hash_node_t *node = (hash_node_t*)calloc(1, sizeof(hash_node_t));
    if (!node) return -2;

    node->key = strdup(key);
    node->value = strdup(value);
    node->next = hash->buckets[idx];
    hash->buckets[idx] = node;
    hash->count++;

    return 0;
}

查询同样通过哈希定位，再遍历链表比对键名：

char* kvs_hash_get(const kvs_hash_t *hash, const char *key) {
    if (!hash || !key) return NULL;

    int idx = hash_func(key, hash->size);
    hash_node_t *node = hash->buckets[idx];

    while (node) {
        if (strcmp(node->key, key) == 0) return node->value;
        node = node->next;
    }

    return NULL;
}

更新与删除操作需遍历链表找到目标节点，并进行相应处理。

以上两种实现分别代表了不同性能与复杂度的权衡：数组实现简单但查找为O(n)，哈希表平均可达O(1)时间复杂度，适用于高并发读写场景。