C語言HashTable完整實現：ELF哈希、鏈表解決衝突、內存池管理、高效遍歷

接口設計

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);      // 刪除單節點

核心數據結構

typedef struct hashnode_struct {
    struct hashnode_struct *next;  // 衝突鏈表
    const char *key;
    void *val;
} *hashnode;

typedef struct hashtable_struct {
    pool_t p;                      // 內存池
    int size;                      // 桶數組大小
    int count;                     // 有效節點數
    struct hashnode_struct *z;     // 桶數組
    // 遍歷優化字段
    int bucket;                    // 當前遍歷桶索引
    hashnode node;                 // 當前遍歷節點游標
} *hashtable;

關鍵算法實現

ELF哈希函數

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) != 0)
            h ^= (g >> 24);
        h &= ~g;
    }
    return (int)h;
}

節點查找與創建

static hashnode hashtable_node_get(hashtable h, const char* key, int len, int index) {
    int i = index % h->size;
    for (hashnode node = &h->z[i]; node; node = node->next)
        if (node->key && strlen(node->key) == len && strncmp(key, node->key, len) == 0)
            return node;
    return NULL;
}

static hashnode hashnode_node_new(hashtable h, int index) {
    int i = index % h->size;
    h->count++;
    // 復用已刪除節點（key==NULL）
    for (hashnode node = &h->z[i]; node; node = node->next)
        if (!node->key) return node;
    // 新建節點並頭插法入鏈
    hashnode node = pool_malloc(h->p, sizeof(_hashnode));
    node->next = h->z[i].next;
    h->z[i].next = node;
    return node;
}

高效遍歷機制

引入bucket和node游標，實現O(1)均攤時間的iter_next：

int hashtable_iter_first(hashtable h) {
    h->bucket = -1; h->node = NULL;
    return hashtable_iter_next(h);
}

int hashtable_iter_next(hashtable h) {
    // 先在當前桶鏈表推進
    while (h->node) {
        h->node = h->node->next;
        if (h->node && h->node->key && h->node->val) return 1;
    }
    // 換桶
    for (h->bucket++; h->bucket < h->size; h->bucket++) {
        h->node = &h->z[h->bucket];
        while (h->node) {
            if (h->node->key && h->node->val) return 1;
            h->node = h->node->next;
        }
    }
    h->bucket = -1; h->node = NULL; return 0;
}

刪除節點時的遍歷游標維護

if (h->node == deleted_node)
    hashtable_iter_next(h);  // 推進游標避免懸空

內存管理優勢

所有分配基於內存池（pool_t），hashtable_free單次調用pool_free即可批量釋放，避免碎片且性能優異。