練習題與詳解 — 雜湊表

本檔收錄 5 題由易到難的練習。建議流程：先蓋住解答自己寫，卡住再看 「解題思路」，寫完對照「參考解答」。每題完整程式碼在 exercises/：

cc -std=c11 -Wall -Wextra -o /tmp/out exercises/ex1_bucket_stats.c && /tmp/out

本單元的基準程式碼是 K&R §6.6 的鏈結法雜湊表： hash = c + 31*hash、hashtab[HASHSIZE] 桶陣列、每桶一條鏈。

---

練習 1：不同 HASHSIZE 下的桶分布（難度：基礎）

題目

把同一批 50 個鍵（var0..var24、word0..word24）分別裝進 HASHSIZE = 1、10、101、1000 的表，統計並比較： 使用中的桶數、最長鏈、平均鏈長。觀察表太小與太大的代價。

解題思路

1. 只要統計就不用建表：本題觀察的是「鍵落在哪個桶」的 分布，用一個 unsigned count[hashsize] 計數器陣列即可， 不需要真的配置節點——分析問題先想清楚需要哪些資料。
2. 三個統計量的意義： - 使用中的桶數：hash 函式把鍵攤開的能力； - 最長鏈：最壞情況的查找成本； - 平均鏈長 = 鍵數 ÷ 使用中桶數：平均查找成本 （教科書的載入係數 α = n/m 是以總桶數為分母， 這裡用「有東西的桶」更直觀）。
3. 極端對照： - HASHSIZE=1：% 1 恆為 0，全部擠一桶——雜湊表退化成 線性搜尋的串列，這就是「雜湊表的效率全靠分布」的證明； - HASHSIZE=1000：幾乎零碰撞，但 95% 的桶閒置——空間浪費； - HASHSIZE=101（K&R 的選擇）：質數且量級接近鍵數， 平均鏈長 ≈ 1，最長鏈 2——甜蜜點。
4. 為什麼選質數：鍵若有規律（例如都以相同字尾結束）， 合數的表大小容易與規律共振（公因數讓某些桶永遠拿不到鍵）； 質數把規律打散。
5. calloc 起手：計數器需要零初始化，calloc 一步到位。

參考解答

/*
 * ex1_bucket_stats.c — 練習 1：不同 HASHSIZE 下的桶分布觀察
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex1_bucket_stats.c
 * 執行：/tmp/out
 *
 * 把同一批鍵分別裝進 HASHSIZE = 1、10、101、1000 的表，
 * 統計：使用中的桶數、最長鏈、平均鏈長（載入係數）。
 * HASHSIZE=1 退化成串列；1000 幾乎沒有碰撞但浪費空間。
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NKEYS 50

/* K&R §6.6 的字串雜湊：hash = hash*31 + c */
static unsigned kr_hash(const char *s, unsigned hashsize)
{
    unsigned hashval;

    for (hashval = 0; *s != '\0'; s++)
        hashval = (unsigned)*s + 31u * hashval;
    return hashval % hashsize;
}

/* 產生 50 個代表性的鍵：var0..var24 與 word0..word24 */
static void make_keys(char keys[NKEYS][16])
{
    for (int i = 0; i < 25; i++)
        snprintf(keys[i], 16, "var%d", i);
    for (int i = 0; i < 25; i++)
        snprintf(keys[25 + i], 16, "word%d", i);
}

/*
 * 對指定 hashsize 統計分布。
 * 不真的建鏈結串列——只需要每桶的計數器就能算出所有統計量。
 */
static void bucket_stats(unsigned hashsize)
{
    char keys[NKEYS][16];
    make_keys(keys);

    unsigned *count = calloc(hashsize, sizeof *count);
    if (count == NULL) {
        fprintf(stderr, "out of memory\n");
        exit(1);
    }

    for (int i = 0; i < NKEYS; i++)
        count[kr_hash(keys[i], hashsize)]++;

    unsigned used = 0, longest = 0;
    for (unsigned b = 0; b < hashsize; b++) {
        if (count[b] > 0)
            used++;
        if (count[b] > longest)
            longest = count[b];
    }

    printf("  HASHSIZE=%4u: buckets used %3u/%4u, longest chain %2u, "
           "avg chain %.2f\n",
           hashsize, used, hashsize, longest,
           used > 0 ? (double)NKEYS / used : 0.0);

    /* 小表順便印出每桶計數，看得到「全部擠在一起」的樣子 */
    if (hashsize <= 10) {
        printf("    per-bucket:");
        for (unsigned b = 0; b < hashsize; b++)
            printf(" %u", count[b]);
        printf("\n");
    }

    free(count);
}

int main(void)
{
    printf("distribute %d keys (var0..24, word0..24) with K&R hash:\n\n",
           NKEYS);

    bucket_stats(1);        /* 退化：全部在同一桶 -> 就是串列 */
    bucket_stats(10);
    bucket_stats(101);      /* K&R 的選擇：質數、量級接近鍵數 */
    bucket_stats(1000);     /* 幾乎無碰撞，但 95% 的桶閒置 */

    printf("\nlesson: table size ~ number of keys (load factor ~1)\n");
    printf("balances memory vs. chain length; primes spread better.\n");
    return 0;
}

程式碼講解

• kr_hash 把 hashsize 當參數傳入而不是用巨集—— 同一個函式要服務四種表大小，「把常數變參數」是實驗程式的 基本手法。
• bucket_stats 一趟迴圈同時算三個統計量； 小表（≤10）加印 per-bucket 計數，「50 全在一桶」與 「每桶恰 5 個」的對比一眼看懂。
• 輸出解讀：HASHSIZE=10 時每桶剛好 5——var0..var24 與 word0..word24 的尾碼數字在 mod 10 下均勻，是測資設計 湊巧幫了忙；101 時 45 桶裝 50 鍵、最長鏈 2，接近理想隨機分布。
• 易錯處：hashval 用有號 int——字元值累乘後溢位是 UB； K&R 原版就用 unsigned，照做。

範例輸出

distribute 50 keys (var0..24, word0..24) with K&R hash:

  HASHSIZE=   1: buckets used   1/   1, longest chain 50, avg chain 50.00
    per-bucket: 50
  HASHSIZE=  10: buckets used  10/  10, longest chain  5, avg chain 5.00
    per-bucket: 5 5 5 5 5 5 5 5 5 5
  HASHSIZE= 101: buckets used  45/ 101, longest chain  2, avg chain 1.11
  HASHSIZE=1000: buckets used  50/1000, longest chain  1, avg chain 1.00

lesson: table size ~ number of keys (load factor ~1)
balances memory vs. chain length; primes spread better.

---

練習 2：count 與 foreach（難度：基礎）

題目

為 K&R 雜湊表加上兩個功能：

• ht_count()：項目總數；
• ht_foreach(visit, user_data)：走訪所有項目並對每個呼叫回呼 void visit(const char *name, const char *defn, void *user_data)。

驗證：重複 install 同一鍵是更新不是新增（count 不變）； 用兩個不同回呼展示 foreach（印出所有項目、統計定義字串總長）。

解題思路

1. 走訪雜湊表的固定模式——雙層迴圈：

for (b = 0; b < HASHSIZE; b++)               /* 外層掃桶 */
    for (np = hashtab[b]; np; np = np->next)  /* 內層走鏈 */

count 與 foreach 都是這個骨架，差別只在迴圈體。 2. foreach 的介面設計（複習函式指標單元）： - 回呼收 name/defn 是唯讀的 const char *； - void *user_data 是關鍵配件：C 的函式指標不能捕捉 環境（沒有閉包），呼叫端的狀態（如累加器）就靠這個 指標夾帶進來。qsort_r、pthread_create 都是同一模式。 3. 兩個回呼展示兩種用法：print_entry 不需要狀態 （user_data 傳 NULL 並忽略）；sum_defn_len 把 size_t total 的位址傳進去，回呼裡累加。 4. count 驗證更新語意：install 對已存在的鍵是換 defn 不是插新節點——count 前後都是 5 就是證據。 5. 輸出順序：foreach 的列印順序是「桶順序」， 與插入順序無關——雜湊表沒有順序概念，這是它與樹的 根本差異（練習 4 深談）。

參考解答

/*
 * ex2_count_foreach.c — 練習 2：雜湊表加上 count 與 foreach
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex2_count_foreach.c
 * 執行：/tmp/out
 *
 * K&R 鏈結法雜湊表（install/lookup），新增：
 *   ht_count  ：項目總數（走訪所有桶、所有鏈）
 *   ht_foreach：對每個項目呼叫回呼（複習函式指標），
 *               並附 void *user_data 讓呼叫端夾帶狀態
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASHSIZE 101

struct nlist {
    struct nlist *next;
    char         *name;
    char         *defn;
};

static struct nlist *hashtab[HASHSIZE];

/* 自製 strdup（-std=c11 下不依賴 POSIX） */
static char *dup_str(const char *s)
{
    char *p = malloc(strlen(s) + 1);
    if (p != NULL)
        strcpy(p, s);
    return p;
}

static unsigned hash(const char *s)
{
    unsigned hashval;

    for (hashval = 0; *s != '\0'; s++)
        hashval = (unsigned)*s + 31u * hashval;
    return hashval % HASHSIZE;
}

static struct nlist *lookup(const char *s)
{
    for (struct nlist *np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
            return np;
    return NULL;
}

static struct nlist *install(const char *name, const char *defn)
{
    struct nlist *np = lookup(name);

    if (np == NULL) {                   /* 新項目：掛到桶的鏈頭 */
        np = malloc(sizeof *np);
        if (np == NULL || (np->name = dup_str(name)) == NULL)
            return NULL;
        unsigned h = hash(name);
        np->next = hashtab[h];
        hashtab[h] = np;
    } else {
        free(np->defn);                 /* 已存在：換定義 */
    }
    if ((np->defn = dup_str(defn)) == NULL)
        return NULL;
    return np;
}

/* ---- 新增 1：項目總數 ---- */
static size_t ht_count(void)
{
    size_t n = 0;

    for (int b = 0; b < HASHSIZE; b++)
        for (const struct nlist *np = hashtab[b]; np != NULL;
             np = np->next)
            n++;
    return n;
}

/* ---- 新增 2：走訪所有項目並套用回呼 ---- */
typedef void (*visit_fn)(const char *name, const char *defn,
                         void *user_data);

static void ht_foreach(visit_fn visit, void *user_data)
{
    for (int b = 0; b < HASHSIZE; b++)
        for (const struct nlist *np = hashtab[b]; np != NULL;
             np = np->next)
            visit(np->name, np->defn, user_data);
}

/* 釋放整張表 */
static void ht_free(void)
{
    for (int b = 0; b < HASHSIZE; b++) {
        struct nlist *np = hashtab[b];
        while (np != NULL) {
            struct nlist *next = np->next;
            free(np->name);
            free(np->defn);
            free(np);
            np = next;
        }
        hashtab[b] = NULL;
    }
}

/* ---- 兩個示範回呼 ---- */

static void print_entry(const char *name, const char *defn, void *ud)
{
    (void)ud;                           /* 這個回呼用不到 user_data */
    printf("    %-8s = %s\n", name, defn);
}

/* 統計定義字串的總長度：結果累加進 user_data 指向的 size_t */
static void sum_defn_len(const char *name, const char *defn, void *ud)
{
    (void)name;
    *(size_t *)ud += strlen(defn);
}

int main(void)
{
    install("PI",    "3.14159");
    install("E",     "2.71828");
    install("SQRT2", "1.41421");
    install("PHI",   "1.61803");
    install("LN2",   "0.69315");

    printf("count after 5 installs      : %zu\n", ht_count());

    install("PI", "3.141592653589793");     /* 更新不是新增 */
    printf("count after re-install PI   : %zu (update, not insert)\n",
           ht_count());

    printf("\nforeach with print_entry:\n");
    ht_foreach(print_entry, NULL);

    size_t total = 0;
    ht_foreach(sum_defn_len, &total);
    printf("\nforeach with sum_defn_len   : total defn length = %zu\n",
           total);

    ht_free();
    printf("count after ht_free         : %zu\n", ht_count());
    return 0;
}

程式碼講解

• dup_str 是自製的 strdup：-std=c11 嚴格模式下 strdup 是 POSIX 函式不保證可見，自己寫三行最穩。
• install 的鏈頭插入 np->next = hashtab[h]; hashtab[h] = np; ——O(1)，順序無所謂（反正雜湊表沒有順序）。
• visit_fn typedef 讓 foreach 的簽名可讀；回呼的第三個參數 void *ud 在 sum_defn_len 中還原成 size_t * 使用—— 型別資訊由「呼叫端與回呼的約定」保證，編譯器幫不上忙， 介面註解要寫清楚。
• ht_free 之後 count 回 0：釋放函式把每個桶設回 NULL， 表回到可重用的初始狀態。
• 易錯處：foreach 的回呼裡刪除目前項目——走訪中修改鏈 會讓 np = np->next 讀已釋放記憶體；要支援「邊走邊刪」 得用練習 3 的指標的指標寫法。

範例輸出

count after 5 installs      : 5
count after re-install PI   : 5 (update, not insert)

foreach with print_entry:
    PHI      = 1.61803
    PI       = 3.141592653589793
    SQRT2    = 1.41421
    LN2      = 0.69315
    E        = 2.71828

foreach with sum_defn_len   : total defn length = 45
count after ht_free         : 0

---

練習 3：undef——指標的指標刪除（難度：進階）

題目

實作 K&R 習題 6-5 的 undef(name)：從雜湊表移除一個項目， 回傳 1（成功）或 0（找不到）。要求用指標的指標走鏈， 「刪鏈頭」與「刪中間」不得有分開的程式碼路徑。 驗證：刪中間、刪頭、刪不存在的鍵、刪後重新 install。

解題思路

1. 樸素寫法的特例：用 prev/cur 走鏈，刪鏈頭時 prev == NULL，要改 hashtab[h] 而不是 prev->next—— 兩條路徑。這正是鏈結串列單元 insert_sorted 討論過的問題， 換到刪除場景再練一次。
2. 統一的觀察：刪除要改的東西是「指向目標節點的那個指標」 ——可能是桶 hashtab[h]，也可能是前一節點的 next。 兩者都是 struct nlist * 的格子，讓 pp 指向格子：

桶 [h] ──> [alpha] ──> [beta] ──> [gamma] ──> NULL
^pp 起點    刪 alpha：*pp = alpha->next（改桶）
           pp = &alpha->next 之後：
                       刪 beta：*pp = beta->next（改 alpha 的 next）

3. 迴圈：while (*pp != NULL)，比對 (*pp)->name； 命中時 *pp = np->next; 繞過節點，然後釋放 name、defn、節點本身三塊記憶體。
4. 釋放順序：先取出 np = *pp 再改 *pp，最後 free np 的內容物——free 之後任何欄位都不可再讀。
5. 驗收設計：alpha/beta/gamma/delta 四鍵，刪 beta（可能在 鏈中）、刪 alpha、刪 nope（不存在）；重 install beta 確認 表在刪除後仍一致可用。

參考解答

/*
 * ex3_undef.c — 練習 3：K&R 習題 6-5 undef（指標的指標版）
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex3_undef.c
 * 執行：/tmp/out
 *
 * undef(name)：從雜湊表移除一個項目。
 * 用「指標的指標」走鏈：刪鏈頭與刪中間共用同一段程式碼
 * （同鏈結串列單元的 insert_sorted 手法）。
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASHSIZE 101

struct nlist {
    struct nlist *next;
    char         *name;
    char         *defn;
};

static struct nlist *hashtab[HASHSIZE];

static char *dup_str(const char *s)
{
    char *p = malloc(strlen(s) + 1);
    if (p != NULL)
        strcpy(p, s);
    return p;
}

static unsigned hash(const char *s)
{
    unsigned hashval;

    for (hashval = 0; *s != '\0'; s++)
        hashval = (unsigned)*s + 31u * hashval;
    return hashval % HASHSIZE;
}

static struct nlist *lookup(const char *s)
{
    for (struct nlist *np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
            return np;
    return NULL;
}

static struct nlist *install(const char *name, const char *defn)
{
    struct nlist *np = lookup(name);

    if (np == NULL) {
        np = malloc(sizeof *np);
        if (np == NULL || (np->name = dup_str(name)) == NULL)
            return NULL;
        unsigned h = hash(name);
        np->next = hashtab[h];
        hashtab[h] = np;
    } else {
        free(np->defn);
    }
    if ((np->defn = dup_str(defn)) == NULL)
        return NULL;
    return np;
}

/*
 * undef：移除 name。回傳 1 成功、0 找不到。
 * pp 從「桶指標本身」出發，一路指向「目前節點的 next 欄位」：
 *   - 目標在鏈頭：*pp 是 hashtab[h]，改它 = 改桶
 *   - 目標在中間：*pp 是前一節點的 next
 * 兩種情況同一行 *pp = np->next 解決——沒有「刪頭」特例。
 */
static int undef(const char *name)
{
    struct nlist **pp = &hashtab[hash(name)];

    while (*pp != NULL) {
        struct nlist *np = *pp;
        if (strcmp(np->name, name) == 0) {
            *pp = np->next;             /* 繞過節點（頭/中間通用） */
            free(np->name);
            free(np->defn);
            free(np);
            return 1;
        }
        pp = &np->next;                 /* 前進到下一個 next 欄位 */
    }
    return 0;                           /* 走完鏈都沒有 */
}

static void show(const char *name)
{
    const struct nlist *np = lookup(name);
    if (np != NULL)
        printf("  %-6s -> %s\n", name, np->defn);
    else
        printf("  %-6s -> (undefined)\n", name);
}

static void ht_free(void)
{
    for (int b = 0; b < HASHSIZE; b++) {
        struct nlist *np = hashtab[b];
        while (np != NULL) {
            struct nlist *next = np->next;
            free(np->name);
            free(np->defn);
            free(np);
            np = next;
        }
        hashtab[b] = NULL;
    }
}

int main(void)
{
    /*
     * 這三個鍵在 HASHSIZE=101 下刻意演示鏈：
     * 同桶與不同桶的删除都會遇到。
     */
    install("alpha", "1");
    install("beta",  "2");
    install("gamma", "3");
    install("delta", "4");

    printf("before undef:\n");
    show("alpha");
    show("beta");
    show("gamma");
    show("delta");

    printf("\nundef(beta)  -> %s\n", undef("beta")  ? "removed" : "absent");
    printf("undef(alpha) -> %s\n", undef("alpha") ? "removed" : "absent");
    printf("undef(nope)  -> %s\n", undef("nope")  ? "removed" : "absent");

    printf("\nafter undef:\n");
    show("alpha");
    show("beta");
    show("gamma");
    show("delta");

    /* 刪掉再重新定義：install 應該把它當新項目 */
    install("beta", "2.0 (redefined)");
    printf("\nafter re-install beta:\n");
    show("beta");

    ht_free();
    return 0;
}

程式碼講解

• struct nlist **pp = &hashtab[hash(name)];——起點是 桶本身的位址；第一輪 *pp 就是鏈頭，命中時改的是桶， 「刪頭特例」自然消失。
• pp = &np->next; 前進的是「格子的位址」不是節點—— 與 insert_sorted 的 pp = &(*pp)->next 一模一樣， 這個模式值得練到閉眼能寫。
• 三次 free（name、defn、節點）一個都不能少：install 配了 三塊，undef 就要收三塊——配置與釋放對稱是記憶體管理的 對帳原則。
• 回傳 1/0 讓呼叫端能區分「刪了」與「本來就沒有」—— 介面誠實原則。
• 易錯處：先 *pp = np->next 之後又用 np->name 比對下一輪 ——本解答的結構（命中即 return）避開了這個順序問題； 若寫成「先找後刪」兩段式，注意找到的節點與 pp 的同步。

範例輸出

before undef:
  alpha  -> 1
  beta   -> 2
  gamma  -> 3
  delta  -> 4

undef(beta)  -> removed
undef(alpha) -> removed
undef(nope)  -> absent

after undef:
  alpha  -> (undefined)
  beta   -> (undefined)
  gamma  -> 3
  delta  -> 4

after re-install beta:
  beta   -> 2.0 (redefined)

---

練習 4：單字頻率統計（難度：進階）

題目

把上一單元（08-trees）的單字計數樹改成雜湊表版本： 統計寫死文本中每個單字的出現次數，然後印出：

1. 雜湊表的自然順序傾印（桶順序——看起來近乎隨機）；
2. 頻率排行榜前 5 名（次數遞減、同次數按字母序—— 把節點指標倒進陣列 qsort）。

比較兩種資料結構在這個問題上的取捨。

解題思路

1. 核心操作 add_word：查找 + 不存在則插入 + 存在則 ++。 雜湊表讓這個操作平均 O(1)（樹是 O(log n)、 未平衡最壞 O(n)）——計數這種「不需要順序」的場景是 雜湊表的主場。
2. 斷詞器：逐字元掃描，isalpha 收集、遇非字母收工； 統一轉小寫（"The" 與 "the" 算同一字）。 (unsigned char) cast 老規矩。
3. 輸出順序的差異就是本題的教學重點： - BST 中序 = 字母序，免費； - 雜湊表傾印 = 桶順序，接近隨機——「hash-order dump」 那行輸出就是證據。
4. 要排序就倒出來：把節點指標收進陣列（不複製字串）， qsort + 多鍵比較（次數遞減、字母序次鍵——複習 函式指標單元練習 4）。
5. 比較函式的細節：元素是 struct wnode *， qsort 給的是「元素的位址」= struct wnode *const *， 要解一層；count 是小的正整數，b->count - a->count 相減安全（遞減）。
6. 選型口訣（單元 README 的複誦）：不需要順序就用 雜湊表；需要排序／範圍查詢才考慮樹。

參考解答

/*
 * ex4_word_freq.c — 練習 4：單字頻率統計（雜湊表版）
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex4_word_freq.c
 * 執行：/tmp/out
 *
 * 上一單元用 BST 做單字計數（輸出天然按字母排序）；
 * 本題改用雜湊表：計數 O(1)，但輸出順序是桶順序（近乎隨機），
 * 想要排序輸出就得倒進陣列 qsort——兩種結構的取捨一目瞭然。
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define HASHSIZE 101
#define MAXWORD  32

struct wnode {
    struct wnode *next;
    char         *word;
    int           count;
};

static struct wnode *hashtab[HASHSIZE];

static char *dup_str(const char *s)
{
    char *p = malloc(strlen(s) + 1);
    if (p != NULL)
        strcpy(p, s);
    return p;
}

static unsigned hash(const char *s)
{
    unsigned hashval;

    for (hashval = 0; *s != '\0'; s++)
        hashval = (unsigned)*s + 31u * hashval;
    return hashval % HASHSIZE;
}

/* 計數 +1（不存在就建立）——單字統計的核心操作 */
static void add_word(const char *w)
{
    unsigned h = hash(w);

    for (struct wnode *np = hashtab[h]; np != NULL; np = np->next) {
        if (strcmp(np->word, w) == 0) {
            np->count++;                /* 已存在：O(鏈長) 找到後 +1 */
            return;
        }
    }
    struct wnode *np = malloc(sizeof *np);
    if (np == NULL || (np->word = dup_str(w)) == NULL) {
        fprintf(stderr, "out of memory\n");
        exit(1);
    }
    np->count = 1;
    np->next = hashtab[h];
    hashtab[h] = np;
}

/* 從字串切出小寫單字餵給 add_word */
static void feed_text(const char *text)
{
    char word[MAXWORD];
    int len = 0;

    for (const char *p = text; ; p++) {
        if (isalpha((unsigned char)*p) && len < MAXWORD - 1) {
            word[len++] = (char)tolower((unsigned char)*p);
        } else if (len > 0) {
            word[len] = '\0';
            add_word(word);
            len = 0;
        }
        if (*p == '\0')
            break;
    }
}

/* 倒進陣列供排序（雜湊表沒有順序，要排序只能倒出來） */
static size_t to_array(struct wnode **arr, size_t cap)
{
    size_t n = 0;

    for (int b = 0; b < HASHSIZE; b++)
        for (struct wnode *np = hashtab[b]; np != NULL; np = np->next)
            if (n < cap)
                arr[n++] = np;
    return n;
}

/* qsort 比較：count 遞減、同次數按字母序（複習多鍵排序） */
static int cmp_freq(const void *pa, const void *pb)
{
    const struct wnode *a = *(struct wnode *const *)pa;
    const struct wnode *b = *(struct wnode *const *)pb;

    if (a->count != b->count)
        return b->count - a->count;     /* count 小、正整數：相減安全 */
    return strcmp(a->word, b->word);
}

static void ht_free(void)
{
    for (int b = 0; b < HASHSIZE; b++) {
        struct wnode *np = hashtab[b];
        while (np != NULL) {
            struct wnode *next = np->next;
            free(np->word);
            free(np);
            np = next;
        }
        hashtab[b] = NULL;
    }
}

int main(void)
{
    /* 寫死的測試文本（重複字樣安排好，排行榜可預期） */
    const char *text =
        "the quick brown fox jumps over the lazy dog "
        "the dog barks and the fox runs away "
        "a quick brown dog meets a lazy fox";

    feed_text(text);

    printf("hash-order dump (bucket order, looks random):\n ");
    struct wnode *arr[64];
    size_t n = to_array(arr, 64);
    for (size_t i = 0; i < n; i++)
        printf(" %s", arr[i]->word);
    printf("\n\n");

    qsort(arr, n, sizeof arr[0], cmp_freq);

    printf("top 5 by frequency (count desc, then alpha):\n");
    for (size_t i = 0; i < 5 && i < n; i++)
        printf("  %2d  %s\n", arr[i]->count, arr[i]->word);

    printf("\ndistinct words: %zu\n", n);
    printf("\nBST version prints alphabetically for free;\n");
    printf("hash version needs an extra sort but counts in O(1).\n");

    ht_free();
    return 0;
}

程式碼講解

• add_word 手寫「查找＋插入」而不是先 lookup 再 install： 一趟探測完成，也順便展示 install/lookup 內部長什麼樣。
• feed_text 的狀態機只有兩個狀態（收集中/間隔中）， 用 len > 0 隱式表達；if (*p == '\0') break; 放在收尾後， 讓最後一個單字不會漏掉。
• to_array 收集的是指標：排序搬動的是 8 位元組的指標 而非整個節點——大結構排序的標準做法。
• 排行榜輸出驗證：the×4、dog×3、fox×3（dog 在 fox 前—— 字母序次鍵生效）、a×2、brown×2。
• 易錯處：qsort 比較函式把 const void * 直接 cast 成 struct wnode *——少解了一層，比較的是垃圾； 「元素是指標時要雙層還原」是 qsort 最常見的坑。

範例輸出

hash-order dump (bucket order, looks random):
  quick lazy away over barks dog runs the and fox jumps meets brown a

top 5 by frequency (count desc, then alpha):
   4  the
   3  dog
   3  fox
   2  a
   2  brown

distinct words: 14

BST version prints alphabetically for free;
hash version needs an extra sort but counts in O(1).

---

練習 5：開放定址與墓碑刪除（難度：挑戰）

題目

實作開放定址（open addressing）＋線性探測的雜湊表 （大小 11 的小表，逼出碰撞），支援 put/get/delete。 刪除必須用墓碑（tombstone）標記，並用實驗證明：

1. 同槽的鍵形成探測鏈（one、dog、sun 都 hash 到 6）；
2. 刪掉探測鏈中間的項目後，鏈尾的項目仍查得到 （若刪除直接清空槽，後面的項目就「丟失」了）；
3. 新插入可以重用墓碑槽。

解題思路

1. 開放定址 vs 鏈結法：項目直接放進表格陣列， 碰撞時「找下一個空位」（線性探測：+1 繞圈）。 沒有每節點的 malloc、cache 友善；代價是刪除變複雜、 載入係數不能太高。
2. 槽的三態是整個設計的核心：

EMPTY     從來沒人用過   —— 查找遇到它：確定不存在，停
USED      有項目
TOMBSTONE 曾有項目被刪   —— 查找穿過它；插入可重用它

3. 為什麼刪除不能設回 EMPTY——畫圖立刻明白：

插入後：  [6]one  [7]dog  [8]sun     （三者都 hash 到 6）
查 sun：  6 不是 -> 7 不是 -> 8 命中

若刪 dog 時把 [7] 設成 EMPTY：
查 sun：  6 不是 -> 7 EMPTY -> 「不存在」？！  sun 丟了！

墓碑：    6 不是 -> 7 墓碑（穿過）-> 8 命中   ✓

EMPTY 是查找的「終止訊號」，探測鏈中間不能出現假訊號。 4. 插入的墓碑重用：探測途中記住第一個墓碑位置； 確認鍵不存在（走到 EMPTY）後，優先放進墓碑槽—— 回收空間、縮短未來的探測距離。 5. 狀態轉移總結：put 在 EMPTY/TOMBSTONE 放入、 get 只認 USED＋鍵相符、delete 把 USED 改 TOMBSTONE。 6. 墓碑的長期代價：刪除頻繁的表會累積墓碑拖慢查找， 實務上定期 rehash 清理（參考本單元 03_rehash.c）。

參考解答

/*
 * ex5_open_addressing.c — 練習 5：開放定址（線性探測）＋墓碑刪除
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex5_open_addressing.c
 * 執行：/tmp/out
 *
 * 與鏈結法不同，開放定址把項目直接放進表格陣列：
 *   插入：從 hash(key) 開始線性探測，找到空槽放入
 *   查找：同樣路線探測，遇到「真空槽」即可宣告不存在
 *   刪除：不能真的清空槽——會切斷後面項目的探測路徑！
 *         改放「墓碑」（tombstone）標記：查找穿過它、插入可重用它
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABSIZE 11          /* 小表，逼出碰撞方便觀察 */

enum slot_state { EMPTY, USED, TOMBSTONE };

struct slot {
    enum slot_state state;
    char            key[16];
    int             value;
};

static struct slot table[TABSIZE];      /* 靜態表：state 初始為 EMPTY(0) */

static unsigned hash(const char *s)
{
    unsigned hashval;

    for (hashval = 0; *s != '\0'; s++)
        hashval = (unsigned)*s + 31u * hashval;
    return hashval % TABSIZE;
}

/*
 * 插入（或更新）。回傳槽索引，-1 表示表滿。
 * 探測時記住「第一個墓碑」：key 確定不存在時優先重用它。
 */
static int oa_put(const char *key, int value)
{
    unsigned h = hash(key);
    int first_tomb = -1;

    for (unsigned i = 0; i < TABSIZE; i++) {
        unsigned idx = (h + i) % TABSIZE;       /* 線性探測：+1 繞圈 */
        struct slot *s = &table[idx];

        if (s->state == USED) {
            if (strcmp(s->key, key) == 0) {
                s->value = value;               /* 已存在：更新 */
                return (int)idx;
            }
        } else if (s->state == TOMBSTONE) {
            if (first_tomb < 0)
                first_tomb = (int)idx;          /* 記住可重用的位置 */
        } else {                                /* EMPTY：確定不存在 */
            int idx2 = first_tomb >= 0 ? first_tomb : (int)idx;
            table[idx2].state = USED;
            strncpy(table[idx2].key, key, sizeof table[idx2].key - 1);
            table[idx2].key[sizeof table[idx2].key - 1] = '\0';
            table[idx2].value = value;
            return idx2;
        }
    }
    if (first_tomb >= 0) {                      /* 全是 USED/墓碑 */
        table[first_tomb].state = USED;
        strncpy(table[first_tomb].key, key,
                sizeof table[first_tomb].key - 1);
        table[first_tomb].key[sizeof table[first_tomb].key - 1] = '\0';
        table[first_tomb].value = value;
        return first_tomb;
    }
    return -1;                                  /* 真的滿了 */
}

/* 查找：回傳槽索引，-1 表示不存在 */
static int oa_get(const char *key)
{
    unsigned h = hash(key);

    for (unsigned i = 0; i < TABSIZE; i++) {
        unsigned idx = (h + i) % TABSIZE;
        struct slot *s = &table[idx];

        if (s->state == EMPTY)
            return -1;              /* 真空槽：路徑到此為止 */
        if (s->state == USED && strcmp(s->key, key) == 0)
            return (int)idx;
        /* USED 不符或 TOMBSTONE：穿過去，繼續探測 */
    }
    return -1;
}

/* 刪除：放墓碑，不清空 */
static int oa_del(const char *key)
{
    int idx = oa_get(key);
    if (idx < 0)
        return 0;
    table[idx].state = TOMBSTONE;   /* 保持探測路徑連續 */
    return 1;
}

static void dump(const char *msg)
{
    printf("%s\n", msg);
    for (int i = 0; i < TABSIZE; i++) {
        switch (table[i].state) {
        case USED:
            printf("    [%2d] %-8s = %d\n", i, table[i].key,
                   table[i].value);
            break;
        case TOMBSTONE:
            printf("    [%2d] +tombstone+\n", i);
            break;
        default:
            printf("    [%2d] (empty)\n", i);
        }
    }
}

int main(void)
{
    /*
     * "one"、"dog"、"sun" 在 TABSIZE=11 的 K&R hash 下同槽
     * （都 hash 到 6），形成探測鏈 6 -> 7 -> 8；
     * 刪掉鏈中間的 "dog" 觀察墓碑的必要性。
     */
    printf("insert five keys ('one','dog','sun' all hash to 6):\n");
    printf("  one  -> slot %d\n", oa_put("one", 1));
    printf("  dog  -> slot %d (collision, probes to next)\n",
           oa_put("dog", 2));
    printf("  sun  -> slot %d (collision, probes further)\n",
           oa_put("sun", 3));
    printf("  ten  -> slot %d\n", oa_put("ten", 10));
    printf("  four -> slot %d\n", oa_put("four", 4));
    dump("\ntable:");

    printf("\nlookup walks the probe chain:\n");
    printf("  get(one) -> slot %d\n", oa_get("one"));
    printf("  get(sun) -> slot %d (walked past 'one' and 'dog')\n",
           oa_get("sun"));

    printf("\ndelete 'dog' -- the slot in the middle of the chain:\n");
    oa_del("dog");
    dump("table now has a tombstone:");

    printf("\n'sun' must still be findable (probe walks through the\n"
           "tombstone). if delete had set EMPTY, this would fail:\n");
    printf("  get(sun) -> slot %d %s\n", oa_get("sun"),
           oa_get("sun") >= 0 ? "(ok)" : "(LOST!)");

    printf("\nnew insert 'mat' (also hashes to 6) reuses the tombstone:\n");
    printf("  put(mat) -> slot %d\n", oa_put("mat", 5));
    dump("final table:");

    printf("\nmemory note: open addressing = one flat array, no\n"
           "per-node malloc; chaining allocates a node per entry.\n");
    return 0;
}

程式碼講解

• enum slot_state 三態 + 靜態陣列：EMPTY 恰好是 0， 靜態初始化免費完成。
• oa_put 的探測迴圈同時做三件事：找同鍵（更新）、 記第一個墓碑（重用）、找 EMPTY（確定不存在）—— 一趟完成，注意「確定不存在」之前不能急著放進墓碑 （後面可能還有同鍵的 USED 槽）。
• (h + i) % TABSIZE：線性探測的繞圈寫法；i 掃滿一圈 仍沒 EMPTY 就看有無墓碑可用，再沒有才回報表滿。
• 實驗輸出的三幕劇：碰撞鏈形成（6→7→8）、墓碑保住 sun （get(sun) -> slot 8 (ok)）、mat 重用墓碑槽 7—— 每一幕都對應解題思路的一條論證。
• 易錯處一：get 遇到 TOMBSTONE 就停——鏈被腰斬， 與「刪除設 EMPTY」同病。
• 易錯處二：put 看到第一個墓碑就立刻放入——若同鍵在 更後面的槽，表裡會出現重複鍵；必須走到 EMPTY 確認後 才回頭用墓碑。

範例輸出

insert five keys ('one','dog','sun' all hash to 6):
  one  -> slot 6
  dog  -> slot 7 (collision, probes to next)
  sun  -> slot 8 (collision, probes further)
  ten  -> slot 9
  four -> slot 3

table:
    [ 0] (empty)
    [ 1] (empty)
    [ 2] (empty)
    [ 3] four     = 4
    [ 4] (empty)
    [ 5] (empty)
    [ 6] one      = 1
    [ 7] dog      = 2
    [ 8] sun      = 3
    [ 9] ten      = 10
    [10] (empty)

lookup walks the probe chain:
  get(one) -> slot 6
  get(sun) -> slot 8 (walked past 'one' and 'dog')

delete 'dog' -- the slot in the middle of the chain:
table now has a tombstone:
    [ 0] (empty)
    [ 1] (empty)
    [ 2] (empty)
    [ 3] four     = 4
    [ 4] (empty)
    [ 5] (empty)
    [ 6] one      = 1
    [ 7] +tombstone+
    [ 8] sun      = 3
    [ 9] ten      = 10
    [10] (empty)

'sun' must still be findable (probe walks through the
tombstone). if delete had set EMPTY, this would fail:
  get(sun) -> slot 8 (ok)

new insert 'mat' (also hashes to 6) reuses the tombstone:
  put(mat) -> slot 7
final table:
    [ 0] (empty)
    [ 1] (empty)
    [ 2] (empty)
    [ 3] four     = 4
    [ 4] (empty)
    [ 5] (empty)
    [ 6] one      = 1
    [ 7] mat      = 5
    [ 8] sun      = 3
    [ 9] ten      = 10
    [10] (empty)

memory note: open addressing = one flat array, no
per-node malloc; chaining allocates a node per entry.

---

常見錯誤解法對照

錯誤寫法	症狀	正解
hash 累加器用有號 int	溢位 UB、分布怪異	unsigned（練習 1）
foreach 回呼裡刪除目前項目	use-after-free	刪除用 undef 的 pp 寫法（練習 2、3）
undef 用 prev/cur 加刪頭特例	兩條路徑、雙倍 bug 面積	指標的指標（練習 3）
qsort 比較函式少解一層指標	排序結果亂	元素是指標時雙層還原（練習 4）
開放定址刪除設 EMPTY	探測鏈斷裂、項目丟失	墓碑標記（練習 5）
put 見墓碑立刻放入	同鍵重複出現	先走到 EMPTY 確認再重用（練習 5）