11、哈希表与键值存储：键值对概念、哈希表作为底层存储、简单内存数据库实现

好，咱们今天聊点实在的。哈希表这东西，说白了就是一张超级查找表。你给它一个钥匙（Key），它立马就能告诉你对应的东西（Value）放在哪。我当年刚学数据结构时，觉得数组和链表就够用了，直到第一次写缓存系统，才真正体会到哈希表有多香。

11.1 键值对：最朴素的数据组织方式

什么是键值对？你想想看，现实生活里到处都是。你的身份证号对应一个人，手机通讯录里名字对应电话号码，字典里单词对应释义。这就是键值对——一个唯一的标识（Key）绑定一个数据（Value）。

在C语言里，键值对通常用一个结构体来表示：

typedef struct {
    char *key;      // 键，通常是字符串或整数
    void *value;    // 值，可以是任意类型
    size_t value_size; // 值的字节长度，方便拷贝
} KeyValuePair;

我个人习惯把Key设计成字符串，因为字符串的可读性最好。你在命令行里敲set name "张三"，这个"name"就是Key，"张三"就是Value。简单直观。

11.2 哈希表作为底层存储

哈希表的核心思想其实就一句话：通过哈希函数，把Key映射到数组的某个位置。

你看，数组的查找是O(1)的，但数组下标必须是整数。哈希函数就是干这个的——把任意类型的Key（字符串、结构体指针等）转成一个整数下标。这样我们就能用数组的随机访问能力，实现O(1)平均时间复杂度的查找。

11.2.1 哈希函数

哈希函数的质量直接决定哈希表的性能。一个糟糕的哈希函数会让所有Key扎堆到同一个桶里，哈希表退化成链表，查找变成O(n)。

我常用的一个字符串哈希函数是BKDRHash，简单且分布均匀：

unsigned long BKDRHash(const char *str) {
    unsigned long hash = 0;
    int c;
    while ((c = *str++)) {
        hash = hash * 131 + c;  // 131是经验值，也可以用31、33等
    }
    return hash;
}

为什么乘131？嗯，这是个经验值。不同的乘数会影响哈希值的分布，131是我试过效果比较好的一个。你也可以用31、33或者5381，各有各的道理。

11.2.2 哈希冲突处理

哈希函数再牛，也避免不了冲突——两个不同的Key算出了同一个下标。怎么办？业界主流有两种方案：

• 链地址法：每个桶里挂一个链表，冲突的Key都链在后面。实现简单，但链表太长会影响性能。
• 开放地址法：冲突了就往后找空位。节省内存，但删除操作比较麻烦。

我个人更偏爱链地址法。为什么？因为实现起来直来直去，不容易出bug。我曾经在一个嵌入式项目里用过开放地址法，结果删除操作引入了一个隐蔽的bug，排查了两天才找到。从那以后，除非内存极度受限，否则我都用链地址法。

11.2.3 负载因子与扩容

哈希表里有个重要概念叫负载因子：

负载因子 = 已存储的键值对数量 / 桶的总数

负载因子越大，冲突概率越高，性能越差。一般建议负载因子超过0.75时就进行扩容——把桶数组扩大一倍，重新哈希所有Key。

扩容是个重操作，时间复杂度O(n)。但好在不是每次插入都扩容，均摊下来还是O(1)。

11.3 简单内存数据库实现

理论说完了，咱们动手写一个迷你内存数据库。说白了，就是基于哈希表的键值存储系统，支持SET、GET、DEL三个基本操作。

11.3.1 数据结构设计

// 哈希表节点
typedef struct HashNode {
    char *key;
    char *value;
    struct HashNode *next;  // 链地址法，指向下一个节点
} HashNode;

// 哈希表主体
typedef struct {
    HashNode **buckets;  // 桶数组，每个元素是一个链表头
    int size;            // 桶的数量
    int count;           // 当前存储的键值对数量
    float load_factor;   // 负载因子阈值
} HashMap;

11.3.2 核心操作实现

SET操作：

void hashmap_set(HashMap *map, const char *key, const char *value) {
    unsigned long index = BKDRHash(key) % map->size;
    HashNode *node = map->buckets[index];
    
    // 先查找是否已存在
    while (node) {
        if (strcmp(node->key, key) == 0) {
            // 更新已有值
            free(node->value);
            node->value = strdup(value);
            return;
        }
        node = node->next;
    }
    
    // 不存在则插入新节点（头插法）
    HashNode *new_node = (HashNode *)malloc(sizeof(HashNode));
    new_node->key = strdup(key);
    new_node->value = strdup(value);
    new_node->next = map->buckets[index];
    map->buckets[index] = new_node;
    map->count++;
    
    // 检查是否需要扩容
    if ((float)map->count / map->size > map->load_factor) {
        hashmap_resize(map, map->size * 2);
    }
}

GET操作：

char *hashmap_get(HashMap *map, const char *key) {
    unsigned long index = BKDRHash(key) % map->size;
    HashNode *node = map->buckets[index];
    
    while (node) {
        if (strcmp(node->key, key) == 0) {
            return node->value;  // 找到了，返回值
        }
        node = node->next;
    }
    return NULL;  // 没找到
}

DEL操作：

int hashmap_del(HashMap *map, const char *key) {
    unsigned long index = BKDRHash(key) % map->size;
    HashNode *node = map->buckets[index];
    HashNode *prev = NULL;
    
    while (node) {
        if (strcmp(node->key, key) == 0) {
            if (prev) {
                prev->next = node->next;
            } else {
                map->buckets[index] = node->next;
            }
            free(node->key);
            free(node->value);
            free(node);
            map->count--;
            return 1;  // 删除成功
        }
        prev = node;
        node = node->next;
    }
    return 0;  // 键不存在
}

11.3.3 完整的内存数据库

有了哈希表，封装一个简单的内存数据库就水到渠成了：

typedef struct {
    HashMap *store;
} SimpleDB;

void db_set(SimpleDB *db, const char *key, const char *value) {
    hashmap_set(db->store, key, value);
}

char *db_get(SimpleDB *db, const char *key) {
    return hashmap_get(db->store, key);
}

int db_del(SimpleDB *db, const char *key) {
    return hashmap_del(db->store, key);
}

你看，核心逻辑就这么几行。真正的Redis、Memcached等内存数据库，底层原理和这个一模一样，只不过在持久化、集群、并发控制等方面做了大量增强。

11.4 哈希表核心知识体系

下面这张图总结了哈希表作为键值存储底层的完整逻辑：

从这张图可以看得很清楚：键值对是上层抽象，哈希表是底层实现，哈希函数和冲突处理是核心机制，负载因子和扩容是性能保障，最终封装成内存数据库对外提供服务。

好了，这一章的内容就到这里。哈希表作为底层存储，原理其实不复杂，但实现细节里坑不少。我建议你亲手把上面的代码敲一遍，跑几个测试用例，感受一下哈希表的工作过程。遇到问题不要慌，调试器里走一遍，什么都明白了。

---