使用開放式解決

Question

當我使用的是開放尋址陣列實現計算哈希表的負載係數刪除哈希表的負載係數計算條目：

numberOfKeysInArray/sizeOfArray 

但它發生，我認爲由於刪除的條目必須被標記爲這樣（爲了區分它們與空白空間），將這些包括在鍵的數量中可能是有意義的。

我的想法是，只要估計探頭的平均發生數爲找到一個條目，刪除條目應計入客座率，但就插入他們應該不是一個新的密鑰。

這是正確的計算：包括刪除鍵或不？

Answer 1

根據定義，不，根據定義，負載因子是元素數量與存儲區陣列大小的比率。見例如Wikipedia或this lecture。

在計算加載因子中的已刪除條目時也會出現實際問題。大多數實現具有最大負載因數。如果實際超過允許的最大值，則後備陣列大小會增加。如果刪除的條目計入較高的負載因數，則可能會導致碎片內容表中幾乎爲空但高度較高的陣列大小增加。