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