哈希表是實現 O(1) 平均查找/插入/刪除的核心資料結構。面對「不同鍵值映射至同一槽位」的哈希衝突，工業界主流採用分離鏈結法與開放定址法。本文系統整理《Data Structures and Algorithm Analysis in C》（Weiss）經典教材中的雙策略完整實作，包含 ADT 設計、質數容量擴充、平方探測、再哈希等進階技術，附帶可直接編譯的標準 C 程式碼。
兩種實作共用統一介面，便於上層邏輯無縫切換：
typedef int ElementType;
typedef unsigned int Index;
typedef Index Position; // 開放定址法直接用索引作 Position
typedef struct HashTbl *HashTable;
HashTable InitializeTable(int TableSize);
void DestroyTable(HashTable H);
Position Find(ElementType Key, HashTable H);
void Insert(ElementType Key, HashTable H);
ElementType Retrieve(Position P, HashTable H); // 開放定址需傳 H
HashTable Rehash(HashTable H); // 僅開放定址需要
struct ListNode {
ElementType Element;
Position Next;
};
typedef Position List; // 帶表頭節點的鏈表
struct HashTbl {
int TableSize; // 質數容量
List *TheLists; // 指標陣列，長度 TableSize
};
TheLists[i] 指向一個哨兵節點，實際資料掛在 Next 之後。NextPrime()static int NextPrime(int N) {
if (N % 2 == 0) N++;
for (;; N += 2) {
int i;
for (i = 3; i * i <= N; i += 2)
if (N % i == 0) goto ContOuter;
return N;
ContOuter: ;
}
}
保證負載因子 λ = N/TableSize ≤ 1，維持鏈表極短。
Index Hash(ElementType Key, int TableSize) {
return Key % TableSize; // 整數鍵值簡單取模
}HashTable InitializeTable(int TableSize) {
HashTable H = malloc(sizeof(struct HashTbl));
H->TableSize = NextPrime(TableSize);
H->TheLists = malloc(sizeof(List) * H->TableSize);
for (int i = 0; i < H->TableSize; ++i) {
H->TheLists[i] = malloc(sizeof(struct ListNode));
H->TheLists[i]->Next = NULL; // 哨兵節點
}
return H;
}
Position Find(ElementType Key, HashTable H) {
Position P;
List L = H->TheLists[Hash(Key, H->TableSize)];
P = L->Next;
while (P != NULL && P->Element != Key)
P = P->Next;
return P; // NULL 表未找到
}
void Insert(ElementType Key, HashTable H) {
Position Pos = Find(Key, H);
if (Pos == NULL) { // 不允許重複鍵
Position NewCell = malloc(sizeof(struct ListNode));
List L = H->TheLists[Hash(Key, H->TableSize)];
NewCell->Element = Key;
NewCell->Next = L->Next;
L->Next = NewCell; // 頭插
}
}
void DestroyTable(HashTable H) {
for (int i = 0; i < H->TableSize; ++i) {
Position P = H->TheLists[i];
while (P != NULL) {
Position Tmp = P->Next;
free(P);
P = Tmp;
}
}
free(H->TheLists);
free(H);
}
enum KindOfEntry { Legitimate, Empty, Deleted };
struct HashEntry {
ElementType Element;
enum KindOfEntry Info; // 狀態標記
};
typedef struct HashEntry Cell;
struct HashTbl {
int TableSize;
Cell *TheCells; // 連續陣列，無額外指標
};
Deleted 標記解決「刪除後查找路徑中斷」問題（Lazy Deletion）。第 i 次探測位移 f(i) = i²，實作上用遞迴公式 f(i) = f(i-1) + 2i - 1 避免乘法：
Position Find(ElementType Key, HashTable H) {
Position CurrentPos = Hash(Key, H->TableSize);
int CollisionNum = 0;
while (H->TheCells[CurrentPos].Info != Empty &&
H->TheCells[CurrentPos].Element != Key) {
CurrentPos += 2 * ++CollisionNum - 1; // +1, +3, +5, +7...
if (CurrentPos >= H->TableSize)
CurrentPos -= H->TableSize;
}
return CurrentPos; // 可能是 Empty、Deleted 或找到的 Legitimate
}
定理：若 TableSize 為質數且負載因子 λ < 0.5，平方探測保證能探測到所有槽位且不會陷入無限迴圈。
void Insert(ElementType Key, HashTable H) {
Position Pos = Find(Key, H);
if (H->TheCells[Pos].Info != Legitimate) {
H->TheCells[Pos].Info = Legitimate;
H->TheCells[Pos].Element = Key;
}
}
HashTable Rehash(HashTable H) {
int OldSize = H->TableSize;
Cell *OldCells = H->TheCells;
H = InitializeTable(2 * OldSize); // 新容量 = 2×舊容量 → 再找質數
for (int i = 0; i < OldSize; ++i)
if (OldCells[i].Info == Legitimate)
Insert(OldCells[i].Element, H);
free(OldCells);
return H;
}
當 λ > 0.5 時呼叫 Rehash()，攤還成本 O(1)。
void DestroyTable(HashTable H) {
free(H->TheCells);
free(H);
}
| 指標 | 分離鏈結法 | 開放定址法（平方探測） |
|---|---|---|
| 記憶體開銷 | 指標 + 節點分配器 | 僅陣列，緊湊 |
| 快取表現 | 跳躍式存取 | 連續掃描，極佳 |
| 負載因子上限 | 可 > 1（鏈表變長） | 建議 < 0.5，否則需 Rehash |
| 刪除複雜度 | 標準鏈表刪除 | 需 Lazy Deletion 標記 |
| 適用場景 | 鍵值大小不一、頻繁刪除、記憶體充裕 | 高效能查找、固定大小鍵、嵌入式系統 |
hashsep.h // 分離鏈結 ADT
hashsep.c // 分離鏈結實作
hashquad.h // 開放定址 ADT
hashquad.c // 開放定址實作
fatal.h // 錯誤處理巨集（Error/FatalError）
main.c // 測試驅動程式編譯指令：gcc -std=c99 -O2 hashsep.c hashquad.c main.c -o hashtable_demo
O(1) 查找。掌握分離鏈結與開放定址兩大經典實作，不僅能應付面試手寫哈希表，更能在效能調優時依據資料特性（鍵值分佈、讀寫比例、記憶體預算）做出最優架構決策。
