C語言哈希表簡易實現：ELF Hash + 拉鏈法 + 內存池 + 迭代器遍歷

接口設計

[c]
hashtable hashtable_new(int size);           // 創建，size 為桶數
void hashtable_put(hashtable h, const char* key, void* val); // 存入/更新
void* hashtable_get(hashtable h, const char* key);           // 查找
void hashtable_free(hashtable h);            // 整體釋放
void hashtable_delete_node(hashtable h, const char* key);    // 刪除單節點
// 遍歷接口
int hashtable_iter_first(hashtable h);       // 定位首節點
int hashtable_iter_next(hashtable h);        // 移動到下一節點
// 當前節點可通過 h->node 訪問

數據結構

[c]
typedef struct hashnode_struct {
    struct hashnode_struct *next;
    const char *key;
    void *val;
} *hashnode, _hashnode;

typedef struct hashtable_struct {
    pool_t p;                 // 內存池
    int size;                 // 桶數
    int count;                // 節點數
    struct hashnode_struct *z; // 桶陣列
    int bucket;               // 遍歷游標：當前桶索引
    hashnode node;            // 遍歷游標：當前節點
} *hashtable, _hashtable;

核心算法

ELF Hash

[c]
static int hashcode(const char *s, int len) {
    const unsigned char *name = (const unsigned char*)s;
    unsigned long h = 0, g;
    for (int i = 0; i < len; i++) {
        h = (h << 4) + name[i];
        if ((g = h & 0xF0000000UL)) h ^= g >> 24;
        h &= ~g;
    }
    return (int)h;
}

插入/更新

[c]
void hashtable_put(hashtable h, const char *key, void *val) {
    if (!h || !key) return;
    int len = strlen(key), index = hashcode(key, len);
    hashnode n = hashtable_node_get(h, key, len, index);
    if (n) { n->key = key; n->val = val; return; } // 更新
    n = hashnode_node_new(h, index); // 新建
    n->key = key; n->val = val;
}

遍歷優化

採用 bucket + node 雙游標，iter_first 初始化，iter_next 先走鏈表 next，鏈表盡頭再掃描下一桶，實現 O(節點數) 遍歷，避免掃描空桶。

內存池整合

所有節點內存從 pool_t 分配，hashtable_free 僅需 pool_free(h->p) 一次性釋放，極簡高效。

刪除節點與遍歷協同

刪除時將 key/val 置 NULL，count--；若被刪節點正是遍歷游標 h->node，調用 hashtable_iter_next(h) 推進游標，保證遍歷不卡死。

總結

此實現包含哈希表核心要素：良好哈希函數、拉鏈解決衝突、內存池管理、高效迭代器、懶惰刪除，適合嵌入式/系統級 C 項目直接使用或擴展。