經典算法深度解析：哈希查找原理、哈希函數構造與沖突解決策略

編輯：關於C語言

哈希查找核心思想

建立關鍵字 key 到存儲地址 f(key) 的直接映射。查找時計算 f(key) 直接定位，**理想情況 O(1)**。屬於「以空間換時間」策略。

六種哈希函數構造方法

方法	公式/思路	適用場景
直接定址法	f(key)=a*key+b	鍵值連續、分布均勻、表較小
數字分析法	取鍵值中分布均勻的若干位	鍵值位數多、已知分布（如手機號後四位）
平方取中法	鍵值平方後取中間位	鍵值分布不明、表長固定
折疊法	分段疊加取後位	鍵值位數很長、各位分布均勻
除留余數法	f(key)=key % p (p≤表長, 取質數)	最常用、通用性強
隨機數法	f(key)=random(key)	鍵值長度不等

四種沖突解決策略

1. 開放定址法

沖突時按探查序列尋找下一空槽：

線性探測：Hi = (H(key)+i) % m，易產生堆積。
二次探測：±i² 跳躍，減少堆積但可能無法探測全表。
偽隨機探測：Hi = (H(key)+Ri) % m，Ri 為隨機序列。

2. 再哈希法

準備多個哈希函數 H1, H2, ...，沖突時依次嘗試。計算開銷大，不易堆積。

3. 鏈地址法（最常用）

每個桶掛單鏈表，同義詞鏈接在同一表中。優點：無堆積、動態分配節點、刪除簡單、適合表長不可預知場景。

4. 公共溢出區法

基本表 + 溢出表。沖突元素全部進溢出表。查找先基本表再溢出表。

查找過程

計算 addr = H(key)。
若桶空 → 失敗。
遍歷桶鏈表/探查序列，比較關鍵字。
匹配 → 成功；遇到空槽/回到起點 → 失敗。

C 代碼實現（鏈地址法 + 除留余數）

#include <stdio.h>
#include <stdlib.h>

#define HASHSIZE 7
#define NULLKEY -32768

typedef struct { int *elem; int count; } HashTable;
int m = 0;

void InitHashTable(HashTable *ht) {
    m = HASHSIZE;
    ht->elem = malloc(m * sizeof(int));
    ht->count = m;
    for (int i=0;ielem[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;icount;i++) printf("%d ", ht->elem[i]);
    printf("\n");
}

int main() {
    HashTable ht; InitHashTable(&ht);
    int a[] = {13,29,27,28,26,30,38};
    for (int i=0;i<7;i++) Insert(&ht, a[i]);
    Display(&ht);
    printf("30 at index %d\n", Search(&ht, 30));
    return 0;
}