建站
咨詢
售后
建站咨詢
新聞中心
正文
讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價值的長期合作伙伴，公司提供的服務(wù)項目有：域名與空間、虛擬主機、營銷軟件、網(wǎng)站建設(shè)、西城網(wǎng)站維護、網(wǎng)站推廣。
加載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度，它衡量的是一個散列表的空間的使用程度，負載因子越大表示散列表的裝填程度越高，反之愈小。
對于使用鏈表法的散列表來說，查找一個元素的平均時間是 O(1+a)。因此如果負載因子越大，對空間的利用更充分，然而后果是查找效率的降低;如果負載因子太小，那么散列表的數(shù)據(jù)將過于稀疏，對空間造成嚴重浪費。
如果你看過源代碼，你會發(fā)現(xiàn)在初始條件下，HashMap 在時間和空間兩者間折中選擇了 0.75
- /**
- * The load factor used when none specified in constructor.
- */
- static final float DEFAULT_LOAD_FACTOR = 0.75f;
但是為什么一定是 0.75?而不是 0.8，0.6，這里有一個非常重要的概念：泊松分布。
相信大家都學(xué)過概率論，對這個大名鼎鼎的定律感覺應(yīng)該是既熟悉又陌生。本篇文章的重點不是為大家普及概率論知識，這里就簡單介紹下。
泊松分布是最重要的離散分布之一，它多出現(xiàn)在當X表示在一定的時間或空間內(nèi)出現(xiàn)的事件個數(shù)這種場合。
舉個簡單的例子，假如你一個老板，新開張了一家酒店，這個時候應(yīng)該如何準備一天所用的食材呢?
準備的太多，最后賣不掉這么多菜只能浪費扔掉;準備不夠，又接不了生意。但是你有很多同行和朋友，他們會告訴你很多經(jīng)驗。
比如把一天分成幾個時間段，上午、下午、晚上每個時間段大概會來多少個客人，每一桌大概會點幾個菜。綜合下來，就可以大致知道在一天的時間內(nèi)，估計出需要準備的食材數(shù)量。
我們接下來看看 HashMap 源碼注釋的原話：
Ideally, under random hashCodes, the frequency of nodes in bins follows a 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: 0.60653066 |
| 1: 0.30326533 |
| 2: 0.07581633 |
| 3: 0.01263606 |
| 4: 0.00157952 |
|
5: 0.0001579 |
|
6: 0.00001316 |
|
7: 0.00000094 |
|
8: 0.00000006 |
|
more: less than 1 in ten million |
翻譯過來說的是，在理想情況下,使用隨機哈希碼，節(jié)點出現(xiàn)的頻率在 hash 桶中遵循泊松分布。
對照桶中元素個數(shù)和概率的表，可以看到當用 0.75 作為加載因子時，桶中元素到達 8 個的時候，概率已經(jīng)變得非常小，因此每個碰撞位置的鏈表長度超過 8 個是幾乎不可能的，因此在鏈表節(jié)點到達 8 時才開始轉(zhuǎn)化為紅黑樹。
本文轉(zhuǎn)載自微信公眾號「程序員大帝」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系程序員大帝公眾號。
當前文章：HashMap加載因子為什么是0.75？轉(zhuǎn)化紅黑樹閾值為8？
文章出自：http://www.5511xx.com/article/dpgojhe.html
