數據結構：C語言實現散列表（哈希表）—— 除留餘數法 + 線性探測

編輯：關於C語言

散列表核心設計

哈希函數：除留餘數法 `H(key) = key % TABLE_SIZE`
衝突解決：開放定址法——線性探測 `(addr + 1) % TABLE_SIZE`
空槽標記：`NULLKEY = -32768`（假設業務數據為非負整數）
表長：素數 7（減少聚集，演示用；生產環境動態擴容）

資料結構定義

#define HASH_SIZE 7
#define NULLKEY -32768

typedef int Status;
#define OK 1
#define ERROR 0

typedef struct {
    int *elem;      // 動態數組基址
    int count;      // 當前元素數（此處復用為表長）
} HashTable;

核心操作實現

1. 初始化

Status init_hash(HashTable *ht) {
    ht->elem = (int *)malloc(HASH_SIZE * sizeof(int));
    if (!ht->elem) return ERROR;
    ht->count = HASH_SIZE;
    for (int i = 0; i < HASH_SIZE; i++) ht->elem[i] = NULLKEY;
    return OK;
}

2. 哈希函數

int hash_func(int key) {
    return key % HASH_SIZE;
}

3. 插入（含線性探測）

void hash_insert(HashTable *ht, int key) {
    int addr = hash_func(key);
    // 線性探測尋找空槽
    while (ht->elem[addr] != NULLKEY) {
        addr = (addr + 1) % HASH_SIZE;
    }
    ht->elem[addr] = key;
}

4. 查找

// 返回索引，-1 表示未找到
int hash_search(HashTable *ht, int key) {
    int addr = hash_func(key);
    int start = addr;
    do {
        if (ht->elem[addr] == key) return addr;
        if (ht->elem[addr] == NULLKEY) return -1;  // 遇到空槽，必不存在
        addr = (addr + 1) % HASH_SIZE;
    } while (addr != start);  // 繞回起點，表滿未找到
    return -1;
}

5. 顯示表內容

void hash_display(HashTable *ht) {
    printf("==============================\n");
    for (int i = 0; i < ht->count; i++) {
        if (ht->elem[i] == NULLKEY) printf("[%d]: NULL ", i);
        else printf("[%d]: %d ", i, ht->elem[i]);
    }
    printf("\n==============================\n");
}

完整測試主程式

int main() {
    HashTable ht;
    int data[] = {13, 29, 27, 28, 26, 30, 38};  // 7 個數，恰好填滿
    int n = sizeof(data) / sizeof(data[0]);

    init_hash(&ht);
    for (int i = 0; i < n; i++) hash_insert(&ht, data[i]);

    hash_display(&ht);

    // 查找測試
    int targets[] = {27, 38, 99};
    for (int i = 0; i < 3; i++) {
        int idx = hash_search(&ht, targets[i]);
        if (idx >= 0) printf("找到 %d @ 索引 %d\n", targets[i], idx);
        else printf("%d 不存在\n", targets[i]);
    }

    free(ht.elem);
    return 0;
}

插入過程圖解（關鍵步驟）

插入鍵值	初始地址	探測序列	最終位置
13	13%7=6	6	6
29	29%7=1	1	1
27	27%7=6	6(佔)→0	0
28	28%7=0	0(佔)→1(佔)→2	2
26	26%7=5	5	5
30	30%7=2	2(佔)→3	3
38	38%7=3	3(佔)→4	4

最終表狀態

索引:  0   1   2   3   4   5   6
值 :  27  29  28  30  38  26  13

關鍵性能指標

裝載因子 α = n/m = 7/7 = 1.0（演示極限；工程中通常 α ≤ 0.7 觸發擴容）
平均查找長度 ASL：取決於聚集程度，線性探測易產生一次聚集

工程級優化方向

雙重哈希：`(h1(key) + i * h2(key)) % m`，消除一次聚集
動態擴容：α 達閾值時 `rehash` 到 2× 素數表長
鏈地址法：每槽掛鏈表，支援任意 α，實現簡單
鍵值泛型：`void *key, *val` + `hash_func`/`eq_func` 函數指針
並發安全：分段鎖（Segment Lock）或無鎖 CAS

常見坑點

| 坑點 | 後果 | 修正 | |------|------|------| | `NULLKEY` 與合法鍵值衝突 | 正常數據被誤判為空槽 | 選用業務不可能值，或改用 `bool occupied[]` 陣列 | | 線性探測死循環 | 表滿時查找/插入無限循環 | 插入前檢查 `count == size`；查找記錄 `start` 判斷繞回 | | `malloc` 未判空 | OOM 時段錯誤 | 生產代碼必須判空並返回錯誤碼 |