資料結構與演算法
關於雜湊表中碰撞（collision）的說明，下列何者正確？
- A能從雜湊值求出原本的鍵
- B不同的鍵求出相同的雜湊值（存放位置）
- C相同的鍵每次執行都求出不同的雜湊值
查看答案與解析
正確答案：B. 不同的鍵求出相同的雜湊值（存放位置）
雜湊表以雜湊函數從鍵計算存放位置，平均能以 O(1) 進行搜尋、插入與刪除。鍵的種類遠多於表的大小，因此不同的鍵落在相同位置（碰撞）無法避免。所以要用把相同位置的元素串成串列的鏈結法，或尋找其他空位置的開放定址法等來處理碰撞。相同的鍵若不一定求出相同的雜湊值就無法搜尋；能否從雜湊值得知原本的鍵，則是用於密碼學時的性質，與碰撞無關。
- A. 無法求出原本的值（單向性）是密碼學雜湊函數的性質，與碰撞無關。
- B. 正確。不同的鍵落在相同位置稱為碰撞，一定要以某種方法處理。
- C. 相同的鍵若產生不同的值就找不到資料，因此雜湊函數會設計成不會如此。