使用線性探測實現散列表時調整大小權衡

Question

我正在嘗試使用線性探測來實現散列表。

在將（key，value）對插入散列表之前，我想檢查它是否已滿。如果是這樣，我需要加倍底層數組的大小。

顯然，有兩種方法可以做到這一點：

之一是創建具有一倍大小的另一個陣列，在老調重彈舊的所有條目，並將它們添加到新陣列。然後，將舊陣列重新綁定到新陣列。這種方式很容易實現，但使用了很多空間。

另一個是將數組加倍並在原地進行重新哈希。看起來，這種方式可能會導致運行時間更長，因爲重新散列可能會導致與新散列的插槽和舊插槽的衝突。

我應該使用哪種方式？

Answer 1

你的第二個解決方案只在調整尺寸處理如果其實也有拓展空間就地現有的哈希表節省了空間 - 我想既然如此爲一個大的哈希表的可能性很小，所以我只想去找你的第一個解決方案。