散列表線性探測法與鏈地址法平均查找長度（ASL）計算實例

題目參數

• 表長 m=8，哈希函數 H(key)=key % 7。
• 關鍵字序列：(25, 31, 8, 27, 13, 68)。

插入過程

ASL 計算 (等概率查找)

成功查找 ASL = Σ(查找次數) / n

• 線性探測：25(1)+31(1)+8(1)+27(1)+13(2)+68(1) = 7 → **7/6 ≈ 1.167**
• 鏈地址：25(1)+31(1)+8(1)+27(1)+13(2)+68(1) = 7 → **7/6 ≈ 1.167**

結論

本例中僅 13 與 27 衝突 (H=6)，兩種解決衝突方法導致的額外比較次數相同，**ASL 均為 7/6**。答案給的鏈地址 4/3 有誤 (可能漏算了 13 的第二次比較)。