原创 | 我说我了解集合类，面试官竟然问我为啥HashMap的负载因子不设置成1！？...
△Hollis, 一個對Coding有著獨特追求的人△
這是Hollis的第?254篇原創分享
作者 l Hollis
來源 l Hollis（ID：hollischuang）
在Java基礎中，集合類是很關鍵的一塊知識點，也是日常開發的時候經常會用到的。比如List、Map這些在代碼中也是很常見的。
個人認為，關于HashMap的實現，JDK的工程師其實是做了很多優化的，要說所有的JDK源碼中，哪個類埋的彩蛋最多，那我想HashMap至少可以排前五。
也正是因為如此，很多細節都容易被忽視，今天我們就來關注其中一個問題，那就是：
為什么HashMap的負載因子設置成0.75，而不是1也不是0.5？這背后到底有什么考慮？
大家千萬不要小看這個問題，因為負載因子是HashMap中很重要的一個概念，也是高端面試的一個常考點。
另外，這個值得設置，有些人會用錯的，比如前幾天我的《阿里巴巴Java開發手冊建議創建HashMap時設置初始化容量，但是多少合適呢？》這篇文章中，就有讀者這樣回復：

既然有人會嘗試著去修改負載因子，那么到底改成1是不是合適呢？為什么HashMap不使用1作為負載因子的默認值呢？
什么是loadFactor
首先我們來介紹下什么是負載因子（loadFactor），如果讀者對這部分已經有了解，那么可以直接跨過這一段。
我們知道，第一次創建HashMap的時候，就會指定其容量（如果未明確指定，默認是16，詳見為啥HashMap的默認容量是16？），那隨著我們不斷的向HashMap中put元素的時候，就有可能會超過其容量，那么就需要有一個擴容機制。
所謂擴容，就是擴大HashMap的容量:
void addEntry(int hash, K key, V value, int bucketIndex) {if ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length);hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex); }從代碼中我們可以看到，在向HashMap中添加元素過程中，如果 元素個數（size）超過臨界值（threshold） 的時候，就會進行自動擴容（resize），并且，在擴容之后，還需要對HashMap中原有元素進行rehash，即將原來桶中的元素重新分配到新的桶中。
在HashMap中，臨界值（threshold） = 負載因子（loadFactor） * 容量（capacity）。
loadFactor是裝載因子，表示HashMap滿的程度，默認值為0.75f，也就是說默認情況下，當HashMap中元素個數達到了容量的3/4的時候就會進行自動擴容。（詳見HashMap中傻傻分不清楚的那些概念）
為什么要擴容
還記得前面我們說過，HashMap在擴容到過程中不僅要對其容量進行擴充，還需要進行rehash！所以，這個過程其實是很耗時的，并且Map中元素越多越耗時。
rehash的過程相當于對其中所有的元素重新做一遍hash，重新計算要分配到那個桶中。
那么，有沒有人想過一個問題，既然這么麻煩，為啥要擴容？HashMap不是一個數組鏈表嗎？不擴容的話，也是可以無限存儲的呀。為啥要擴容？
這其實和哈希碰撞有關。
哈希碰撞
我們知道，HashMap其實是底層基于哈希函數實現的，但是哈希函數都有如下一個基本特性：根據同一哈希函數計算出的哈希值如果不同，那么輸入值肯定也不同。但是，根據同一哈希函數計算出的哈希值如果相同，輸入值不一定相同。
兩個不同的輸入值，根據同一哈希函數計算出的哈希值相同的現象叫做碰撞。
衡量一個哈希函數的好壞的重要指標就是發生碰撞的概率以及發生碰撞的解決方案。
而為了解決哈希碰撞，有很多辦法，其中比較常見的就是鏈地址法，這也是HashMap采用的方法。詳見全網把Map中的hash()分析的最透徹的文章，別無二家。
HashMap將數組和鏈表組合在一起，發揮了兩者的優勢，我們可以將其理解為鏈表的數組。
HashMap基于鏈表的數組的數據結構實現的。
我們在向HashMap中put元素的時候，就需要先定位到是數組中的哪條鏈表，然后把這個元素掛在這個鏈表的后面。
當我們從HashMap中get元素的時候，也是需要定位到是數組中的哪條鏈表，然后再逐一遍歷鏈表中的元素，直到查找到需要的元素為止。
但是，如果一個HashMap中沖突太高，那么數組的鏈表就會退化為鏈表。這時候查詢速度會大大降低。
所以，為了保證HashMap的讀取的速度，我們需要想辦法盡量保證HashMap的沖突不要太高。
擴容避免哈希碰撞
那么如何能有效的避免哈希碰撞呢？
我們先反向思維一下，你認為什么情況會導致HashMap的哈希碰撞比較多？
無外乎兩種情況：
1、容量太小。容量小，碰撞的概率就高了。狼多肉少，就會發生爭搶。
2、hash算法不夠好。算法不合理，就可能都分到同一個或幾個桶中。分配不均，也會發生爭搶。
所以，解決HashMap中的哈希碰撞也是從這兩方面入手。
這兩點在HashMap中都有很好的體現。兩種方法相結合，在合適的時候擴大數組容量，再通過一個合適的hash算法計算元素分配到哪個數組中，就可以大大的減少沖突的概率。就能避免查詢效率低下的問題。
為什么默認loadFactor是0.75
至此，我們知道了loadFactor是HashMap中的一個重要概念，他表示這個HashMap最大的滿的程度。
為了避免哈希碰撞，HashMap需要在合適的時候進行擴容。那就是當其中的元素個數達到臨界值的時候，而這個臨界值前面說過和loadFactor有關，換句話說，設置一個合理的loadFactor，可以有效的避免哈希沖突。
那么，到底loadFactor設置成多少算合適呢？
這個值現在在JDK的源碼中是0.75:
/*** The load factor used when none specified in constructor.*/static final float DEFAULT_LOAD_FACTOR = 0.75f;那么，為什么選擇0.75呢？背后有什么考慮？為什么不是1，不是0.8？不是0.5，而是0.75呢？
在JDK的官方文檔中，有這樣一段描述描述：
As a general rule, the default load factor (.75) offers a good tradeoff between time and 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).
大概意思是：一般來說，默認的負載因子(0.75)在時間和空間成本之間提供了很好的權衡。更高的值減少了空間開銷，但增加了查找成本(反映在HashMap類的大多數操作中，包括get和put)。
試想一下，如果我們把負載因子設置成1，容量使用默認初始值16，那么表示一個HashMap需要在"滿了"之后才會進行擴容。
那么在HashMap中，最好的情況是這16個元素通過hash算法之后分別落到了16個不同的桶中，否則就必然發生哈希碰撞。而且隨著元素越多，哈希碰撞的概率越大，查找速度也會越低。
0.75的數學依據?
另外，我們可以通過一種數學思維來計算下這個值是多少合適。
我們假設一個bucket空和非空的概率為0.5，我們用s表示容量，n表示已添加元素個數。
用s表示添加的鍵的大小和n個鍵的數目。根據二項式定理，桶為空的概率為:
P(0) = C(n, 0) * (1/s)^0 * (1 - 1/s)^(n - 0)因此，如果桶中元素個數小于以下數值，則桶可能是空的：
log(2)/log(s/(s - 1))當s趨于無窮大時，如果增加的鍵的數量使P(0) = 0.5，那么n/s很快趨近于log(2):
log(2) ~ 0.693...所以，合理值大概在0.7左右。
當然，這個數學計算方法，并不是在Java的官方文檔中體現的，我們也無從考察到底有沒有這層考慮，就像我們根本不知道魯迅寫文章時候怎么想的一樣，只能推測。這個推測來源于Stack Overflow（https://stackoverflow.com/questions/10901752/what-is-the-significance-of-load-factor-in-hashmap）
0.75的必然因素
理論上我們認為負載因子不能太大，不然會導致大量的哈希沖突，也不能太小，那樣會浪費空間。
通過一個數學推理，測算出這個數值在0.7左右是比較合理的。
那么，為什么最終選定了0.75呢？
還記得前面我們提到過一個公式嗎，就是臨界值（threshold） = 負載因子（loadFactor） * 容量（capacity）。
我們在《為啥HashMap的默認容量是16？》中介紹過，根據HashMap的擴容機制，他會保證capacity的值永遠都是2的冪。
那么，為了保證負載因子（loadFactor） * 容量（capacity）的結果是一個整數，這個值是0.75(3/4)比較合理，因為這個數和任何2的冪乘積結果都是整數。
總結
HashMap是一種K-V結構，為了提升其查詢及插入的速度，底層采用了鏈表的數組這種數據結構實現的。
但是因為在計算元素所在的位置的時候，需要使用hash算法，而HashMap采用的hash算法就是鏈地址法。這種方法有兩個極端。
如果HashMap中哈希沖突概率高，那么HashMap就會退化成鏈表（不是真的退化，而是操作上像是直接操作鏈表），而我們知道，鏈表最大的缺點就是查詢速度比較慢，他需要從表頭開始逐一遍歷。
所以，為了避免HashMap發生大量的哈希沖突，所以需要在適當的時候對其進行擴容。
而擴容的條件是元素個數達到臨界值時。HashMap中臨界值的計算方法：
臨界值（threshold） = 負載因子（loadFactor） * 容量（capacity）其中負載因子表示一個數組可以達到的最大的滿的程度。這個值不宜太大，也不宜太小。
loadFactor太大，比如等于1，那么就會有很高的哈希沖突的概率，會大大降低查詢速度。
loadFactor太小，比如等于0.5，那么頻繁擴容沒，就會大大浪費空間。
所以，這個值需要介于0.5和1之間。根據數學公式推算。這個值在log(2)的時候比較合理。
另外，為了提升擴容效率，HashMap的容量（capacity）有一個固定的要求，那就是一定是2的冪。
所以，如果loadFactor是3/4的話，那么和capacity的乘積結果就可以是一個整數。
所以，一般情況下，我們不建議修改loadFactor的值，除非特殊原因。
比如我明確的知道我的Map只存5個kv，并且永遠不會改變，那么可以考慮指定loadFactor。
但是其實我也不建議這樣用。我們完全可以通過指定capacity達到這樣的目的。詳見阿里巴巴Java開發手冊建議創建HashMap時設置初始化容量，但是多少合適呢？
參考資料：
https://stackoverflow.com/questions/10901752/what-is-the-significance-of-load-factor-in-hashmap
https://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html
https://preshing.com/20110504/hash-collision-probabilities/
關于作者：Hollis，一個對Coding有著獨特追求的人，現任阿里巴巴技術專家，個人技術博主，技術文章全網閱讀量數千萬，《程序員的三門課》聯合作者。
- MORE | 更多精彩文章 -
一道大題決定去留：為什么synchronized無法禁止指令重排，卻能保證有序性？
一個技術總監的忠告：精通那么多技術為何還是做不好一個項目？
Undertow技術：為什么很多Spring Boot開發者放棄了Tomcat
這家全球最大的成人網站，保存著西方媒體最后的良心
如果你喜歡本文,
請長按二維碼，關注?Hollis.
轉發至朋友圈，是對我最大的支持。
好文章，我在看??
總結
以上是生活随笔為你收集整理的原创 | 我说我了解集合类，面试官竟然问我为啥HashMap的负载因子不设置成1！？...的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 暴力求解法 之 简单枚举
- 下一篇： 暴力求解法 之 枚举排列