資料結構：雜湊函數設計與衝突處理策略

資料結構：雜湊函數設計與衝突處理策略

雜湊查找核心思想

建立關鍵字與儲存位址的確定對應關係 H(key) → address，查找時間複雜度可達 O(1)。優於循序查找 O(n) 與樹狀查找 O(log n)。

雜湊函數構造方法

好函數標準：構造簡單、雜湊地址均勻分佈 (均勻雜湊函數)、衝突少。

衝突處理策略

1. 開放定址法

Hi = (H(key) + di) MOD m, i = 1..k

• 線性探測：di = 1,2,3... — 易產生「堆積」
• 二次探測：di = 1²,-1²,2²,-2²... — 減少堆積
• 偽隨機探測：di 為偽隨機序列

2. 再雜湊法

構造多個雜湊函數 RHi，衝突時依序嘗試 RH1, RH2...。優點：不易堆積；缺點：計算時間增加。

3. 鏈結法 (最常用)

同義詞存入單鏈表，雜湊表儲存頭指標陣列 RecNode *linkhash[m]。插入/查找/刪除皆在鏈表操作，負載因子可 > 1。

雜湊查找效能分析

平均查找長度 (ASL) 取決於：

• 雜湊函數品質 (影響衝突頻率)
• 衝突處理方法 (各方法 ASL 公式不同)
• 裝填因子 α = 表中記錄數 / 雜湊表長度 — α 越小衝突越少，α 越大比較次數越多

結論：ASL 與裝填因子相關，與記錄總數無關。設計核心在於「好函數 + 適當衝突處理 + 控制 α」。