在元素很多、負載因子維持在0.5左右的雜湊表中，使用線性探測的開放定址法往往比鏈結法（以鏈結串列串接的方法）快，最適當的原因為下列何者？

正確答案：A. 發生碰撞時下一個檢查的位置是相鄰的元素，多半位於同一條快取行或緊接的下一條，因此記憶體存取較少

在現今的 CPU 中，因快取未命中而讀取主記憶體的時間，比比較等計算長得多。線性探測在碰撞時檢查相鄰位置，因此多半在同一條快取行內就能完成，預取也能發揮效果。鏈結法中，串列的下一個元素常位於記憶體中遠處，每追蹤一次指標都容易發生快取未命中。即使時間複雜度的階相同，實際速度也會因記憶體存取方式而有很大差異。不過，線性探測在負載因子變高時，被占用的位置會聚集而急遽變慢，因此要把負載因子維持在較低的程度。

• A. 正確。只檢查相鄰的位置，因此容易只用快取中的資料就完成。
• B. 開放定址法也會發生碰撞，是靠檢查相鄰位置來處理。
• C. 兩者都只計算1次雜湊函數，差異在於記憶體的存取方式。