BKDRHash 字串雜湊算法 C 語言完整實作：雜湊表、鏈地址法與增刪改查

BKDRHash 算法

簡單高效的字串雜湊函數，種子質數常用 131、1313、13131、131313 等。

unsigned int BKDRHash(const char *key, size_t tableSize) {
    unsigned int seed = 131;
    unsigned int hash = 0;
    while (*key) {
        hash = hash * seed + (*key++);
    }
    return hash % tableSize;
}

雜湊表資料結構 (鏈地址法)

#define STRLEN 15
#define DICLEN 100000

typedef struct Node {
    char data[STRLEN];
    struct Node *next;
} Node;

typedef struct {
    Node *buckets[DICLEN]; // 每個桶為鏈表頭指標
} HashTable;

HashTable *createHash() {
    HashTable *ht = calloc(1, sizeof(HashTable));
    return ht; // calloc 自動歸零所有桶指標
}

Node *createNode(const char *str) {
    Node *n = malloc(sizeof(Node));
    strncpy(n->data, str, STRLEN-1);
    n->data[STRLEN-1] = '\0';
    n->next = NULL;
    return n;
}

核心操作實作

插入

bool insert(HashTable *ht, const char *str) {
    unsigned int idx = BKDRHash(str, DICLEN);
    Node *n = createNode(str);
    n->next = ht->buckets[idx];
    ht->buckets[idx] = n; // 頭插法 O(1)
    return true;
}

查找

Node *find(HashTable *ht, const char *str) {
    unsigned int idx = BKDRHash(str, DICLEN);
    for (Node *p = ht->buckets[idx]; p; p = p->next)
        if (strcmp(p->data, str) == 0) return p;
    return NULL;
}

刪除

bool erase(HashTable *ht, const char *str) {
    unsigned int idx = BKDRHash(str, DICLEN);
    Node **pp = &ht->buckets[idx];
    while (*pp) {
        if (strcmp((*pp)->data, str) == 0) {
            Node *tmp = *pp;
            *pp = (*pp)->next;
            free(tmp);
            return true;
        }
        pp = &(*pp)->next;
    }
    return false;
}

修改 (刪除舊 + 插入新)

bool modify(HashTable *ht, const char *oldStr, const char *newStr) {
    if (strcmp(oldStr, newStr) == 0) return true;
    return erase(ht, oldStr) && insert(ht, newStr);
}

效能與調優建議

1. 負載因子：元素數/桶數。超過 0.75 觸發擴容 (重新雜湊)。
2. 種子選擇：131 為經驗值，可嘗試 1313、13131 測試衝突率。
3. 桶數為質數：減少模運算模式導致的聚集，或使用 2 的冪次配合位元運算 (需優質雜湊分佈)。
4. 字串長度固定：本範例固定 STRLEN，實際專案可用柔性陣列或動態分配。
5. 現代替代：C++ std::unordered_map、C 語言 khash、uthash 等成熟庫。

完整測試主程式

int main() {
    HashTable *ht = createHash();
    insert(ht, "hello");
    insert(ht, "world");
    insert(ht, "hello"); // 允許重複鍵 (多節點)

    Node *n = find(ht, "world");
    if (n) printf("Found: %s\n", n->data);

    erase(ht, "hello");
    modify(ht, "world", "earth");

    // 釋放所有節點 (略)
    return 0;
}

總結

BKDRHash + 鏈地址法是教學與中小規模工程的經典組合，代碼簡潔、無需複雜遷移邏輯、自然支援動態增減。生產環境高併發/大數據場景建議採用無鎖雜湊表、Cuckoo Hashing 或成熟庫。