HashMap的0.75可能只是一個經驗值詳情 - hashmap,java 北冥有隻魚博客

前言

還是要面對HashMap的，這是個高頻面試點，以前本身想着一口氣講投HashMap的，但是一口氣講投HashMap想來非常消耗肺活量，篇幅也讓人生畏，所以將其分拆為幾篇，每篇是獨立的主題，最後又將主題合併起來。本篇就來看HashMap, 看的就是HashMap的構造函數:

static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
   this.loadFactor = DEFAULT_LOAD_FACTOR; 
}

這也是HashMap的一道面試題，為什麼HashMap的負載因子選擇了0.75，有人從代碼註釋上入手:

As a general rule, the default load factor (.75) offers a good tradeoff between time a. space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

一般而言，默認負載因子是0.75在時間和空間的成本上進行了很好的權衡，過大雖然會減少空間開銷，但是會增加查找開銷(反應在HashMap的大多數操作中，包括get和put)。設置初始容量的時候，預期的鍵值對數目和負載因子應當被考慮，避免過度擴容。如果初始容量大於預期的最大鍵值對除以負載因子，就會發生擴容操作。

這好像説了什麼，又好像什麼都沒説，在0和1之間有很多數字，為什麼偏偏就選中了0.75。在python裏面也有類似於HashMap的集合，Python中是0.762，在Go中是0.65，Dart中是0.68。好像都在0.7附近。網上有其他答案是從泊松分佈入手的，從泊松分佈入手的大概是沒有好好看HashMap的註釋:

Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD).

因為TreeNode的大小約是普通結點的兩倍，所以我們使用TreeNode僅當在桶上有足夠的結點才會去使用(TREEIFY_THRESHOLD)，

And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used.

而當它們由於移除或擴容操作，它們會被轉為普通的哈希桶。哈希分佈良好的情況下，幾乎很少使用樹結構。

Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
factorial(k)).

理想情況下，哈希值隨機，負載因子為0.75的情況下，儘管由於粒度調整會產生較大的方差，桶中的節點分佈頻率遵從參數為0.5的泊松分佈。桶裏出現一個的概率為0.6，超過8個的概率已經小於千萬分之一。

The first values are:
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million

我們可以看到這個只是解釋鏈表在有幾個節點轉為紅黑樹的原因，已經默認是在負載因子為0.75下進行的討論，還是沒有解釋負載因子為什麼是0.75。在知乎上隨手翻問題的答案，有人給了一個看起來比較靠譜的鏈接:

https://stackoverflow.com/questions/10901752/what-is-the-significance-of-load-factor-in-hashmap/10901821#10901821。

一種可能的答案

我們知道，在理想情況下，對於散列算法我們有一個簡單的假設，散列函數應當易於計算，並且能夠均勻的分佈所有鍵，即對於任意鍵，0到M-1之間的每個整數都有相等的可能性。也就是説如果我們的數組容量為s，放在0-s-1這些位置上的概率是相等的也就是

$$ \frac{1}{s} $$

那我們現在有n個key，數組大小還是s，那麼我們現在就要求出現0碰撞為0的概率，也就是説要麼不出現碰撞，要麼至少出現一次碰撞，設每次不出現碰撞的概率為p, 則出現碰撞的概率為1-p。現在我們來求兩個不相等的元素出現在一個位置的概率, 首先將用h代替哈希函數，hash碰撞意味着h(k1) = h(k2) , 我們用$F_x$ 標記事件h(k1) = h(k2) = x, 每個鍵映射到任意一個桶的概率是:

$$ \frac{1}{s} $$

我們用E來標記兩個不同的key出現在相同位置這個事件:

$$ E=⋃\limits_{x}F(x) $$

x = 2 , 意味着兩個不同的key出現在了相同位置上，x=3意味着三個元素被計算到一個位置上。E是所有這類事件的並集，對每個特定的位置，兩個key都在這個位置的概率為:

$$ \frac{1}{s^2} $$

由於E是所有事件的並集所以, 所以我們是對概率求和，一共有s個位置，每個位置都是:

$$ \frac{1}{s^2} $$

那麼累加起來就是

$$ \frac{1}{s} $$

也就是説出現hash碰撞的概率我們可以用$\frac{1}{s}$來表示，如果對於上述不理解，用扔骰子這個例子來解釋就是，一個骰子，連續扔兩次，兩次點數為一樣的概率，這個骰子當然要是均勻的，也就是説每一面出現的概率都是相同的，這個概率為$\frac{1}{s}$。讓我們的問題再超前走一步，我們向s個桶裏放了n次，0次碰撞的概率，在均勻假設下，這符合二項式分佈：

$$ (n,k)p^k(1-p)^(n-k) $$

n為實驗次數, k為成功次數，我們希望一次也不碰撞，上面的式子化簡為:

$$ (n,0)\frac{1}{s}^0(1-\frac{1}{s})^n $$

我們希望不發生碰撞的概率大一些也就是$\frac{1}{2}$, 我們的式子就變成了下面這樣:

$$ (1-\frac{1}{s})^n >= \frac{1}{2} $$

這裏我們藉助對數進行來對不等式進行處理，鑑於一些同學的對數放縮可能忘記了，我們這裏再複習一下對數:

$$ c = a^b $$

然後我們有:

$$ b = \log_{a} c $$

a被稱為底數，x被稱為真數，當 0 < a < 1, 單調遞減，1 < a的時候單調遞增，所以我們有下面的變換:

$$ \log_{a} c > \log_{a} d $$

則c > d , 所以對於上面的對數我們可以用對數來進行變換:

$$ n ln(1-\frac{1}{s}) >= -ln2; 1- \frac{1}{s} < 1 , ln 1 = 0, ln({1-\frac{1}{s}}) < 0。 n <= \frac{-ln2}{ln\frac{s-1}{s}}; \frac{s-1}{s} 可以看成\frac{s}{s-1}^-1。 n <= \frac{ln2} {\ln\frac{s}{s-1}} $$

然後同時除以s，我們只關注等於的情況:

$$ \frac{n}{s} = \frac{ln2}{s ln\frac{s}{s-1}} $$

$\frac{n}{s}$剛好是擴容因子，現在讓桶不斷的變大，我們觀察擴容因子會向哪個值靠近，這個問題就等價於求極限:

$$ \lim_{s \to \infty} \frac{ln2}{s ln\frac{s}{s-1}} $$

然後我們將s = m + 1, s 趨於無窮就可以被代換為m 趨於無窮，兩者是等價無窮大，然後上面的式子就變形為:

$$ \lim_{m \to \infty} \frac{ln2}{m+1 ln\frac{m+1}{m}} $$

然後我們將$x = \frac{1}{m}$, 則m趨於無窮，x趨於0, 於是式子變為:

$$ \lim_{s \to 0} \frac{ln2} {(\frac{1}{x + 1}) ln (1 +x)} $$

而$ln(1 + x)$ 和 $x$ 又是等價無窮小，所以式子變換為:

$$ \lim_{s \to 0} \frac{ln2} {(\frac{1}{x + 1}) x} $$

於是當s 趨於0的時候，n/s整體向ln2靠近，而ln2則是0.69314718055995，我們直到HashMap的容量大小是2的次方，乘以ln2得到的也是一個小數，所以我們需要向上取整，所以取了0.75。在做對數變換的時候，我們取的是以e為底的對數，但是我們上面提到，我們用大於1的底數進行替換，仍然成立。但為什麼取e呢，取e上面的邏輯走的通了，這很牽強，建立的建設也是在hash函數完美理想的情況下。下面我們談一下為什麼當鏈表的節點為8個的時候，才轉為紅黑樹，為什麼符合泊松分佈。

為什麼是泊松分佈?

什麼是概率，由原因結果，什麼概率，一種定義事件發生概率的方法是利用事件發生的相對頻率。定義如下: 假設有一個樣本空間為S的實驗，它在相同的條件下可重複進行，對於樣本空間S中的事件E，記n(E)為n次重複實驗中事件E的發生次數，那麼，該事件發生發生的概率P(E)就定義如下:

$$ P(E) =\lim_{m \to \infty}\frac{n(E)}{n} $$

即定義頻率P(E)為E發生的次數佔實驗次數的比例的極限，也即E發生頻率的極限。上述定義雖然很直觀，但是有一個致命的缺陷在於你怎麼知道n(E)/n會收斂到一個固定的常數，而且如果進行另一次重複實驗，它會收斂到同樣的常數。有人可能回答，我實驗了好多次啊，這種回答可能基於概率建立在n(E) / n趨於某常數值這樣一個公設上面，但它不夠簡單，更為通用的是，假定一些更簡單、更為顯而易見的公理，然後去證明頻率在某種意義下趨於一個常數極限不是更合情合理嘛。這也就是現代概率公理化方法。那什麼是數理統計，由結果看原因，這裏不再展開數理統計的討論，本篇不涉及這個。所以我們在算概率的時候，要先知道原因，也就是説，知道骰子的均勻性。上面我們在算概率的時候用到了二項式分佈，如果我們令n足夠大，p充分小，而使得np保持適當的大小時，參數為(n,p)的二項隨機變量可近似地看做是參數為λ = np的泊松隨機變量，這裏不給出證明過程，我們只給出泊松分佈的分佈列:

$$ P(X = k) = \frac{e^{-\lambda} \lambda^k}{k!} $$

再把上面的註釋拉出來看一下:

Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
factorial(k)).

理想情況下，哈希值隨機，負載因子為0.75的情況下，儘管由於粒度調整會產生較大的方差，桶中的節點分佈頻率遵從參數為0.5的泊松分佈。桶裏出現一個的概率為0.6，超過8個的概率已經小於千萬分之一。

那λ也就是0.5，至於怎麼得出呢，也沒給出過程，λ=np, np是二項式分佈的數學期望，這是一個加權平均，E(X) = np，p為1/s, 在理想情況下，一次不衝突的概率是0.75，這裏也不知道是怎麼推導出來的，在衝突的概率下推導出的np = 0.5 , 然後算這個桶裏面出現一個元素的概率為0.60653066，出現8個元素的概率為0.00000006。所以我覺得HashMap的默認負載因子是一個經驗值，鏈表由八個結點變為紅黑樹也是一個經驗值，建立在np= 0.5的基礎上。

寫在最後

這是我畢業時我看到的問題，我看了許多推導，感覺都是差了一些，不完備，這次就係統而完善的對這個問題進行討論，有可能我也有遺漏的地方。歡迎指出。

參考資料

[1] Java 8系列之重新認識HashMap https://tech.meituan.com/2016/06/24/java-hashmap.html

[2] 【JAVA】HashMap的負載因子為什麼是0.75 https://segmentfault.com/a/1190000023308658

[3] What is the significance of load factor in HashMap? https://stackoverflow.com/questions/10901752/what-is-the-significance-of-load-factor-in-hashmap/10901821#10901821

[4]散列表、全域散列與完全散列 https://zhuanlan.zhihu.com/p/300827204

[5] SUHA https://en.wikipedia.org/wiki/SUHA_(computer_science)

[6] 算法第四版