您现在的位置：程式碼之家 >> 編程語言 > >> 更多程式語言 >> 更多程式設計知識

哈希表 C 語言完整實作：開放定址法、線性探測與動態重建

編輯：更多程式設計知識

前言

哈希表是鍵值查找的核心資料結構。本文提供教學級 C 語言實作，採用開放定址法 + 線性探測解決衝突，並支援動態擴容重建，完整包含初始化、插入、查找、遍歷、銷毀操作。

一、核心資料結構


#define NULLKEY 0      // 0 代表空槽
#define N 10           // 測試資料筆數
typedef int KeyType;

typedef struct {
    KeyType key;
    int ord;           // 附加資料：原始序號
} ElemType;

// 擴容用質數序列
int hashsize[] = {11, 19, 29, 37};
int m = 0;             // 當前表長 (全域)

typedef struct {
    ElemType *elem;    // 動態陣列基址
    int count;         // 當前元素數
    int sizeindex;     // hashsize 索引
} HashTable;

二、核心操作實作

1. 初始化與銷毀


int InitHashTable(HashTable *H) {
    H->count = 0;
    H->sizeindex = 0;
    m = hashsize[0];
    H->elem = (ElemType*)malloc(m * sizeof(ElemType));
    if (!H->elem) exit(0);
    for (int i = 0; i < m; i++) H->elem[i].key = NULLKEY;
    return 1;
}

void DestroyHashTable(HashTable *H) {
    free(H->elem);
    H->elem = NULL;
    H->count = 0;
    H->sizeindex = 0;
}

2. 雜湊函數與衝突處理


// 除留餘數法
unsigned Hash(KeyType K) { return K % m; }

// 線性探測：p = (p + d) % m
void collision(int *p, int d) { *p = (*p + d) % m; }

3. 查找 (核心邏輯)


// 回傳: SUCCESS=找到, UNSUCCESS=未找到(並回傳插入位置 p), c=衝突次數
int SearchHash(HashTable H, KeyType K, int *p, int *c) {
    *p = Hash(K);
    while (H.elem[*p].key != NULLKEY && !(K == H.elem[*p].key)) {
        (*c)++;
        if (*c < m) collision(p, *c);
        else break;
    }
    if (K == H.elem[*p].key) return SUCCESS;
    return UNSUCCESS;  // p 為可插入位置
}

4. 插入與動態重建


#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1

int InsertHash(HashTable *H, ElemType e) {
    int c = 0, p;
    if (SearchHash(*H, e.key, &p, &c)) return DUPLICATE;  // 鍵值重複

    if (c < hashsize[H->sizeindex] / 2) {  // 衝突未達閾值
        H->elem[p] = e;
        H->count++;
        return 1;
    } else {
        RecreateHashTable(H);  // 觸發重建
        return 0;
    }
}

void RecreateHashTable(HashTable *H) {
    // 1. 備份現有資料
    ElemType *backup = malloc(H->count * sizeof(ElemType));
    ElemType *q = backup;
    for (int i = 0; i < m; i++)
        if (H->elem[i].key != NULLKEY) *q++ = H->elem[i];

    // 2. 擴容
    H->count = 0;
    H->sizeindex++;
    m = hashsize[H->sizeindex];
    H->elem = realloc(H->elem, m * sizeof(ElemType));
    for (int i = 0; i < m; i++) H->elem[i].key = NULLKEY;

    // 3. 重新插入
    for (q = backup; q < backup + H->count; q++)
        InsertHash(H, *q);
    free(backup);
    printf("重建哈希表，新容量: %d\n", m);
}

5. 遍歷與查找介面


void TraverseHash(HashTable H, void(*Visit)(int, ElemType)) {
    printf("哈希地址 0～%d\n", m-1);
    for (int i = 0; i < m; i++)
        if (H.elem[i].key != NULLKEY) Visit(i, H.elem[i]);
}

int Find(HashTable H, KeyType K, int *p) {
    int c = 0;
    *p = Hash(K);
    while (H.elem[*p].key != NULLKEY && !(K == H.elem[*p].key)) {
        c++;
        if (c < m) collision(p, c);
        else return UNSUCCESS;
    }
    return (K == H.elem[*p].key) ? SUCCESS : UNSUCCESS;
}

三、主程式測試流程


int main() {
    ElemType r[N] = {{17,1},{60,2},{29,3},{38,4},{1,5},{2,6},{3,7},{4,8},{60,9},{13,10}};
    HashTable h; int i, j, p; KeyType k;

    InitHashTable(&h);
    // 插入前 9 筆 (第 10 筆鍵值 60 重複)
    for (i = 0; i < N-1; i++) {
        j = InsertHash(&h, r[i]);
        if (j == DUPLICATE)
            printf("鍵值 %d 已存在，跳過 (%d,%d)\n", r[i].key, r[i].key, r[i].ord);
    }

    printf("=== 初始表遍歷 ===\n");
    TraverseHash(h, [](int p, ElemType e){ printf("addr=%d (%d,%d)\n", p, e.key, e.ord); });

    printf("輸入查找鍵值: "); scanf("%d", &k);
    if (Find(h, k, &p) == SUCCESS) printf("找到: addr=%d (%d,%d)\n", p, h.elem[p].key, h.elem[p].ord);
    else printf("未找到\n");

    // 插入第 10 筆觸發重建
    j = InsertHash(&h, r[i]);
    if (j == 0) InsertHash(&h, r[i]);  // 重建後再插

    printf("=== 重建後遍歷 ===\n");
    TraverseHash(h, [](int p, ElemType e){ printf("addr=%d (%d,%d)\n", p, e.key, e.ord); });

    DestroyHashTable(&h);
    return 0;
}

四、執行結果範例

鍵值 60 已存在，跳過 (60,9)
=== 初始表遍歷 ===
哈希地址 0～10
addr=1 (1,5)
addr=2 (2,6)
addr=3 (3,7)
addr=4 (4,8)
addr=5 (60,2)
addr=6 (17,1)
addr=7 (29,3)
addr=8 (38,4)
輸入查找鍵值: 17
找到: addr=6 (17,1)
重建哈希表，新容量: 19
=== 重建後遍歷 ===
哈希地址 0～18
addr=0 (38,4)
addr=1 (1,5)
addr=2 (2,6)
addr=3 (3,7)
addr=4 (4,8)
addr=6 (60,2)
addr=10 (29,3)
addr=13 (13,10)
addr=17 (17,1)
輸入查找鍵值: 13
找到: addr=13 (13,10)

五、關鍵設計點總結

機制	實作細節	優/缺點
衝突解決	線性探測	簡單、緩存友好；易產生聚集
負載因子閾值	衝突次數 < 表長/2	動態觸發重建，避免效能急跌
擴容策略	質數序列 {11,19,29,37}	減少模運算衝突，利用 CPU 快取
重建方式	完整重新雜湊	O(n) 擴攤銷成本，查找維持 O(1) 期望