雜湊表計算工具

正確答案：B. 不同的鍵求出相同的雜湊值（存放位置）

雜湊表以雜湊函數從鍵計算存放位置，平均能以 O(1) 進行搜尋、插入與刪除。鍵的種類遠多於表的大小，因此不同的鍵落在相同位置（碰撞）無法避免。所以要用把相同位置的元素串成串列的鏈結法，或尋找其他空位置的開放定址法等來處理碰撞。相同的鍵若不一定求出相同的雜湊值就無法搜尋；能否從雜湊值得知原本的鍵，則是用於密碼學時的性質，與碰撞無關。

正確答案：C. 位置6

4個鍵除以7的餘數都是3，因此都會先檢查位置3。10放入位置3；17因位置3已被占用而放入位置4；24因位置3、4已被占用而放入位置5。3因位置3、4、5都已被占用，所以存放在位置6。如此可見，線性探測法會使被占用的位置聚集在一起（叢集），越晚來的鍵需要檢查的次數越多。

正確答案：A. 鏈結法在負載因子超過1時也能存放，但開放定址法無法存放超過表大小的元素，且負載因子接近1時搜尋次數會急遽增加

鏈結法把相同位置的元素串成串列，因此元素數超過表的大小也能存放，但串列的平均長度與負載因子成正比增加，搜尋的工作量也隨之增加。開放定址法只存放在表中，元素數最多只能到表的大小，負載因子接近1時尋找空位的次數會急遽增加。無論哪種方法，負載因子超過設定值（例如約0.5～0.75）時，通常都會放大表格並重新放入所有元素（重新雜湊）。開放定址法也會發生碰撞，是靠尋找空位置來處理。

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

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