哈希表模块：哈希函数的选择、冲突解决与键值对存储实战
哈希表，说白了就是“用空间换时间”的典型代表。你想想看，数组查找是O(1)，链表是O(n)，而哈希表在理想情况下也能做到O(1)。但理想很丰满，现实很骨感——哈希冲突就是那个“骨感”的部分。
我在项目中用过不下十种哈希表实现，从嵌入式RTOS里的轻量级符号表，到网络协议栈中的流表管理。每次踩的坑都不一样，但核心问题就两个：哈希函数怎么选？冲突怎么解决？
哈希函数的选择
哈希函数的目标很简单：把任意长度的输入，映射到一个固定范围的整数上。但“简单”不等于“随便”。
我见过有人直接用取模：key % table_size。这在key是连续整数时还行，但如果key是内存地址（总是4字节对齐），那取模结果的后两位永远是0——哈希表直接废了一半。
常用的哈希函数有几种：
- 直接取模法：
hash = key % N。简单，但要求N是质数，且key分布均匀。 - 乘法哈希：
hash = floor(N * (key * A % 1))，其中A是黄金分割比例0.618...。对整数key效果不错。 - BKDR哈希：对字符串key，用
hash = hash * 131 + c迭代。我在嵌入式项目里常用这个，冲突率低，计算也快。 - MurmurHash / xxHash：现代高性能哈希，适合通用场景。但嵌入式平台如果没硬件乘法器，跑起来有点吃力。
我的经验：在资源受限的MCU上，BKDR哈希配合质数大小的表，基本够用。别一上来就上MurmurHash，那玩意儿在Cortex-M0上跑一次够你干别的好多事了。
冲突解决：链地址法 vs 开放地址法
哈希冲突不可避免。两个不同的key算出了同一个桶号，怎么办？
链地址法
每个桶里挂一个链表。冲突了，就往链表后面加。这是最直观的做法。
typedef struct HashNode {
uint32_t key;
void *value;
struct HashNode *next;
} HashNode;
typedef struct {
HashNode **buckets;
size_t size;
} HashMap;
优点：实现简单，删除方便，负载因子可以大于1。
缺点：链表遍历慢，缓存不友好。
我曾经在一个网络包处理模块里用链地址法，结果哈希表里存了10万条流表项，链表越挂越长，查找越来越慢。后来改成开放地址法，性能直接翻倍。
开放地址法
冲突了，不挂链表，而是往后找空位。常见的有线性探测、二次探测、双重哈希。
// 线性探测
size_t index = hash(key) % table_size;
while (table[index].occupied) {
if (table[index].key == key) {
// 更新值
break;
}
index = (index + 1) % table_size; // 往后找
}
优点：内存紧凑，缓存命中率高。
缺点：删除麻烦（不能直接清空，得用“已删除”标记），负载因子不能太高（超过0.7性能急剧下降）。
注意：开放地址法的删除操作是个坑。我曾经在调试一个内存数据库时，因为删除时直接置空，导致后续查找提前终止——明明key在表里，却查不到。后来改用“墓碑标记”才解决。
实战：实现一个键值对存储模块
下面我带你手写一个轻量级的键值对存储模块。这个模块我在一个传感器数据采集项目里用过，跑在STM32上，内存只有64KB。
接口设计
// kv_store.h
#ifndef KV_STORE_H
#define KV_STORE_H
#include <stdint.h>
#include <stdbool.h>
typedef struct {
uint32_t key;
int32_t value;
bool occupied;
bool deleted; // 墓碑标记
} KVEntry;
typedef struct {
KVEntry *entries;
size_t capacity;
size_t count;
} KVStore;
// 初始化
void kv_init(KVStore *store, KVEntry *buffer, size_t capacity);
// 插入/更新
bool kv_put(KVStore *store, uint32_t key, int32_t value);
// 查找
bool kv_get(KVStore *store, uint32_t key, int32_t *value);
// 删除
bool kv_delete(KVStore *store, uint32_t key);
// 清空
void kv_clear(KVStore *store);
#endif
哈希函数
我用的是改进版的取模法——先对key做一次位运算打散，再取模。
static size_t hash(uint32_t key, size_t capacity) {
// 用质数做乘法，打散低位
key = key * 2654435761U; // 黄金分割比例相关
return key % capacity;
}
核心实现
bool kv_put(KVStore *store, uint32_t key, int32_t value) {
if (store->count >= store->capacity * 0.7) {
return false; // 负载因子超限，需要扩容（这里简化处理）
}
size_t idx = hash(key, store->capacity);
size_t start = idx;
do {
if (!store->entries[idx].occupied || store->entries[idx].deleted) {
// 找到空位或已删除位置
store->entries[idx].key = key;
store->entries[idx].value = value;
store->entries[idx].occupied = true;
store->entries[idx].deleted = false;
store->count++;
return true;
}
if (store->entries[idx].key == key) {
// 更新已有key
store->entries[idx].value = value;
return true;
}
idx = (idx + 1) % store->capacity;
} while (idx != start);
return false; // 表满了
}
小技巧：查找和插入用同一个探测路径。这样插入时如果发现key已存在，直接更新；查找时如果遇到空位，说明key不存在。逻辑统一，不容易出错。
哈希表核心逻辑图
下面这张图展示了从key到存储位置的完整流程：
避坑指南
我这些年踩过的坑，总结成几条：
- 表大小一定要是质数。我曾经图省事用了2的幂次大小，结果哈希函数取模后分布极不均匀——因为key的低位有规律。
- 删除操作别偷懒。开放地址法下，直接置空会导致查找链断裂。用墓碑标记虽然麻烦点，但正确性有保障。
- 负载因子要设上限。链地址法可以到1.0以上，但开放地址法超过0.7性能就崩了。我一般设0.7为扩容阈值。
- 哈希函数要快。嵌入式平台上，一个复杂的哈希函数可能比查找本身还慢。BKDR或简单乘法取模就够用。
我的习惯：在项目初期，先用链地址法快速实现功能。等性能瓶颈出现时，再针对性优化成开放地址法。别一开始就追求“最优”，迭代开发才是正道。
总结
哈希表模块的核心就三件事：选好哈希函数、定好冲突策略、管好负载因子。代码量不大，但细节不少。你把这个模块封装好了，以后任何需要键值对存储的场景——配置管理、缓存、符号表——都能直接复用。
嗯，哈希表这块就聊到这儿。记住：简单、正确、可复用，比花哨的优化更重要。