爲什麼使用線性探測的散列表需要「無對象」值或布爾的並行數組？

Question

爲什麼使用線性探測的散列表需要「無對象」值或布爾的並行數組？ 舉例說明如果我們既沒有這些技術，也可能發生問題？哪種技術更節省空間？爲什麼？

Answer 1

問問自己：當我們從哈希表中刪除一個項目時會發生什麼？如果在某個時候我們將某個元素插入導致碰撞的散列表中，我們將不得不線性探測以找到一個更好的點，但是如果我們刪除原始項並且不留下標記，我們將永遠無法再次找到新項目。

至於哪一個更有效率，通常留下一個「無對象」值是最好的，因爲空間必須以任何方式使用，所以我們不妨將它用於某些東西而不是分配一個全新的數組跟蹤哈希表中什麼內存是無用的。