您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

雜湊表原理與C語言實作：從設計到完整增刪查代碼

編輯：關於C

雜湊表是介於鏈表與二叉樹之間的「黃金平衡點」：鏈表插刪 O(1) 但查詢 O(n)；二叉樹查詢 O(log n) 但需額外指標與平衡維護。雜湊表以空間換時間，透過雜湊函數將鍵值映射到桶位，桶內以鏈表解決衝突，實現平均 O(1) 的查找、插入、刪除，且記憶體開銷可控。

生活化類比：圖書館分類法

線性表/鏈表：書堆在一起，找書需逐本翻閱
二叉樹：書按編號嚴格排序，二分查找快，但維護排序成本高
雜湊表：書按類別分架（文學、理工、藝術），找書先定類別再在該架查找，效率與成本雙贏

核心資料結構定義

typedef struct _NODE {
    int data;
    struct _NODE* next;
} NODE;

typedef struct _HASH_TABLE {
    NODE* value[10];  // 固定 10 個桶位，簡化演示
} HASH_TABLE;

雜湊表建立

HASH_TABLE* create_hash_table() {
    HASH_TABLE* pHashTbl = (HASH_TABLE*)malloc(sizeof(HASH_TABLE));
    memset(pHashTbl, 0, sizeof(HASH_TABLE));  // 全桶位初始化為 NULL
    return pHashTbl;
}

雜湊函數與查找

採用簡單取模法：index = data % 10

NODE* find_data_in_hash(HASH_TABLE* pHashTbl, int data) {
    if (!pHashTbl) return NULL;
    
    NODE* pNode = pHashTbl->value[data % 10];
    if (!pNode) return NULL;
    
    while (pNode) {
        if (data == pNode->data) return pNode;
        pNode = pNode->next;
    }
    return NULL;
}

資料插入

STATUS insert_data_into_hash(HASH_TABLE* pHashTbl, int data) {
    if (!pHashTbl) return FALSE;
    
    int idx = data % 10;
    if (!pHashTbl->value[idx]) {  // 桶位為空，直接建立首節點
        NODE* pNode = (NODE*)malloc(sizeof(NODE));
        memset(pNode, 0, sizeof(NODE));
        pNode->data = data;
        pHashTbl->value[idx] = pNode;
        return TRUE;
    }
    
    if (find_data_in_hash(pHashTbl, data)) return FALSE;  // 去重
    
    // 桶位非空，遍歷至鏈表尾部插入
    NODE* pNode = pHashTbl->value[idx];
    while (pNode->next) pNode = pNode->next;
    
    pNode->next = (NODE*)malloc(sizeof(NODE));
    memset(pNode->next, 0, sizeof(NODE));
    pNode->next->data = data;
    return TRUE;
}

資料刪除

STATUS delete_data_from_hash(HASH_TABLE* pHashTbl, int data) {
    if (!pHashTbl || !pHashTbl->value[data % 10]) return FALSE;
    
    NODE* pNode = find_data_in_hash(pHashTbl, data);
    if (!pNode) return FALSE;
    
    int idx = data % 10;
    if (pNode == pHashTbl->value[idx]) {  // 刪除桶位首節點
        pHashTbl->value[idx] = pNode->next;
        goto final;
    }
    
    // 刪除中間/尾部節點：需找前驅
    NODE* pHead = pHashTbl->value[idx];
    while (pNode != pHead->next) pHead = pHead->next;
    pHead->next = pNode->next;
    
final:
    free(pNode);
    return TRUE;
}