Hashmap - 負載因子等於容量

我在一次採訪中被問到一個非常好的問題。問題是 -Hashmap - 負載因子等於容量

我們知道如果hashmap條目達到loadfactor，就會發生重新哈希。例如 - 如果我的loadfactor是7，我的mapsize是9，那麼當沒有時，就會發生刷新。的條目達到7個。

現在的問題是，我想在這張地圖上只輸入8個元素（因爲我們知道我已經將負載因子保持爲7），那麼當我輸入第7個元素時，就會發生重新哈希。所以我只是想在第7個元素後添加一個元素，但是重新哈希發生並且大小不必要地增加，並且導致不必要的內存浪費。那麼爲什麼我沒有保持loadfactor大小等於初始容量。爲什麼它保持在75％或80％或類似的東西。

在此先感謝您的答案。

來源

2013-08-25 Shanky

「那麼我爲什麼不保持客座率大小等於初始容量。爲什麼它是保持在75％或80％，或類似的東西。」

散列表代碼無法預測您將插入地圖的元素數量。它所要做的就是減少內存realloc操作的次數。在超載情況下進行擴展是一種簡單（有效的）策略，它可以保持時間複雜度較低，即在最差情況下O（log（n））次重新分配。

更新

負荷率的新插入的元素相撞已加載的元素的可能性的指標，也就是你的HashMap裝的越多，它更可能將新的元素碰撞，手段元素的hashkey是相等的，這將導致目標桶中更長的喜歡列表，從而降低效率。加載因子嘗試防止散列表退化爲多個長鏈接列表，對於插入或刪除操作，這不是o（1）。

來源

2013-08-25 05:53:08 lulyon

很多謝謝你的回答。但我仍然感到困惑。你說的是，當超過負載因子時擴展是一個簡單的（和有效的）策略......這很好，但他們爲什麼不保持負載因子等於初始容量，這樣只有當hashmap滿了纔會發生重新哈希。 – Shanky

@Shanky我想我明白你的意思了。這是爲什麼：加載因子是新插入的元素與已加載元素相沖突的可能性的指示器，也就是說，加載的散列表越多，新元素髮生碰撞的可能性越大，意味着元素的散列密鑰相等，這將導致目標桶中更長的喜歡名單，從而降低效率。加載因子嘗試防止散列表退化爲多個長鏈接列表，這對於插入操作不是o（1）。 – lulyon

這並不能解釋爲什麼加載因子不是1.它解釋了爲什麼調整大小不僅僅爲空間分配了一些新元素。 –

在這種情況下，加載因子不是7，而是7/9。你在問爲什麼它小於1，因爲這意味着在空桶上浪費了一些內存。答案是它通過增加桶之間物品均勻分佈的可能性來加速插入和刪除。如果負載因子小於1，並且散列函數很好，那麼通常每個存儲桶只有一個項目 - 低衝突或無衝突。

來源

2013-08-25 14:49:26

@ SeanOwen-你的回答是對的，我的查詢得到了答覆。謝謝 – Shanky

Hashmap - 負載因子等於容量

回答

相關問題