為什麼 HashMap 中的load factor在各個語言的實現中都在 0 6 0 8 之間？

1樓：乾貨滿滿張雜湊

首先，這個基於乙個假設，那麼就是當乙個事件發生的概率大於 0.5，那麼這件事就是很可能發生的。

然後，假設當前有 s 個桶，那麼每次放入乙個元素進入某乙個桶的概率就是：

放入了第 n 個元素，那麼，某乙個桶元素個數為e的概率，根據二項式分布就是：

將e=0代入，得出：

讓這個概率大於 0.5 也就是 1/2

那麼解這個不等式，得到：

n" eeimg="1"/>

如果讓 s 趨近於無窮大，那麼 n/s 就無限接近於 log(2). 也就是放入的元素數量是所有桶的數量的 log(2) ~ 0.693

2樓：Excalibur

設定load factor的目的是為了提高hashmap的插值和取值效率。因此在考慮Load Factor取值範圍的時候，必須要考慮hashmap構成的兩種情況，Hashmap的構成方式是究竟是open address還是separate chain.

在open address的情況下，load factor的取值等價於 n/m。n為元素的數量，m為array的長度，我們對它的期望值一般為2/3，即0.667。

當load factor取值超過2/3時，效能開始變差。

而在separate chain的情況下，load factor的情況開始不同，因為separate chain是array的每個值套上乙個linked list，因此load factor可以超過1。

3樓：

正如題主說的，load factor的取值對於hashmap來說非常重要，因為太大了，則會影響到插入和查詢效率。太小了就會造成不斷擴容而影響hashmap的效能。不同語言對這個值的取值並不是完全一樣，因為目前來說更多的是從測試分析應該取多少合適。

這點可以在wikipedia上看到：

當load factor取值大於0.8的時候，線性探測的未命中數會急劇增加，這也意味著線性探測的效能在急劇下降。