資料結構與演算法
比較處理雜湊表碰撞的鏈結法（以鏈結串列串接相同位置的元素）與開放定址法（在表中尋找其他空位置），下列說明何者正確？負載因子為存放的元素數除以表的大小所得的值。
- A鏈結法在負載因子超過1時也能存放，但開放定址法無法存放超過表大小的元素，且負載因子接近1時搜尋次數會急遽增加
- B開放定址法不會發生碰撞，因此無論負載因子為何，搜尋都只需1次
- C鏈結法無論負載因子多高，搜尋的工作量都不變
查看答案與解析
正確答案：A. 鏈結法在負載因子超過1時也能存放，但開放定址法無法存放超過表大小的元素，且負載因子接近1時搜尋次數會急遽增加
鏈結法把相同位置的元素串成串列，因此元素數超過表的大小也能存放，但串列的平均長度與負載因子成正比增加，搜尋的工作量也隨之增加。開放定址法只存放在表中，元素數最多只能到表的大小，負載因子接近1時尋找空位的次數會急遽增加。無論哪種方法，負載因子超過設定值（例如約0.5～0.75）時，通常都會放大表格並重新放入所有元素（重新雜湊）。開放定址法也會發生碰撞，是靠尋找空位置來處理。
- A. 正確。正確說明了可存放數量的差異，以及負載因子高時搜尋次數增加方式的差異。
- B. 開放定址法也會發生碰撞，是靠尋找其他空位置來處理。
- C. 串列的平均長度與負載因子成正比，負載因子高時搜尋的工作量會增加。