為什麼 HashMap 的加載因子是0.75？

雲栖号資訊：【 點選檢視更多行業資訊

】

在這裡您可以找到不同行業的第一手的上雲資訊，還在等什麼，快來！

有很多東西之前在學的時候沒怎麼注意，筆者也是在重溫HashMap的時候發現有很多可以去細究的問題，最終是會回歸于數學的，如HashMap的加載因子為什麼是0.75？

本文主要對以下内容進行介紹：

• 為什麼HashMap需要加載因子？
• 解決沖突有什麼方法？

• 為什麼加載因子一定是0.75？而不是0.8，0.6？

  若文章有不正之處，或難以了解的地方，請多多諒解，歡迎指正。

HashMap的底層是哈希表，是存儲鍵值對的結構類型，它需要通過一定的計算才可以确定資料在哈希表中的存儲位置：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}           

// AbstractMap

public int hashCode() {
     int h = 0;
     Iterator<Entry<K,V>> i = entrySet().iterator();
     while (i.hasNext())
         h += i.next().hashCode();

     return h;
}           

一般的資料結構，不是查詢快就是插入快，HashMap就是一個插入慢、查詢快的資料結構。

但這種資料結構容易産生兩種問題：

① 如果空間使用率高，那麼經過的雜湊演算法計算存儲位置的時候，會發現很多存儲位置已經有資料了（哈希沖突）；

② 如果為了避免發生哈希沖突，增大數組容量，就會導緻空間使用率不高。

而加載因子就是表示Hash表中元素的填滿程度。

加載因子 = 填入表中的元素個數 / 散清單的長度

加載因子越大，填滿的元素越多，空間使用率越高，但發生沖突的機會變大了；

加載因子越小，填滿的元素越少，沖突發生的機會減小，但空間浪費了更多了，而且還會提高擴容rehash操作的次數。

沖突的機會越大，說明需要查找的資料還需要通過另一個途徑查找，這樣查找的成本就越高。是以，必須在“沖突的機會”與“空間使用率”之間，尋找一種平衡與折衷。

是以我們也能知道，影響查找效率的因素主要有這幾種：

散列函數是否可以将哈希表中的資料均勻地散列？

怎麼處理沖突？

哈希表的加載因子怎麼選擇？

本文主要對後兩個問題進行介紹。

1. 開放定址法

   Hi = (H(key) + di) MOD m，其中i=1,2,…,k(k<=m-1)

H(key)為哈希函數，m為哈希表表長，di為增量序列，i為已發生沖突的次數。其中，開放定址法根據步長不同可以分為3種：

1.1 線性探查法（Linear Probing）：di = 1,2,3,…,m-1

簡單地說，就是以目前沖突位置為起點，步長為1循環查找，直到找到一個空的位置，如果循環完了都占不到位置，就說明容器已經滿了。舉個栗子，就像你在飯點去街上吃飯，挨家去看是否有位置一樣。

1.2 平方探測法（Quadratic Probing）：di = ±12, ±22，±32，…，±k2（k≤m/2）

相對于線性探查法，這就相當于的步長為di = i2來循環查找，直到找到空的位置。以上面那個例子來看，現在你不是挨家去看有沒有位置了，而是拿手機算去第i2家店，然後去問這家店有沒有位置。

1.3 僞随機探測法：di = 僞随機數序列

這個就是取随機數來作為步長。還是用上面的例子，這次就是完全按心情去選一家店問有沒有位置了。

但開放定址法有這些缺點：

這種方法建立起來的哈希表，當沖突多的時候資料容易堆集在一起，這時候對查找不友好；

删除結點的時候不能簡單将結點的空間置空，否則将截斷在它填入散清單之後的同義詞結點查找路徑。是以如果要删除結點，隻能在被删結點上添加删除标記，而不能真正删除結點；

如果哈希表的空間已經滿了，還需要建立一個溢出表，來存入多出來的元素。

1. 再哈希法

   Hi = RHi(key), 其中i=1,2,…,k

RHi()函數是不同于H()的哈希函數，用于同義詞發生位址沖突時，計算出另一個哈希函數位址，直到不發生沖突位置。這種方法不容易産生堆集，但是會增加計算時間。

是以再哈希法的缺點是：

增加了計算時間。

1. 建立一個公共溢出區

   假設哈希函數的值域為[0, m-1]，設向量HashTable[0,…,m-1]為基本表，每個分量存放一個記錄，另外還設定了向量OverTable[0,…,v]為溢出表。基本表中存儲的是關鍵字的記錄，一旦發生沖突，不管他們哈希函數得到的哈希位址是什麼，都填入溢出表。

但這個方法的缺點在于：

查找沖突資料的時候，需要周遊溢出表才能得到資料。

1. 鍊位址法（拉鍊法）

   将沖突位置的元素構造成連結清單。在添加資料的時候，如果哈希位址與哈希表上的元素沖突，就放在這個位置的連結清單上。

拉鍊法的優點：

處理沖突的方式簡單，且無堆集現象，非同義詞絕不會發生沖突，是以平均查找長度較短；

由于拉鍊法中各連結清單上的結點空間是動态申請的，是以它更适合造表前無法确定表長的情況；

删除結點操作易于實作，隻要簡單地删除連結清單上的相應的結點即可。

拉鍊法的缺點：

需要額外的存儲空間。

從HashMap的底層結構中我們可以看到，HashMap采用是數組+連結清單/紅黑樹的組合來作為底層結構，也就是開放位址法+鍊位址法的方式來實作HashMap。

至于為什麼在JDK1.8的時候要運用到紅黑樹，下篇文章會介紹。關注微信公衆号：網際網路架構師，在背景回複：2T，可以擷取架構師全套教程，都是幹貨。

為什麼HashMap加載因子一定是0.75？而不是0.8，0.6？

從上文我們知道，HashMap的底層其實也是哈希表（散清單），而解決沖突的方式是鍊位址法。HashMap的初始容量大小預設是16，為了減少沖突發生的機率，當HashMap的數組長度到達一個臨界值的時候，就會觸發擴容，把所有元素rehash之後再放在擴容後的容器中，這是一個相當耗時的操作。

而這個臨界值就是由加載因子和目前容器的容量大小來确定的：

臨界值 = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR

即預設情況下是16x0.75=12時，就會觸發擴容操作。

那麼為什麼選擇了0.75作為HashMap的加載因子呢？筆者不才，通過看源碼解釋和大佬的文章，才知道這個跟一個統計學裡很重要的原理——泊松分布有關。

泊松分布是統計學和機率學常見的離散機率分布，适用于描述機關時間内随機事件發生的次數的機率分布。

等号的左邊，P 表示機率，N表示某種函數關系，t 表示時間，n 表示數量。等号的右邊，λ 表示事件的頻率。

在HashMap的源碼中有這麼一段注釋：

* 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)). 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的情況下，節點出現在頻率在Hash桶（表）中遵循參數平均為0.5的泊松分布。忽略方差，即X = λt，P(λt = k)，其中λt = 0.5的情況，按公式：

計算結果如上述的清單所示，當一個bin中的連結清單長度達到8個元素的時候，機率為0.00000006，幾乎是一個不可能事件。

是以我們可以知道，其實常數0.5是作為參數代入泊松分布來計算的，而加載因子0.75是作為一個條件，當HashMap長度為length/size ≥ 0.75時就擴容，在這個條件下，沖突後的拉鍊長度和機率結果為：

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           

那麼為什麼不可以是0.8或者0.6呢？

HashMap中除了雜湊演算法之外，有兩個參數影響了性能：初始容量和加載因子。初始容量是哈希表在建立時的容量，加載因子是哈希表在其容量自動擴容之前可以達到多滿的一種度量。

在維基百科來描述加載因子：

對于開放定址法，加載因子是特别重要因素，應嚴格限制在0.7-0.8以下。超過0.8，查表時的CPU緩存不命中（cache missing）按照指數曲線上升。是以，一些采用開放定址法的hash庫，如Java的系統庫限制了加載因子為0.75，超過此值将resize散清單。

在設定初始容量時應該考慮到映射中所需的條目數及其加載因子，以便最大限度地減少擴容rehash操作次數，是以，一般在使用HashMap時建議根據預估值設定初始容量，以便減少擴容操作。

選擇0.75作為預設的加載因子，完全是時間和空間成本上尋求的一種折衷選擇。

結語

曾經有一堆高數、線性代數、離散數學擺在我面前，但是我沒有珍惜。等到碰到各種數學問題的時候，才後悔莫及。學計算機的時候最痛苦的事，莫過于此。如果老天可以再給我一個，再來一次的機會的話。我會跟當時的我，說三個字——“學數學！”

數學真的太重要。離開大學之後，該怎麼學數學啊，有什麼好的建議嗎？

如果本文對你有幫助，請給一個贊吧，這會是我最大的動力~

【雲栖号線上課堂】每天都有産品技術專家分享！

課程位址：

https://yqh.aliyun.com/zhibo

立即加入社群，與專家面對面，及時了解課程最新動态！

【雲栖号線上課堂 社群】

https://c.tb.cn/F3.Z8gvnK

原文釋出時間：2020-06-08

本文作者： 網際網路架構師

本文來自：“

網際網路架構師 微信公衆号

”，了解相關資訊可以關注“

網際網路架構師

”