C 語言實現輕量級 HashMap：鏈地址法、通用鍵值與記憶體管理最佳實踐

編輯：關於C語言

C 標準庫缺乏關聯容器，手寫一個輕量、無依賴的 HashMap 是系統級開發常見需求。本文呈現一個生產就緒的實現：鏈地址法解決衝突、鍵為字串、值為任意指針、自定義值釋放回調，適合嵌入式、內核模組、高性能服務端場景。

設計決策

層面	選擇	理由
哈希函數	簡易多項式滾動哈希 `h = 17*h + c`	無依賴、分布均勻、字串專用
衝突解決	鏈地址法（單向鏈表）	實現簡單、動態擴容無需遷移、刪除 O(1)
鍵類型	C 字串 `const char*`，內部複製存儲	通用、生命周期可控
值類型	`void*`，調用者分配/釋放	零拷貝、支援任意類型
內存管理	調用者提供 `value_free` 回調	解決值所有權模糊，防洩漏
擴容	固定桶數（1024），無動態擴容	嵌入式友好、確定性延遲、代碼極簡

頭文件：hashmap.h


#ifndef HASHMAP_H
#define HASHMAP_H

#include  // size_t

typedef struct _hash_map_t *hash_map; // 不透明指針，封裝細節

// 值釋放回調原型
typedef void (*hashmap_value_free_fn)(void *value);

// 創建：size 建議 1024 或質數
hash_map hashmap_create(size_t size);

// 銷毀：遍歷所有桶，調用 value_free 釋放值，再釋放鍵/節點/表
void hashmap_destroy(hash_map hm, hashmap_value_free_fn value_free);

// 插入：key 複製存儲，key_len=-1 時自動 strlen
// 允許覆蓋同鍵（視為更新），返回 0 成功，-1 OOM
int hashmap_insert(hash_map hm, const char *key, int key_len, void *value);

// 查找：返回值指針，未找到返回 NULL
void *hashmap_search(hash_map hm, const char *key);

// 刪除（可選擴展）
// int hashmap_remove(hash_map hm, const char *key, hashmap_value_free_fn value_free);

#endif

核心實現：hashmap.c


#include "hashmap.h"
#include 
#include 
#include 

// 內部節點
typedef struct node {
    struct node *next;
    char *key;   // 複製的鍵字串
    void *value; // 用戶值指針
} node_t;

struct _hash_map_t {
    size_t size;      // 桶數組大小
    node_t **buckets; // 桶數組，每桶為鏈表頭
};

// 簡易哈希
static size_t hash_str(const char *s, int len) {
    size_t h = 0;
    if (len < 0) len = s ? strlen(s) : 0;
    for (int i = 0; i < len; ++i) h = 17 * h + (unsigned char)s[i];
    return h;
}

hash_map hashmap_create(size_t size) {
    hash_map hm = malloc(sizeof(*hm));
    if (!hm) return NULL;
    hm->size = size;
    hm->buckets = calloc(size, sizeof(node_t*));
    if (!hm->buckets) { free(hm); return NULL; }
    return hm;
}

void hashmap_destroy(hash_map hm, hashmap_value_free_fn vfree) {
    if (!hm) return;
    for (size_t i = 0; i < hm->size; ++i) {
        node_t *n = hm->buckets[i];
        while (n) {
            node_t *next = n->next;
            free(n->key);
            if (vfree) vfree(n->value);
            free(n);
            n = next;
        }
    }
    free(hm->buckets);
    free(hm);
}

int hashmap_insert(hash_map hm, const char *key, int key_len, void *value) {
    if (!hm || !key) return -1;
    if (key_len < 0) key_len = strlen(key);

    size_t idx = hash_str(key, key_len) % hm->size;
    node_t *n = hm->buckets[idx];

    // 查找是否已存在 → 更新值
    while (n) {
        if (strcmp(n->key, key) == 0) {
            if (hm->value_free) hm->value_free(n->value); // 若有舊值釋放
            n->value = value;
            return 0;
        }
        n = n->next;
    }

    // 新建節點插入桶頭
    node_t *new_node = malloc(sizeof(*new_node));
    if (!new_node) return -1;
    new_node->key = malloc(key_len + 1);
    if (!new_node->key) { free(new_node); return -1; }
    memcpy(new_node->key, key, key_len);
    new_node->key[key_len] = '\0';
    new_node->value = value;
    new_node->next = hm->buckets[idx];
    hm->buckets[idx] = new_node;
    return 0;
}

void *hashmap_search(hash_map hm, const char *key) {
    if (!hm || !key) return NULL;
    size_t idx = hash_str(key, -1) % hm->size;
    for (node_t *n = hm->buckets[idx]; n; n = n->next)
        if (strcmp(n->key, key) == 0) return n->value;
    return NULL;
}

使用示例


// 值類型示例
typedef struct { int id; double score; } Student;

void student_free(void *p) { free(p); }

int main() {
    hash_map hm = hashmap_create(1024);
    Student *s = malloc(sizeof(*s)); s->id = 1; s->score = 95.5;
    hashmap_insert(hm, "Alice", -1, s);

    Student *found = hashmap_search(hm, "Alice");
    if (found) printf("ID=%d Score=%.1f\n", found->id, found->score);

    hashmap_destroy(hm, student_free);
    return 0;
}