摘要：本文將說明如何使用 C 語言實作一個簡單的雜湊表資料結構。我會先簡要示範線性搜尋與二元搜尋，接著設計並實作雜湊表。我的目標是讓大家看到，雜湊表的內部原理並不可怕——在一定的限制條件下，從頭開始打造其實相當容易。

前陣子我寫了一篇比較各種語言的文章，比較了一個計算字詞頻率的簡單程式，其中提到的一點是，C 語言的標準函式庫並沒有提供雜湊表這種資料結構。

發現這點之後，你有很多選擇：使用線性搜尋、使用二元搜尋、直接拿別人的雜湊表實作來用，或是自己寫一個雜湊表。或者，乾脆換成機能更豐富的語言。接下來我們會快速看一下線性搜尋與二元搜尋，然後學習如何自己動手寫一個雜湊表。這在 C 語言中經常是必要的，但即使你用的是其他語言，如果需要客製化的雜湊表，這也同樣有用。

線性搜尋

最簡單的做法，就是用線性搜尋來逐一掃描陣列。如果項目不多，這其實不算糟的策略——在我的簡單比較中，以字串測試為例，項目數在 7 個以內時，線性搜尋甚至比雜湊表查找還快（不過除非你的程式對效能非常敏感，否則用到 20 或 30 個項目大概也還可以接受）。線性搜尋還讓你可以直接把新項目加到陣列尾端。這種搜尋方式平均需要比較 num_keys/2 個項目。

假設你要在以下陣列中搜尋鍵 bob（每個項目都是一個字串鍵搭配一個整數值）：

你只要從頭開始（索引 0 的 foo）逐一比較每個鍵。如果鍵符合你要找的，就完成了；如果不符合，就移到下一個位置。搜尋 bob 需要五個步驟（索引 0 到 4）。

以下是在 C 語言中的演算法（假設陣列中每個項目都是一個字串鍵與整數值）：

typedef struct {
    char* key;
    int value;
} item;

item* linear_search(item* items, size_t size, const char* key) {
    for (size_t i=0; i<size; i++) {
        if (strcmp(items[i].key, key) == 0) {
            return &items[i];
        }
    }
    return NULL;
}

int main(void) {
    item items[] = {
        {"foo", 10}, {"bar", 42}, {"bazz", 36}, {"buzz", 7},
        {"bob", 11}, {"jane", 100}, {"x", 200}};
    size_t num_items = sizeof(items) / sizeof(item);

    item* found = linear_search(items, num_items, "bob");
    if (!found) {
        return 1;
    }
    printf("linear_search: value of 'bob' is %d\n", found->value);
    return 0;
}

二元搜尋

另一種簡單的做法，是把項目放進一個依鍵排序好的陣列中，然後使用二元搜尋來減少比較次數。這有點像我們在（紙本）字典中查東西的方式。

C 語言的標準函式庫甚至就有 bsearch 函式。即使有數百個項目，二元搜尋的速度也還算不錯（雖然還是不及雜湊表），因為平均只需要比較 log(num_keys) 個項目。不過，由於陣列必須保持排序狀態，插入新項目時就得把後面的資料往後搬移，所以插入平均仍需要 num_keys/2 次操作。

假設我們再次查找 bob（在這個已事先排序好的陣列中）：

使用二元搜尋時，我們從中間開始（buzz），如果該位置的鍵比我們要找的大，就對下半部重複同樣的過程；如果比較大，就對上半部重複。在這個例子中，總共需要三個步驟，依序是索引 3、1、2，然後就找到了。這是 3 步而非 5 步，而且項目越多，相較於線性搜尋的改善就（指數級地）越明顯。

以下是用 C 語言的做法（分別展示有使用與未使用 bsearch 的版本）。item 結構的定義與前面相同。

int cmp(const void* a, const void* b) {
    item* item_a = (item*)a;
    item* item_b = (item*)b;
    return strcmp(item_a->key, item_b->key);
}

item* binary_search(item* items, size_t size, const char* key) {
    if (size + size < size) {
        return NULL; // size too big; avoid overflow
    }
    size_t low = 0;
    size_t high = size;
    while (low < high) {
        size_t mid = (low + high) / 2;
        int c = strcmp(items[mid].key, key);
        if (c == 0) {
            return &items[mid];
        }
        if (c < 0) {
            low = mid + 1; // eliminate low half of array
        } else {
            high = mid;    // eliminate high half of array
        }
    }
    // Entire array has been eliminated, key not found.
    return NULL;
}

int main(void) {
    item items[] = {
        {"bar", 42}, {"bazz", 36}, {"bob", 11}, {"buzz", 7},
        {"foo", 10}, {"jane", 100}, {"x", 200}};
    size_t num_items = sizeof(items) / sizeof(item);

    item key = {"bob", 0};
    item* found = bsearch(&key, items, num_items, sizeof(item), cmp);
    if (found == NULL) {
        return 1;
    }
    printf("bsearch: value of 'bob' is %d\n", found->value);

    found = binary_search(items, num_items, "bob");
    if (found == NULL) {
        return 1;
    }
    printf("binary_search: value of 'bob' is %d\n", found->value);
    return 0;
}

附註：在 binary_search 中，若要完整支援 size_t 的範圍，更好的做法是避免一開始的「半數大小溢位檢查」，而將 mid 的計算改為 low + (high-low)/2。不過為了教學目的，我就讓程式碼維持原樣——加上最初的溢位檢查後，我認為並沒有 bug，只是只能用到 size_t 範圍的一半，不太理想。反正在我的 64 位元系統上，我也不會去搜尋一個 16 exabyte 的陣列！想進一步了解，可參考這篇文章Nearly All Binary Searches and Mergesorts are Broken。感謝 Seth Arnold 與 Olaf Seibert 的回饋。

雜湊表

雜湊表看起來可能有點嚇人：種類繁多，還有各式各樣的最佳化手法。不過，只要搭配一個簡單的雜湊函式，再加上所謂的「線性探測」，就能相當輕鬆地做出一個堪用的雜湊表。

如果你還不太清楚雜湊表的運作原理，這裡快速複習一下。雜湊表是一種容器資料結構，讓你能透過鍵（通常是字串）快速找到對應的值（任何資料型別）。在底層，它們其實就是用鍵的雜湊函式來當索引的陣列。

雜湊函式會把一個鍵轉成看起來隨機的數字，而且同一個鍵每次都必須回傳相同的數字。舉例來說，使用我們接下來要用的雜湊函式（64 位元 FNV-1a），上述這些鍵的雜湊值如下：

我之所以列出雜湊值 mod 16，是因為我們會從一個 16 個元素的陣列開始，所以必須把雜湊值限制在陣列大小的範圍內——modulo 運算就是除以 16 後取餘數，讓陣列索引落在 0 到 15 之間。

當我們把一個值插入雜湊表時，會先計算它的雜湊值，對 16 取餘數，然後以此作為陣列索引。所以在大小為 16 的陣列中，我們會把 bar 插入索引 10、bazz 插入 8、bob 插入 4，依此類推。接下來讓我們把所有項目都插入雜湊表陣列中（除了 x——稍後再談）：

要查找一個值，只要取出 array[hash(key) % 16] 即可。如果陣列大小是 2 的次方，也可以用 array[hash(key) & 15]。注意，此時元素的順序已經沒有意義了。

但如果兩個鍵雜湊後得到相同的值（取 mod 16 之後）呢？依據雜湊函式與陣列大小的不同，這其實相當常見。舉例來說，當我們嘗試把 x 加入上面的陣列時，它的雜湊值 mod 16 是 7，但索引 7 已經有 foo 了，於是就發生了碰撞。

處理碰撞有各種方法。傳統上，你會建立一個固定大小的雜湊陣列，如果發生碰撞，就用鏈結串列來存放雜湊到同一個索引的值。然而，鏈結串列通常在新增項目時需要額外的記憶體配置，而且遍歷時得沿著散落在記憶體各處的指標去追，這在現代 CPU 上相對較慢。

一種更簡單也更快處理碰撞的方法是線性探測：如果我們要插入一個項目卻發現該位置已被佔用，就直接移到下一個位置。如果下一個位置也是滿的，就繼續往下找，直到找到空位為止；若走到陣列尾端，就繞回開頭。（除了移到下一個位置之外，還有其他探測方式，但已超出本文範圍。）這種技巧比鏈結串列快得多，因為你的 CPU 快取很可能已經把接下來的項目預先載入了。

以下是加入「發生碰撞」的 x（值為 200）之後，雜湊表陣列的樣子。我們先嘗試索引 7，但那裡已經放了 foo，所以移到索引 8，但那裡放著 bazz，於是再移到索引 9，而那裡是空的，所以就插在那裡：

當雜湊表變得太滿時，我們需要配置一個更大的陣列並把項目搬過去。當雜湊表中的項目數達到陣列大小時，這絕對是必要的，但通常你會在表格半滿或四分之三滿時就先做。如果太晚才擴容，碰撞會越來越頻繁，查找與插入也會越來越慢。如果等到幾乎全滿才擴容，基本上就又退回線性搜尋了。

搭配一個好的雜湊函式，這種雜湊表平均每次查找只需要一次操作，再加上計算鍵的雜湊所需的時間（不過鍵通常是相當短的字串）。

就是這樣！這方面還有很多可以深入的地方，本文只是點到為止。我不打算對 Big O 表示法、最佳陣列大小、不同種類的探測方式等做學術性的分析。如果想要那種程度的細節，請去讀 Donald Knuth 的 TAOCP！

雜湊表實作

你可以在 GitHub 上的 benhoyt/ht 儲存庫中找到這個實作的程式碼，分別在 ht.h 與 ht.c。僅供參考，所有程式碼皆以寬鬆的 MIT 授權釋出。

我從 Code Review Stack Exchange 上得到了一些很好的回饋，幫我修掉了幾個棘手的問題，其中最主要的是在 ht_expand 步驟中呼叫 strdup 的方式所導致的記憶體洩漏（已在此修復）。我用 Valgrind 確認了這個洩漏——早該跑一下的。Seth Arnold 也針對本文的草稿提供了實用的回饋。感謝大家！

API 設計

首先來想想我們想要什麼樣的 API：我們需要能建立與銷毀雜湊表、依鍵取得值、依鍵設定值、取得項目數量，以及遍歷所有項目。我並非追求最高效能的 API，而是想做一個相對簡單、容易實作的版本。

經過幾次調整後，我定案了以下這些函式與結構（參見 ht.h）：

// Hash table structure: create with ht_create, free with ht_destroy.
typedef struct ht ht;

// Create hash table and return pointer to it, or NULL if out of memory.
ht* ht_create(void);

// Free memory allocated for hash table, including allocated keys.
void ht_destroy(ht* table);

// Get item with given key (NUL-terminated) from hash table. Return
// value (which was set with ht_set), or NULL if key not found.
void* ht_get(ht* table, const char* key);

// Set item with given key (NUL-terminated) to value (which must not
// be NULL). If not already present in table, key is copied to newly
// allocated memory (keys are freed automatically when ht_destroy is
// called). Return address of copied key, or NULL if out of memory.
const char* ht_set(ht* table, const char* key, void* value);

// Return number of items in hash table.
size_t ht_length(ht* table);

// Hash table iterator: create with ht_iterator, iterate with ht_next.
typedef struct {
    const char* key;  // current key
    void* value;      // current value

    // Don't use these fields directly.
    ht* _table;       // reference to hash table being iterated
    size_t _index;    // current index into ht._entries
} hti;

// Return new hash table iterator (for use with ht_next).
hti ht_iterator(ht* table);

// Move iterator to next item in hash table, update iterator's key
// and value to current item, and return true. If there are no more
// items, return false. Don't call ht_set during iteration.
bool ht_next(hti* it);

關於這個 API 設計，有幾點要說明：

• 為了簡單起見，我們使用 C 風格的 NUL 結尾字串。我知道有更有效率的字串處理方式，但這與 C 標準函式庫的風格一致。
• ht_set 函式會配置並複製鍵（如果是第一次插入）。通常你不會希望呼叫端還得煩惱這件事，或確保鍵的記憶體一直存在。注意，ht_set 會回傳指向複製後鍵的指標，這主要是用來作為「記憶體不足」錯誤的信號——失敗時會回傳 NULL。
• 不過，ht_set 並不會複製值。呼叫端必須自行確保值指標在雜湊表的生命週期內保持有效。
• 值不能是 NULL。這讓 ht_get 的簽章稍微單純一些，因為你不必區分 NULL 值與根本未設定的情況。
• ht_length 函式並非絕對必要，因為你也可以透過遍歷表格來算出長度。不過那有點麻煩（而且慢），所以有 ht_length 還是很方便。
• 迭代有很多種做法。使用明確的迭代器型別搭配 while 迴圈，在 C 語言中看起來簡單又自然（見下方範例）。ht_iterator 回傳的是一個值而非指標，這是為了效率，也讓呼叫端不必另外釋放記憶體。
• 沒有提供 ht_remove 來從雜湊表中移除項目。使用線性探測時，移除是比較棘手的一件事（因為會留下「空洞」），但我平常使用雜湊表時不太需要刪除功能，所以就把這部分當作給讀者的練習。

範例程式

下方是一個簡單的程式（demo.c），示範了 API 中所有函式的用法。它會從標準輸入讀取以空白分隔的單字，統計每個不重複單字的出現次數，並印出結果（順序是任意的，因為我們雜湊表的迭代順序未定義）。最後會印出不重複單字的總數。

// Example:
// $ echo 'foo bar the bar bar bar the' | ./demo
// foo 1
// bar 4
// the 2
// 3

void exit_nomem(void) {
    fprintf(stderr, "out of memory\n");
    exit(1);
}

int main(void) {
    ht* counts = ht_create();
    if (counts == NULL) {
        exit_nomem();
    }

    // Read next word from stdin (at most 100 chars long).
    char word[101];
    while (scanf("%100s", word) != EOF) {
        // Look up word.
        void* value = ht_get(counts, word);
        if (value != NULL) {
            // Already exists, increment int that value points to.
            int* pcount = (int*)value;
            (*pcount)++;
            continue;
        }

        // Word not found, allocate space for new int and set to 1.
        int* pcount = malloc(sizeof(int));
        if (pcount == NULL) {
            exit_nomem();
        }
        *pcount = 1;
        if (ht_set(counts, word, pcount) == NULL) {
            exit_nomem();
        }
    }

    // Print out words and frequencies, freeing values as we go.
    hti it = ht_iterator(counts);
    while (ht_next(&it)) {
        printf("%s %d\n", it.key, *(int*)it.value);
        free(it.value);
    }

    // Show the number of unique words.
    printf("%d\n", (int)ht_length(counts));

    ht_destroy(counts);
    return 0;
}

接下來，讓我們來看看雜湊表的實作（ht.c）。

建立與銷毀

配置一個新的雜湊表相當直觀。我們從初始陣列容量 16 開始（存放在 capacity 中），代表在擴容前最多可容納 8 個項目。這裡有兩次配置，一次是給雜湊表結構本身，一次是給 entries 陣列。注意，我們對 entries 陣列使用 calloc，以確保一開始所有鍵都是 NULL，也就是所有位置都是空的。

ht_destroy 函式會釋放這些記憶體，同時也會釋放過程中為複製鍵所配置的記憶體（下方會再詳述）。

// Hash table entry (slot may be filled or empty).
typedef struct {
    const char* key;  // key is NULL if this slot is empty
    void* value;
} ht_entry;

// Hash table structure: create with ht_create, free with ht_destroy.
struct ht {
    ht_entry* entries;  // hash slots
    size_t capacity;    // size of _entries array
    size_t length;      // number of items in hash table
};

#define INITIAL_CAPACITY 16  // must not be zero

ht* ht_create(void) {
    // Allocate space for hash table struct.
    ht* table = malloc(sizeof(ht));
    if (table == NULL) {
        return NULL;
    }
    table->length = 0;
    table->capacity = INITIAL_CAPACITY;

    // Allocate (zero'd) space for entry buckets.
    table->entries = calloc(table->capacity, sizeof(ht_entry));
    if (table->entries == NULL) {
        free(table); // error, free table before we return!
        return NULL;
    }
    return table;
}

void ht_destroy(ht* table) {
    // First free allocated keys.
    for (size_t i = 0; i < table->capacity; i++) {
        free((void*)table->entries[i].key);
    }

    // Then free entries array and table itself.
    free(table->entries);
    free(table);
}

雜湊函式

接下來我們來定義雜湊函式，這是 FNV-1a 雜湊演算法簡單直接的 C 語言實作。請注意，FNV 並非隨機化或加密用的雜湊函式，因此攻擊者有可能刻意製造大量碰撞的鍵，導致查找速度大幅變慢——Python 也就是因為這個原因才捨棄 FNV。不過就我們的使用情境來說，FNV 簡單又快速。

就演算法本身而言，FNV-1a 只是用一個「偏移」常數作為雜湊的起始值，然後對字串中的每個位元組，先將雜湊值與該位元組做 XOR，再乘上一個很大的質數。這個偏移量與質數都是由擁有博士學位的人精心挑選出來的。

我們使用的是 64 位元版本，因為，嗯，現在大多數電腦都是 64 位元，這似乎是個不錯的主意。看得出來我可沒有那種博士學位。:-) 不過認真說來，考慮到雜湊表可能會非常大，用 64 位元似乎比 32 位元更好。

#define FNV_OFFSET 14695981039346656037UL
#define FNV_PRIME 1099511628211UL

// Return 64-bit FNV-1a hash for key (NUL-terminated). See description:
// https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
static uint64_t hash_key(const char* key) {
    uint64_t hash = FNV_OFFSET;
    for (const char* p = key; *p; p++) {
        hash ^= (uint64_t)(unsigned char)(*p);
        hash *= FNV_PRIME;
    }
    return hash;
}

這裡我不會做詳細的分析，不過我附了一個小型的統計程式，會印出由輸入中不重複單字所建立的雜湊表的平均探測長度。我們使用的 FNV-1a 雜湊演算法在一份五十萬個英文單字的清單上表現不錯（平均探測長度 1.40），在五十萬個非常相似的鍵如 word1、word2 等組成的清單上也表現良好（平均探測長度 1.38）。

有趣的是，當我嘗試 FNV-1 演算法（與 FNV-1a 類似，只是先做乘法再做 XOR）時，英文單字的平均探測長度仍為 1.43，但相似鍵的表現就非常糟——平均探測長度高達 5.02。所以在我的快速測試中，FNV-1a 明顯勝出。

取得

接下來看看 ht_get 函式。首先它會計算雜湊值，並對 capacity（entries 陣列的大小）取餘數，這是透過與 capacity - 1 做 AND 運算來完成的。只有在陣列大小恆為 2 的次方時，才能使用 AND，而為了簡單起見，如下方所見，我們確實會確保這一點。

接著我們會循環直到找到一個空位置，若遇到空位就代表沒找到該鍵。對於每個非空的位置，我們用 strcmp 來檢查該位置的鍵是否就是我們要找的（除非曾發生碰撞，否則通常會在第一個位置就找到）。如果不是，就往下一個位置移動。

void* ht_get(ht* table, const char* key) {
    // AND hash with capacity-1 to ensure it's within entries array.
    uint64_t hash = hash_key(key);
    size_t index = (size_t)(hash & (uint64_t)(table->capacity - 1));

    // Loop till we find an empty entry.
    while (table->entries[index].key != NULL) {
        if (strcmp(key, table->entries[index].key) == 0) {
            // Found key, return value.
            return table->entries[index].value;
        }
        // Key wasn't in this slot, move to next (linear probing).
        index++;
        if (index >= table->capacity) {
            // At end of entries array, wrap around.
            index = 0;
        }
    }
    return NULL;
}

設定

ht_set 函式稍微複雜一些，因為當元素太多時，它必須擴充表格。在我們的實作中，只要表格半滿就將容量加倍。這有點浪費記憶體，但能讓實作保持非常簡單。

首先是 ht_set 函式。它只是在必要時擴充表格，然後插入項目：

const char* ht_set(ht* table, const char* key, void* value) {
    assert(value != NULL);
    if (value == NULL) {
        return NULL;
    }

    // If length will exceed half of current capacity, expand it.
    if (table->length >= table->capacity / 2) {
        if (!ht_expand(table)) {
            return NULL;
        }
    }

    // Set entry and update length.
    return ht_set_entry(table->entries, table->capacity, key, value,
                        &table->length);
}

實際的核心操作在 ht_set_entry 這個輔助函式中（注意其中的迴圈與 ht_get 中的非常相似）。如果 plength 參數不是 NULL，表示它是被 ht_set 呼叫的，因此我們會配置並複製鍵，然後更新長度：

// Internal function to set an entry (without expanding table).
static const char* ht_set_entry(ht_entry* entries, size_t capacity,
        const char* key, void* value, size_t* plength) {
    // AND hash with capacity-1 to ensure it's within entries array.
    uint64_t hash = hash_key(key);
    size_t index = (size_t)(hash & (uint64_t)(capacity - 1));

    // Loop till we find an empty entry.
    while (entries[index].key != NULL) {
        if (strcmp(key, entries[index].key) == 0) {
            // Found key (it already exists), update value.
            entries[index].value = value;
            return entries[index].key;
        }
        // Key wasn't in this slot, move to next (linear probing).
        index++;
        if (index >= capacity) {
            // At end of entries array, wrap around.
            index = 0;
        }
    }

    // Didn't find key, allocate+copy if needed, then insert it.
    if (plength != NULL) {
        key = strdup(key);
        if (key == NULL) {
            return NULL;
        }
        (*plength)++;
    }
    entries[index].key = (char*)key;
    entries[index].value = value;
    return key;
}

那 ht_expand 這個輔助函式呢？它會配置一個容量為目前兩倍的新 entries 陣列，並使用 plength 為 NULL 的 ht_set_entry 來把項目複製過去。雖然雜湊值相同，但由於 capacity 改變了（索引是雜湊值對 capacity 取餘數），索引位置會有所不同。

// Expand hash table to twice its current size. Return true on success,
// false if out of memory.
static bool ht_expand(ht* table) {
    // Allocate new entries array.
    size_t new_capacity = table->capacity * 2;
    if (new_capacity < table->capacity) {
        return false;  // overflow (capacity would be too big)
    }
    ht_entry* new_entries = calloc(new_capacity, sizeof(ht_entry));
    if (new_entries == NULL) {
        return false;
    }

    // Iterate entries, move all non-empty ones to new table's entries.
    for (size_t i = 0; i < table->capacity; i++) {
        ht_entry entry = table->entries[i];
        if (entry.key != NULL) {
            ht_set_entry(new_entries, new_capacity, entry.key,
                         entry.value, NULL);
        }
    }

    // Free old entries array and update this table's details.
    free(table->entries);
    table->entries = new_entries;
    table->capacity = new_capacity;
    return true;
}

長度與迭代

ht_length 函式非常簡單——我們會在過程中持續更新 _length 中的項目數，所以只要回傳它即可：

size_t ht_length(ht* table) {
    return table->length;
}

迭代是最後一塊拼圖。要建立迭代器，使用者會呼叫 ht_iterator，而要移到下一個項目，則在迴圈中呼叫 ht_next，直到它回傳 true 為止。它們的定義如下：

hti ht_iterator(ht* table) {
    hti it;
    it._table = table;
    it._index = 0;
    return it;
}

bool ht_next(hti* it) {
    // Loop till we've hit end of entries array.
    ht* table = it->_table;
    while (it->_index < table->capacity) {
        size_t i = it->_index;
        it->_index++;
        if (table->entries[i].key != NULL) {
            // Found next non-empty item, update iterator key and value.
            ht_entry entry = table->entries[i];
            it->key = entry.key;
            it->value = entry.value;
            return true;
        }
    }
    return false;
}

討論

就是這樣——在 ht.c 中的實作只有大約 200 行程式碼，包含空行與註解在內。

注意：這是一個教學工具，而非函式庫，所以我鼓勵你動手玩玩看，並告訴我任何你發現、我還沒找到的 bug！我不建議在沒有經過大量進一步測試、檢查邊界情況等之前就直接使用它。別忘了，我們面對的是不安全的 C 語言。甚至在寫這篇文章的過程中，我才發現自己曾用 malloc 而非 calloc 來配置 entries 陣列，這意味著鍵可能沒有被初始化為 NULL。

如前所述，我希望保持實作的簡單，並沒有太擔心效能。不過，與 Go 的 map 實作做了一個快速、非嚴謹的效能比較後，結果顯示表現相當不錯——在五十萬個英文單字的測試中，這個 C 版本在查找上慢了約 50%，但在插入上快了約 40%。

說到 Go，在 Go 這類語言中要寫出客製化的雜湊表甚至更簡單，因為你不必擔心處理記憶體配置錯誤或釋放已配置的記憶體。我最近在 Go 中寫了一個 counter 套件，實作了類似的雜湊表。

對於 C 版本，顯然還有許多可以發揮的空間。你可以透過各種測試來著重於安全性與可靠性。你也可以專注於效能，減少記憶體配置、使用「bump allocator」來處理複製的鍵、將短鍵直接存放在每個項目結構內等等。你也可以改善記憶體使用率，調整 _ht_expand 讓它不要每次都加倍。或者，你也可以加入像是移除項目這類功能。

寫完這篇文章後，我才想起 Bob Nystrom 的優秀著作 Crafting Interpreters 中有一個關於雜湊表的章節。他的設計選擇與本文有些相似，不過他的章節比本文深入得多。如果我在動筆前就想起他的章節，大概就不會寫這一篇了！

無論如何，希望你覺得這篇文章有用或有趣。如果你發現任何 bug 或有任何回饋，歡迎告訴我。你也可以前往 Hacker News、programming Reddit 與 Lobsters 上的討論串。