您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> C 語言入門

經典算法學習：哈希查找（散列表）原理、六大構造函數、四種沖突解決法與 C 完整實現

編輯：C 語言入門

哈希查找（Hash Search）通過哈希函數將關鍵字直接映射為存儲地址，實現平均 O(1) 查找。本文系統講解六種哈希函數構造方法、四大沖突解決策略，並提供基於開放定址法（線性探測）的 C 語言完整實現。

一、六種哈希函數構造方法

方法	公式/思想	適用場景	優/缺點
1. 直接定址法	H(key) = a·key + b	關鍵字連續、範圍小、已知分佈	無沖突、均勻 / 需預知分佈
2. 數字分析法	取關鍵字中分佈均勻的若干位	關鍵字位數多、某些位固定（如手機號前綴）	靈活 / 需人工分析
3. 平方取中法	取 key² 中間幾位	關鍵字位數較少、分佈未知	中間位與所有位相關、沖突少 / 計算稍重
4. 折疊法	分段疊加取後位	關鍵字位數很長、各位分佈均勻	信息融合好 / 需選擇分段方式
5. 除留余數法	H(key) = key % p (p ≤ 表長，通常取素數)	最常用、通用性強	簡單高效 / p 選擇影響沖突率
6. 隨機數法	H(key) = random(key)	關鍵字長度不等	分佈均勻 / 需優質隨機函數

除留余數法取素數經驗表

表長 m =  8  -> p =  7
表長 m = 16  -> p = 13
表長 m = 32  -> p = 31
表長 m = 64  -> p = 61
一般取 ≤ m 的最大素數

二、四大沖突解決策略

1. 開放定址法

沖突時在表內尋找下一個空槽。三種探測序列：

線性探測：Hᵢ = (H(key) + i) % m —— 簡單但易產生「堆集」。
二次探測：Hᵢ = (H(key) ± i²) % m —— 減少堆集，但可能無法探測到所有槽位。
偽隨機探測：Hᵢ = (H(key) + Rᵢ) % m —— R 為隨機序列。

2. 再哈希法

Hᵢ = RHᵢ(key)，使用多個不同哈希函數。優點：不堆集。缺點：計算開銷大。

3. 鏈地址法（工程首選）

同義詞鏈成單鏈表，哈希表存鏈表頭指針。優點：無堆集、動態分配適合不定長、刪除簡單。Java HashMap、C++ unordered_map、Redis 哈希表均採用此法。

4. 公共溢出區法

基本表 + 溢出表。沖突者統一進溢出表。結構簡單但查找效率較低。

三、C 語言完整實現（開放定址法 + 線性探測 + 除留余數法）

#include 
#include 

#define HASHSIZE 7
#define NULLKEY -32768

typedef int Status;
typedef struct {
    int* elem;   // 動態數組
    int count;   // 當前元素數
} HashTable;

int m = 0;  // 實際表長

// 初始化
void InitHashTable(HashTable* ht) {
    m = HASHSIZE;
    ht->elem = (int*)malloc(m * sizeof(int));
    ht->count = m;
    for (int i = 0; i < m; i++) ht->elem[i] = NULLKEY;
}

// 哈希函數：除留余數法
int Hash(int key) { return key % m; }

// 插入
void Insert(HashTable* ht, int key) {
    int addr = Hash(key);
    while (ht->elem[addr] != NULLKEY) {  // 沖突
        addr = (addr + 1) % m;           // 線性探測
    }
    ht->elem[addr] = key;
}

// 查找
int Search(HashTable* ht, int key) {
    int addr = Hash(key);
    while (ht->elem[addr] != key) {
        addr = (addr + 1) % m;
        if (ht->elem[addr] == NULLKEY || addr == Hash(key)) return -1;  // 失敗
    }
    return addr;  // 成功返回位置
}

// 顯示
void Display(HashTable* ht) {
    for (int i = 0; i < ht->count; i++) printf("%d ", ht->elem[i]);
    printf("\n");
}

int main() {
    HashTable ht;
    int data[] = {13, 29, 27, 28, 26, 30, 38};
    
    InitHashTable(&ht);
    for (int i = 0; i < HASHSIZE; i++) Insert(&ht, data[i]);
    Display(&ht);  // 觀察分佈
    
    int pos = Search(&ht, 30);
    if (pos == -1) printf("未找到\n");
    else printf("位置: %d\n", pos);
    
    free(ht.elem);
    return 0;
}

運行結果示例

哈希表內容: 26 30 38 13 29 27 28 
查找 30 -> 位置: 1

四、狀態碼規範定義

#define TRUE  1
#define FALSE 0
#define OK    1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;  // 函數返回狀態碼類型

C 無內置 bool，統一定義 Status 類型統一錯誤碼語義，提高代碼可讀性與可維護性。

五、工程選型建議

場景	推薦方案	理由
通用鍵值存儲	鏈地址法 + 動態擴容	無堆集、負載因子可控、刪除 O(1)
嵌入式/固定表	開放定址 + 線性探測	內存緊湊、無指針開銷、代碼極簡
高性能緩存	Cuckoo Hash / Robin Hood Hash	最壞情況 O(1)、緩存友好
字符串鍵	FNV-1a / MurmurHash / SipHash	高質量哈希值、防哈希洪水攻擊