C語言通用HashMap實現：從設計原理到生產級代碼

編輯：關於C語言

設計目標

實現一個泛型、跨平台、無內存洩漏的哈希表，支持任意鍵值類型（void*），提供創建、增刪改查、遍歷、銷毀全生命周期API，適合嵌入式到服務端各類C項目。

核心數據結構

// 元素節點
typedef struct _hashmap_elem_t {
    char* key;           // 鍵字符串（調用者管理內存）
    use_state used;      // unused_0 / used_1
    void_ptr data;       // 值指針（調用者分配內存）
} hashmap_elem_t;

// 哈希表結構
typedef struct _hashmap_map_t {
    int table_size;      // 當前桶數組大小（2的冪）
    int size;            // 已存元素數
    hashmap_elem_t* elems; // 桶數組
} hashmap_map_t;

關鍵算法設計

1. 哈希函數：CRC32 + Jenkins Mix + Knuth乘法

static unsigned int _find_hash_index(hashmap_map_t* m, char* keystring) {
    unsigned long key = crc32((unsigned char*)keystring, strlen(keystring));
    // Robert Jenkins 32-bit Mix
    key += (key << 12); key ^= (key >> 22); key += (key << 4);
    key ^= (key >> 9);  key += (key << 10); key ^= (key >> 2);
    key += (key << 7);  key ^= (key >> 12);
    // Knuth Multiplicative Method
    key = (key >> 3) * 2654435761u;
    return key % m->table_size;
}

三層混合保證分佈均勻，抗惡意碰撞攻擊能力強。

2. 衝突解決：線性探測 + 固定鏈長

static int _hashmap_hash(hmap_t in, char* key) {
    if (m->size >= m->table_size/2) return HMAP_E_OVERFLOW; // 負載因子0.5擴容
    int curr = _find_hash_index(m, key);
    for (int i = 0; i < HMAP_CHAIN_LENGTH; i++) {  // 最多探測8次
        elem = m->elems + curr;
        if (elem->used == unused_0) return curr;           // 空槽
        if (elem->used == used_1 && !strcmp(elem->key, key)) return curr; // 找到鍵
        curr = (curr + 1) % m->table_size;
    }
    return HMAP_E_OVERFLOW;
}

HMAP_CHAIN_LENGTH=8 限制最長探測鏈，避免退化，觸發擴容。

3. 動態擴容：2倍增長 + 完全重哈希

static int _hashmap_rehash(hmap_t in) {
    hashmap_elem_t* temp = calloc(2 * m->table_size, sizeof(hashmap_elem_t));
    // ... 重新插入所有元素 ...
    free(old_elems);
    m->elems = temp;
    m->table_size *= 2;
    m->size = 0;  // 重新計數
}

API 設計亮點

函數	簽名	語義
創建	`hmap_t hashmap_create()`	返回不透明句柄，初始256桶
插入	`int hashmap_put(hmap_t, char*, void_ptr)`	鍵重複覆蓋，自動擴容
查找	`int hashmap_get(hmap_t, char, void_ptr)`	雙指針輸出值，未找到返回HMAP_E_NOTFOUND
刪除	`int hashmap_remove(hmap_t, char, void_ptr)`	可選輸出被刪值，負載因子不降縮容
遍歷	`int hashmap_iterate(hmap_t, callback, void_ptr)`	回調返回非0終止遍歷，支持提前退出
銷毀	`void hashmap_destroy(hmap_t, free_fn, void_ptr)`	調用釋放回調，遞歸釋放嵌套HashMap

內存安全與測試

測試代碼演示嵌套HashMap（用戶數據含子Map），配合_CrtDumpMemoryLeaks()驗證無洩漏：

// 釋放回調鏈
static int free_data(void* data, void* arg) {
    userdata* dat = (userdata*)data;
    hashmap_destroy(dat->map, free_elem, 0); // 遞歸釋放子Map
    free(dat);
    return 0;
}
hashmap_destroy(map, free_data, 0); // 一鍵清理整棵樹