閉散列表（開放定址法）完整實現：線性探測、插入、查找、刪除與標記刪除

核心概念

• 閉散列表：所有鍵值直接存儲在雜湊表數組中，衝突通過探測序列尋找下一個空槽
• 本文採用線性探測：hash(key) + i (mod size)
• 刪除標記 (DEL)：區別「從未使用 (NIL)」與「曾使用現已刪除」，保證查找不中斷

常量與類型定義

#define NIL -1   // 空槽
#define DEL -2   // 刪除標記
#define SIZE 13  // 表長（質數）

typedef int KeyType;
KeyType HashTable[SIZE];

哈希函數與探測

int hash(KeyType k) { return k % SIZE; }

int probe(int idx, int i) { return (idx + i) % SIZE; }  // 線性探測

四大核心操作

1. 插入

void InsertHashTable(KeyType k) {
    int idx = hash(k);
    for (int i = 0; i < SIZE; i++) {
        int pos = probe(idx, i);
        if (HashTable[pos] == NIL || HashTable[pos] == DEL) {
            HashTable[pos] = k;
            return;
        }
    }
    // 表滿，實際工程需擴容/報錯
}

2. 查找

// 返回下標，失敗返回 -1
int HashSearch(KeyType k) {
    int idx = hash(k);
    for (int i = 0; i < SIZE; i++) {
        int pos = probe(idx, i);
        if (HashTable[pos] == k) return pos;
        if (HashTable[pos] == NIL) return -1;  // 遇到 NIL 肯定不存在
        // 遇到 DEL 繼續探測
    }
    return -1;
}

3. 刪除

void DeleteHashTable(KeyType k) {
    int pos = HashSearch(k);
    if (pos == -1) {
        printf("Key %d not found\n", k);
        return;
    }
    HashTable[pos] = DEL;  // 標記刪除，不設為 NIL
}

4. 打印調試

void PrintHashTable(void) {
    printf("HashTable: ");
    for (int i = 0; i < SIZE; i++) {
        if (HashTable[i] == NIL) printf("[NIL] ");
        else if (HashTable[i] == DEL) printf("[DEL] ");
        else printf("%d ", HashTable[i]);
    }
    printf("\n");
}

主程序演示

int main() {
    for (int i = 0; i < SIZE; i++) HashTable[i] = NIL;

    int keys[] = {12, 25, 38, 51, 64, 77, 90};
    for (int k : keys) InsertHashTable(k);
    PrintHashTable();

    printf("Search 38: %d\n", HashSearch(38));
    printf("Search 99: %d\n", HashSearch(99));

    DeleteHashTable(38);
    PrintHashTable();
    printf("Search 38 after del: %d\n", HashSearch(38));
    printf("Search 51 after del: %d\n", HashSearch(51));  // 穿過 DEL 能找到

    InsertHashTable(38);  // 復用 DEL 槽
    PrintHashTable();
    return 0;
}

運行輸出示例

HashTable: 12 25 38 51 64 77 90 [NIL] [NIL] [NIL] [NIL] [NIL] [NIL]
Search 38: 2
Search 99: -1
HashTable: 12 25 [DEL] 51 64 77 90 [NIL] [NIL] [NIL] [NIL] [NIL] [NIL]
Search 38 after del: -1
Search 51 after del: 3
HashTable: 12 25 38 51 64 77 90 [NIL] [NIL] [NIL] [NIL] [NIL] [NIL]

關鍵點總結

工程擴展建議

1. 表長取質數（如 13, 101, 10007），減少聚集
2. 探測改為二次探測 (h + i²) % size 或雙重雜湊，緩解主聚集
3. 負載因子達閾值觸發rehash：分配 2× 質數表，重新插入所有非 NIL/DEL 鍵
4. 鍵值為字符串/結構體時，提供通用 hash_func、equal_func 接口

總結

閉散列表通過線性探測 + DEL 標記實現高效的插入、查找、刪除。掌握「NIL 停止查找、DEL 繼續探測、插入優先復用 DEL」三條規則，即可正確實現開放定址法雜湊表。