關於散列表中基於線性探測方法的Open Addressing的混淆？

Question

假設根據字符串「temp」的哈希函數的數組索引爲155，並且位置155被預先佔用，則嘗試位置156。假設位置156是可用的，所以這個條目保存在位置156而不是155.稍後，我發現另一個字符串「another_temp」，它映射到位置156，再次保存在下一個可用位置157處。

問題是：稍後如果我想查找「another_temp」的位置，我怎麼知道它是157而不是156，即使散列函數返回156？

謝謝。

Answer 1

您需要比較密鑰，而不僅僅是哈希代碼。在散列表中，無論如何都需要存儲密鑰（「temp」和「another_temp」）。只存儲和比較散列值是不夠的，因爲散列值不是唯一的。

開放尋址有幾個問題。一個是：刪除一個條目後該怎麼辦？通常你會存儲一個特殊的「已刪除」標記。另一個問題是：如果發生衝突，你應該增加散列碼嗎？你會在維基百科找到更多細節。