演算法實作筆記：從零手寫 Hash Table（雜湊表）

前言：為什麼需要 Hash Table？

在資料結構的譜系中，鏈結串列 插入刪除 O(1) 但查找 O(n)；二元搜尋樹 查找 O(log n) 卻需額外指標維護平衡。Hash Table（雜湊表） 以「空間換時間」的思想，提供平均 O(1) 的查找、插入、刪除，且實作相對簡單，是工程中極高頻的基礎組件。

核心概念：雜湊函數與鏈位法解決衝突

將鍵值透過雜湊函數映射到陣列索引（桶位）。當不同鍵值落入同一桶位（衝突）時，採用鏈位法：每個桶位維護一條鏈結串列，同桶鍵值串接在鏈上。

本文示例採用最簡單的除留餘數法：index = key % TABLE_SIZE。

資料結構定義

#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 10
#define TRUE 1
#define FALSE 0
typedef int STATUS;

/* 鏈結串列節點 */
typedef struct _NODE {
    int data;
    struct _NODE *next;
} NODE;

/* 雜湊表結構：固定大小桶位陣列 */
typedef struct _HASH_TABLE {
    NODE *buckets[TABLE_SIZE];
} HASH_TABLE;

核心操作實作

1. 建立雜湊表

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

2. 查找資料

NODE *find_data_in_hash(HASH_TABLE *ht, int key) {
    if (!ht) return NULL;

    NODE *cur = ht->buckets[key % TABLE_SIZE];
    while (cur) {
        if (cur->data == key) return cur;
        cur = cur->next;
    }
    return NULL;  // 未找到
}

3. 插入資料（不允許重複鍵）

STATUS insert_data_into_hash(HASH_TABLE *ht, int key) {
    if (!ht) return FALSE;

    int idx = key % TABLE_SIZE;
    NODE *head = ht->buckets[idx];

    /* 桶位為空，直接建立首節點 */
    if (!head) {
        NODE *new_node = (NODE *)malloc(sizeof(NODE));
        if (!new_node) return FALSE;
        new_node->data = key;
        new_node->next = NULL;
        ht->buckets[idx] = new_node;
        return TRUE;
    }

    /* 檢查重複 */
    if (find_data_in_hash(ht, key)) return FALSE;

    /* 尾插法掛入鏈表末尾 */
    while (head->next) head = head->next;
    NODE *new_node = (NODE *)malloc(sizeof(NODE));
    if (!new_node) return FALSE;
    new_node->data = key;
    new_node->next = NULL;
    head->next = new_node;
    return TRUE;
}

4. 刪除資料

STATUS delete_data_from_hash(HASH_TABLE *ht, int key) {
    if (!ht) return FALSE;

    int idx = key % TABLE_SIZE;
    NODE *head = ht->buckets[idx];
    if (!head) return FALSE;

    NODE *target = find_data_in_hash(ht, key);
    if (!target) return FALSE;

    /* 刪除頭節點 */
    if (target == head) {
        ht->buckets[idx] = head->next;
    } else {
        /* 找前驅節點 */
        NODE *prev = head;
        while (prev->next != target) prev = prev->next;
        prev->next = target->next;
    }
    free(target);
    return TRUE;
}

效能分析與優化方向

關鍵優化點：

• 負載因子：當 元素數/桶位數 > 0.75 時觸發 Rehash（擴容重雜湊），維持 O(1)。
• 雜湊函數品質：採用 MurmurHash、FNV-1a 等高品質函數，減少衝突。
• 開放定址法：線性探測、二次探測、雙重雜湊，適合資料量固定、追求高快取命中率的場景。
• 紅黑樹化桶位：Java 8 HashMap 在鏈長 > 8 時轉紅黑樹，將最壞查找降為 O(log n)。

思考延伸：Hash Table + BST 複合結構

文末提到「Hash Table 可與二元樹形成複合結構」。典型應用：LRU Cache 以 Hash Table 快速定位節點，雙向鏈表維護存取順序；資料庫索引 中 Hash 索引定位頁，B+ 樹範圍查詢。理解各結構優劣，靈活組合才是架構師必修課。

完整測試主程式

int main(void) {
    HASH_TABLE *ht = create_hash_table();
    insert_data_into_hash(ht, 15);
    insert_data_into_hash(ht, 25);  // 同桶 5
    insert_data_into_hash(ht, 7);

    NODE *n = find_data_in_hash(ht, 25);
    printf("Find 25: %s\n", n ? "OK" : "FAIL");

    delete_data_from_hash(ht, 15);
    printf("Delete 15: %s\n", find_data_in_hash(ht, 15) ? "FAIL" : "OK");

    /* 記憶體釋放略 */
    return 0;
}