哈希表 - 链地址法 (Separate Chaining)
通过数组加链表解决哈希冲突。每个桶（bucket）维护一条链表，冲突元素追加到链表末尾。
结构定义
typedef struct HNode {
char *key;
int value;
struct HNode *next;
} HNode;
typedef struct {
HNode **buckets; /* 桶数组，每个元素为链表头指针 */
size_t capacity; /* 桶数量 */
size_t size; /* 当前 key 数量 */
} HashMap;函数签名
| 函数 | 复杂度 | 说明 |
|---|---|---|
void hm_init(HashMap *h, size_t cap) | O(cap) | 初始化 |
void hm_put(HashMap *h, const char *key, int val) | 均摊 O(1) | 插入/更新键值 |
int hm_get(HashMap *h, const char *key, int *out) | 均摊 O(1) | 查找，返回 0/1 表示是否存在 |
int hm_remove(HashMap *h, const char *key) | 均摊 O(1) | 删除，返回 0/1 |
void hm_rehash(HashMap *h) | O(n) | 扩容重整，负载因子超阈值时触发 |
void hm_free(HashMap *h) | O(cap + n) | 释放内存 |
哈希函数
/* DJB2 哈希 — 简单高效 */
unsigned long hash_djb2(const char *str) {
unsigned long hash = 5381;
int c;
while ((c = *str++))
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}取模映射桶索引：index = hash(key) % capacity。
扩容重整
当 size / capacity >= LOAD_FACTOR（通常 0.75），将 buckets 容量翻倍并重新分配所有节点：
/* 简单扩容：新建数组，遍历旧链表，头插到新桶 */
void hm_rehash(HashMap *h) {
size_t new_cap = h->capacity * 2;
HNode **new_buckets = calloc(new_cap, sizeof(HNode *));
for (size_t i = 0; i < h->capacity; i++) {
HNode *node = h->buckets[i];
while (node) {
HNode *next = node->next;
size_t idx = hash_djb2(node->key) % new_cap;
node->next = new_buckets[idx]; /* 头插 */
new_buckets[idx] = node;
node = next;
}
}
free(h->buckets);
h->buckets = new_buckets;
h->capacity = new_cap;
}