我說(shuō)我了解集合類，面試官竟然問(wèn)我為啥HashMap的負(fù)載因子不設(shè)置成1??？
在Java基礎(chǔ)中，集合類是很關(guān)鍵的一塊知識(shí)點(diǎn)，也是日常開(kāi)發(fā)的時(shí)候經(jīng)常會(huì)用到的。比如List、Map這些在代碼中也是很常見(jiàn)的。
個(gè)人認(rèn)為，關(guān)于HashMap的實(shí)現(xiàn)，JDK的工程師其實(shí)是做了很多優(yōu)化的，要說(shuō)所有的JDK源碼中，哪個(gè)類埋的彩蛋最多，那我想HashMap至少可以排前五。
也正是因?yàn)槿绱?，很多?xì)節(jié)都容易被忽視，今天我們就來(lái)關(guān)注其中一個(gè)問(wèn)題，那就是：
為什么HashMap的負(fù)載因子設(shè)置成0.75，而不是1也不是0.5?這背后到底有什么考慮?
大家千萬(wàn)不要小看這個(gè)問(wèn)題，因?yàn)樨?fù)載因子是HashMap中很重要的一個(gè)概念，也是高端面試的一個(gè)?？键c(diǎn)。
另外，這個(gè)值得設(shè)置，有些人會(huì)用錯(cuò)的，比如前幾天我的《阿里巴巴Java開(kāi)發(fā)手冊(cè)建議創(chuàng)建HashMap時(shí)設(shè)置初始化容量，但是多少合適呢?》這篇文章中，就有讀者這樣回復(fù)：
既然有人會(huì)嘗試著去修改負(fù)載因子，那么到底改成1是不是合適呢?為什么HashMap不使用1作為負(fù)載因子的默認(rèn)值呢?
什么是loadFactor
首先我們來(lái)介紹下什么是負(fù)載因子(loadFactor)，如果讀者對(duì)這部分已經(jīng)有了解，那么可以直接跨過(guò)這一段。
我們知道，第一次創(chuàng)建HashMap的時(shí)候，就會(huì)指定其容量(如果未明確指定，默認(rèn)是16，詳見(jiàn)為啥HashMap的默認(rèn)容量是16?)，那隨著我們不斷的向HashMap中put元素的時(shí)候，就有可能會(huì)超過(guò)其容量，那么就需要有一個(gè)擴(kuò)容機(jī)制。
所謂擴(kuò)容，就是擴(kuò)大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中添加元素過(guò)程中，如果 元素個(gè)數(shù)(size)超過(guò)臨界值(threshold) 的時(shí)候，就會(huì)進(jìn)行自動(dòng)擴(kuò)容(resize)，并且，在擴(kuò)容之后，還需要對(duì)HashMap中原有元素進(jìn)行rehash，即將原來(lái)桶中的元素重新分配到新的桶中。
在HashMap中，臨界值(threshold) = 負(fù)載因子(loadFactor) * 容量(capacity)。
loadFactor是裝載因子，表示HashMap滿的程度，默認(rèn)值為0.75f，也就是說(shuō)默認(rèn)情況下，當(dāng)HashMap中元素個(gè)數(shù)達(dá)到了容量的3/4的時(shí)候就會(huì)進(jìn)行自動(dòng)擴(kuò)容。(詳見(jiàn)HashMap中傻傻分不清楚的那些概念)
為什么要擴(kuò)容
還記得前面我們說(shuō)過(guò)，HashMap在擴(kuò)容到過(guò)程中不僅要對(duì)其容量進(jìn)行擴(kuò)充，還需要進(jìn)行rehash!所以，這個(gè)過(guò)程其實(shí)是很耗時(shí)的，并且Map中元素越多越耗時(shí)。
rehash的過(guò)程相當(dāng)于對(duì)其中所有的元素重新做一遍hash，重新計(jì)算要分配到那個(gè)桶中。
那么，有沒(méi)有人想過(guò)一個(gè)問(wèn)題，既然這么麻煩，為啥要擴(kuò)容?HashMap不是一個(gè)數(shù)組鏈表嗎?不擴(kuò)容的話，也是可以無(wú)限存儲(chǔ)的呀。為啥要擴(kuò)容?
這其實(shí)和哈希碰撞有關(guān)。
哈希碰撞
我們知道，HashMap其實(shí)是底層基于哈希函數(shù)實(shí)現(xiàn)的，但是哈希函數(shù)都有如下一個(gè)基本特性：根據(jù)同一哈希函數(shù)計(jì)算出的哈希值如果不同，那么輸入值肯定也不同。但是，根據(jù)同一哈希函數(shù)計(jì)算出的哈希值如果相同，輸入值不一定相同。
兩個(gè)不同的輸入值，根據(jù)同一哈希函數(shù)計(jì)算出的哈希值相同的現(xiàn)象叫做碰撞。
衡量一個(gè)哈希函數(shù)的好壞的重要指標(biāo)就是發(fā)生碰撞的概率以及發(fā)生碰撞的解決方案。
而為了解決哈希碰撞，有很多辦法，其中比較常見(jiàn)的就是鏈地址法，這也是HashMap采用的方法。詳見(jiàn)全網(wǎng)把Map中的hash()分析的最透徹的文章，別無(wú)二家。
HashMap將數(shù)組和鏈表組合在一起，發(fā)揮了兩者的優(yōu)勢(shì)，我們可以將其理解為鏈表的數(shù)組。
HashMap基于鏈表的數(shù)組的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的。
我們?cè)谙騂ashMap中put元素的時(shí)候，就需要先定位到是數(shù)組中的哪條鏈表，然后把這個(gè)元素掛在這個(gè)鏈表的后面。
當(dāng)我們從HashMap中g(shù)et元素的時(shí)候，也是需要定位到是數(shù)組中的哪條鏈表，然后再逐一遍歷鏈表中的元素，直到查找到需要的元素為止。
但是，如果一個(gè)HashMap中沖突太高，那么數(shù)組的鏈表就會(huì)退化為鏈表。這時(shí)候查詢速度會(huì)大大降低。
所以，為了保證HashMap的讀取的速度，我們需要想辦法盡量保證HashMap的沖突不要太高。
擴(kuò)容避免哈希碰撞
那么如何能有效的避免哈希碰撞呢?
我們先反向思維一下，你認(rèn)為什么情況會(huì)導(dǎo)致HashMap的哈希碰撞比較多?
無(wú)外乎兩種情況：
1、容量太小。容量小，碰撞的概率就高了。狼多肉少，就會(huì)發(fā)生爭(zhēng)搶。
2、hash算法不夠好。算法不合理，就可能都分到同一個(gè)或幾個(gè)桶中。分配不均，也會(huì)發(fā)生爭(zhēng)搶。
所以，解決HashMap中的哈希碰撞也是從這兩方面入手。
這兩點(diǎn)在HashMap中都有很好的體現(xiàn)。兩種方法相結(jié)合，在合適的時(shí)候擴(kuò)大數(shù)組容量，再通過(guò)一個(gè)合適的hash算法計(jì)算元素分配到哪個(gè)數(shù)組中，就可以大大的減少?zèng)_突的概率。就能避免查詢效率低下的問(wèn)題。
為什么默認(rèn)loadFactor是0.75
至此，我們知道了loadFactor是HashMap中的一個(gè)重要概念，他表示這個(gè)HashMap最大的滿的程度。
為了避免哈希碰撞，HashMap需要在合適的時(shí)候進(jìn)行擴(kuò)容。那就是當(dāng)其中的元素個(gè)數(shù)達(dá)到臨界值的時(shí)候，而這個(gè)臨界值前面說(shuō)過(guò)和loadFactor有關(guān)，換句話說(shuō)，設(shè)置一個(gè)合理的loadFactor，可以有效的避免哈希沖突。
那么，到底loadFactor設(shè)置成多少算合適呢?
這個(gè)值現(xiàn)在在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).
大概意思是：一般來(lái)說(shuō)，默認(rèn)的負(fù)載因子(0.75)在時(shí)間和空間成本之間提供了很好的權(quán)衡。更高的值減少了空間開(kāi)銷，但增加了查找成本(反映在HashMap類的大多數(shù)操作中，包括get和put)。
試想一下，如果我們把負(fù)載因子設(shè)置成1，容量使用默認(rèn)初始值16，那么表示一個(gè)HashMap需要在"滿了"之后才會(huì)進(jìn)行擴(kuò)容。
那么在HashMap中，最好的情況是這16個(gè)元素通過(guò)hash算法之后分別落到了16個(gè)不同的桶中，否則就必然發(fā)生哈希碰撞。而且隨著元素越多，哈希碰撞的概率越大，查找速度也會(huì)越低。
0.75的數(shù)學(xué)依據(jù)
另外，我們可以通過(guò)一種數(shù)學(xué)思維來(lái)計(jì)算下這個(gè)值是多少合適。
我們假設(shè)一個(gè)bucket空和非空的概率為0.5，我們用s表示容量，n表示已添加元素個(gè)數(shù)。
用s表示添加的鍵的大小和n個(gè)鍵的數(shù)目。根據(jù)二項(xiàng)式定理，桶為空的概率為:
P(0) = C(n, 0) * (1/s)^0 * (1 - 1/s)^(n - 0)
因此，如果桶中元素個(gè)數(shù)小于以下數(shù)值，則桶可能是空的：
log(2)/log(s/(s - 1))
當(dāng)s趨于無(wú)窮大時(shí)，如果增加的鍵的數(shù)量使P(0) = 0.5，那么n/s很快趨近于log(2):
log(2) ~ 0.693...
所以，合理值大概在0.7左右。
當(dāng)然，這個(gè)數(shù)學(xué)計(jì)算方法，并不是在Java的官方文檔中體現(xiàn)的，我們也無(wú)從考察到底有沒(méi)有這層考慮，就像我們根本不知道魯迅寫(xiě)文章時(shí)候怎么想的一樣，只能推測(cè)。這個(gè)推測(cè)來(lái)源于Stack Overflow(https://stackoverflow.com/questions/10901752/what-is-the-significance-of-load-factor-in-hashmap)
0.75的必然因素
理論上我們認(rèn)為負(fù)載因子不能太大，不然會(huì)導(dǎo)致大量的哈希沖突，也不能太小，那樣會(huì)浪費(fèi)空間。
通過(guò)一個(gè)數(shù)學(xué)推理，測(cè)算出這個(gè)數(shù)值在0.7左右是比較合理的。
那么，為什么最終選定了0.75呢?
還記得前面我們提到過(guò)一個(gè)公式嗎，就是臨界值(threshold) = 負(fù)載因子(loadFactor) * 容量(capacity)。
我們?cè)凇稙樯禜ashMap的默認(rèn)容量是16?》中介紹過(guò)，根據(jù)HashMap的擴(kuò)容機(jī)制，他會(huì)保證capacity的值永遠(yuǎn)都是2的冪。
那么，為了保證負(fù)載因子(loadFactor) * 容量(capacity)的結(jié)果是一個(gè)整數(shù)，這個(gè)值是0.75(3/4)比較合理，因?yàn)檫@個(gè)數(shù)和任何2的冪乘積結(jié)果都是整數(shù)。
總結(jié)
HashMap是一種K-V結(jié)構(gòu)，為了提升其查詢及插入的速度，底層采用了鏈表的數(shù)組這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的。
但是因?yàn)樵谟?jì)算元素所在的位置的時(shí)候，需要使用hash算法，而HashMap采用的hash算法就是鏈地址法。這種方法有兩個(gè)極端。
如果HashMap中哈希沖突概率高，那么HashMap就會(huì)退化成鏈表(不是真的退化，而是操作上像是直接操作鏈表)，而我們知道，鏈表最大的缺點(diǎn)就是查詢速度比較慢，他需要從表頭開(kāi)始逐一遍歷。
所以，為了避免HashMap發(fā)生大量的哈希沖突，所以需要在適當(dāng)?shù)臅r(shí)候?qū)ζ溥M(jìn)行擴(kuò)容。
而擴(kuò)容的條件是元素個(gè)數(shù)達(dá)到臨界值時(shí)。HashMap中臨界值的計(jì)算方法：
臨界值(threshold) = 負(fù)載因子(loadFactor) * 容量(capacity)
其中負(fù)載因子表示一個(gè)數(shù)組可以達(dá)到的最大的滿的程度。這個(gè)值不宜太大，也不宜太小。
loadFactor太大，比如等于1，那么就會(huì)有很高的哈希沖突的概率，會(huì)大大降低查詢速度。
loadFactor太小，比如等于0.5，那么頻繁擴(kuò)容沒(méi)，就會(huì)大大浪費(fèi)空間。
所以，這個(gè)值需要介于0.5和1之間。根據(jù)數(shù)學(xué)公式推算。
這個(gè)值在log(2)的時(shí)候比較合理。
另外，為了提升擴(kuò)容效率，HashMap的容量(capacity)有一個(gè)固定的要求，那就是一定是2的冪。
所以，如果loadFactor是3/4的話，那么和capacity的乘積結(jié)果就可以是一個(gè)整數(shù)。
所以，一般情況下，我們不建議修改loadFactor的值，除非特殊原因。
比如我明確的知道我的Map只存5個(gè)kv，并且永遠(yuǎn)不會(huì)改變，那么可以考慮指定loadFactor。
但是其實(shí)我也不建議這樣用。
我們完全可以通過(guò)指定capacity達(dá)到這樣的目的。
詳見(jiàn)阿里巴巴Java開(kāi)發(fā)手冊(cè)建議創(chuàng)建HashMap時(shí)設(shè)置初始化容量，但是多少合適呢?
