資料結構設計

#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; ielem[i].key = NULLKEY;
    return 1;
}

2. 雜湊函數與衝突處理

unsigned Hash(KeyType K) { return K % m; }           // 除留餘數法
void collision(int *p, int d) { *p = (*p + d) % m; } // 線性探測

3. 查找（核心演算法 9.17）

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;
    }
    return (K == H.elem[*p].key) ? 1 : 0; // 1=找到, 0=未找到(插入位置在 p)
}

4. 插入與動態重建（演算法 9.18）

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

    if (c < hashsize[H->sizeindex] / 2) { // 衝突次數未達閾值
        H->elem[p] = e;
        H->count++;
        return 1;
    } else {
        RecreateHashTable(H); // 重建：擴容、重新雜湊
        return 0;
    }
}

void RecreateHashTable(HashTable *H) {
    int count = H->count;
    ElemType *old = (ElemType*)malloc(count * sizeof(ElemType));
    ElemType *q = old;
    for (int i=0; ielem[i].key != NULLKEY) *q++ = H->elem[i];

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

    for (q = old; q < old+count; q++) InsertHash(H, *q);
    free(old);
}

5. 遍列與銷毀

void TraverseHash(HashTable H, void(*Visit)(int, ElemType)) {
    printf("雜湊地址 0~%d\n", m-1);
    for (int i=0; ielem); H->elem = NULL; H->count = 0; H->sizeindex = 0;
}

主程式測試流程

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}}; // 含重複鍵 60
    HashTable h; InitHashTable(&h);

    for (int i=0; i

執行結果關鍵點

第 2 筆鍵值 60 插入成功，第 9 筆鍵值 60 偵測重複 → 略過。
初始容量 11，插入 9 筆負載因子 ≈ 0.82，超過 0.5 閾值 → 第 10 筆插入觸發重建至容量 19。
重建後所有鍵值重新雜湊，分布更均勻。


教學重點總結

開放定址法：衝突時在表內尋找下一空槽，無額外鏈表記憶體開銷。
線性探測：簡單但易產生「堆積」；實務常用二次探測或雙重雜湊。
動態重建：負載因子超標時擴容並重新雜湊，維持 O(1) 平均查找。
素數容量序列：減少鍵值模運算碰撞，提升分布均勻度。


此實作為經典教科書《資料結構 (C語言版)》演算法 9.17/9.18 的完整可執行碼，適合資結課程實驗與面試複習。