在 Java 基礎(chǔ)中购啄，集合類是很關(guān)鍵的一塊知識點襟企，也是日常開發(fā)的時候經(jīng)常會用到的。比如 List狮含、Map 這些在代碼中也是很常見的顽悼。
個人認為，關(guān)于 HashMap 的實現(xiàn)几迄，JDK 的工程師其實是做了很多優(yōu)化的蔚龙，要說所有的 JDK 源碼中，哪個類埋的彩蛋最多映胁，那我想 HashMap 至少可以排前五木羹。
也正是因為如此，很多細節(jié)都容易被忽視解孙，今天我們就來關(guān)注其中一個問題坑填，那就是：
為什么 HashMap 的負載因子設(shè)置成 0.75，而不是 1 也不是 0.5弛姜？****這背后到底有什么考慮脐瑰？
大家千萬不要小看這個問題，因為負載因子是 HashMap 中很重要的一個概念廷臼，也是高端面試的一個巢栽冢考點。
1. 什么是 loadFactor
首先我們來介紹下什么是負載因子（loadFactor）荠商，如果讀者對這部分已經(jīng)有了解寂恬，那么可以直接跨過這一段。
我們知道莱没，第一次創(chuàng)建 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 中添加元素過程中，如果 元素個數(shù)（size）超過臨界值（threshold） 的時候盯拱，就會進行自動擴容（resize）盒发，并且，在擴容之后狡逢，還需要對 HashMap 中原有元素進行 rehash宁舰，即將原來桶中的元素重新分配到新的桶中。
在 HashMap 中奢浑，臨界值（threshold） = 負載因子（loadFactor） * 容量（capacity）蛮艰。
loadFactor 是裝載因子，表示 HashMap 滿的程度雀彼，默認值為 0.75f壤蚜，也就是說默認情況下，當 HashMap 中元素個數(shù)達到了容量的 3/4 的時候就會進行自動擴容徊哑。
2. 為什么要擴容
還記得前面我們說過袜刷，HashMap 在擴容到過程中不僅要對其容量進行擴充，還需要進行 rehash莺丑！所以著蟹，這個過程其實是很耗時的，并且 Map 中元素越多越耗時梢莽。
rehash 的過程相當于對其中所有的元素重新做一遍 hash萧豆，重新計算要分配到那個桶中。
那么蟹漓，有沒有人想過一個問題炕横，既然這么麻煩，為啥要擴容葡粒？HashMap 不是一個數(shù)組鏈表嗎份殿？不擴容的話，也是可以無限存儲的呀嗽交。為啥要擴容卿嘲？
這其實和哈希碰撞有關(guān)！夫壁！
哈希碰撞：
我們知道拾枣，HashMap 其實是底層基于哈希函數(shù)實現(xiàn)的，但是哈希函數(shù)都有如下一個基本特性：根據(jù)同一哈希函數(shù)計算出的哈希值如果不同，那么輸入值肯定也不同梅肤。但是司蔬，根據(jù)同一哈希函數(shù)計算出的哈希值如果相同，輸入值不一定相同姨蝴。
兩個不同的輸入值俊啼，根據(jù)同一哈希函數(shù)計算出的哈希值相同的現(xiàn)象叫做碰撞。
衡量一個哈希函數(shù)的好壞的重要指標就是發(fā)生碰撞的概率以及發(fā)生碰撞的解決方案左医。
而為了解決哈希碰撞授帕，有很多辦法，其中比較常見的就是鏈地址法浮梢，這也是 HashMap 采用的方法跛十。
HashMap 將數(shù)組和鏈表組合在一起，發(fā)揮了兩者的優(yōu)勢秕硝，我們可以將其理解為鏈表的數(shù)組芥映。
HashMap 基于鏈表的數(shù)組的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的。
我們在向 HashMap 中 put 元素的時候缝裤，就需要先定位到是數(shù)組中的哪條鏈表屏轰，然后把這個元素掛在這個鏈表的后面颊郎。
當我們從 HashMap 中 get 元素的時候憋飞，也是需要定位到是數(shù)組中的哪條鏈表，然后再逐一遍歷鏈表中的元素姆吭，直到查找到需要的元素為止榛做。
但是，如果一個 HashMap 中沖突太高内狸，那么數(shù)組的鏈表就會退化為鏈表检眯。這時候查詢速度會大大降低。
所以昆淡，為了保證 HashMap 的讀取的速度锰瘸，我們需要想辦法盡量保證 HashMap 的沖突不要太高。
擴容避免哈希碰撞
那么如何能有效的避免哈希碰撞呢昂灵？
我們先反向思維一下避凝，你認為什么情況會導(dǎo)致 HashMap 的哈希碰撞比較多？
無外乎兩種情況：
1眨补、容量太小管削。容量小，碰撞的概率就高了撑螺。狼多肉少含思，就會發(fā)生爭搶。
2、hash 算法不夠好含潘。算法不合理饲做，就可能都分到同一個或幾個桶中。分配不均遏弱，也會發(fā)生爭搶艇炎。
所以，解決 HashMap 中的哈希碰撞也是從這兩方面入手腾窝。
這兩點在 HashMap 中都有很好的體現(xiàn)缀踪。兩種方法相結(jié)合，在合適的時候擴大數(shù)組容量虹脯，再通過一個合適的 hash 算法計算元素分配到哪個數(shù)組中驴娃，就可以大大的減少沖突的概率，就能避免查詢效率低下的問題循集。
3. 為什么默認 loadFactor 是 0.75
解釋了這么多唇敞，我們終于回歸到了標題上的問題。
至此咒彤，我們知道了 loadFactor 是 HashMap 中的一個重要概念疆柔，他表示這個 HashMap 最大的滿的程度。
為了避免哈希碰撞镶柱，HashMap 需要在合適的時候進行擴容旷档。那就是當其中的元素個數(shù)達到臨界值的時候，而這個臨界值前面說過和 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).
大概意思是：一般來說，默認的負載因子 (0.75) 在時間和空間成本之間提供了很好的權(quán)衡罚缕。更高的值減少了空間開銷艇纺，但增加了查找成本(反映在 HashMap 類的大多數(shù)操作中，包括 get 和 put)。
試想一下黔衡，如果我們把負載因子設(shè)置成 1蚓聘，容量使用默認初始值 16，那么表示一個 HashMap 需要在 "滿了" 之后才會進行擴容盟劫。
那么在 HashMap 中夜牡，最好的情況是這 16 個元素通過 hash 算法之后分別落到了 16 個不同的桶中，否則就必然發(fā)生哈希碰撞侣签。而且隨著元素越多塘装，哈希碰撞的概率越大，查找速度也會越低影所。
4. 0.75 的數(shù)學(xué)依據(jù)和必然性
理論上我們認為負載因子不能太大蹦肴，不然會導(dǎo)致大量的哈希沖突，也不能太小猴娩，那樣會浪費空間阴幌。
通過一個數(shù)學(xué)推理 log(2)/log(s/(s - 1)) ，當 s 趨于無窮大時卷中，如果增加的鍵的數(shù)量使 P(0) = 0.5矛双，那么 n/s 很快趨近于 log(2)，測算出這個數(shù)值在 log(2)（即：0.7 左右）時是比較合理的蟆豫。
當然议忽，這個數(shù)學(xué)計算方法，并不是在 Java 的官方文檔中體現(xiàn)的无埃，而是查詢了一些資料習(xí)得徙瓶，所以也無從考證毛雇，只做參考了嫉称。
那么，為什么最終選定了 0.75 呢灵疮？
還記得前面我們提到過一個公式嗎织阅，就是：臨界值（threshold） = 負載因子（loadFactor） * 容量（capacity）。
根據(jù) HashMap 的擴容機制震捣，它會保證 capacity 的值永遠都是 2 的冪荔棉；
那么，為了保證負載因子（loadFactor） * 容量（capacity）的結(jié)果是一個整數(shù)蒿赢，這個值是 0.75(3/4) 比較合理润樱，因為這個數(shù)和任何 2 的冪乘積結(jié)果都是整數(shù)。
5. 總結(jié)（非常重要）
HashMap 是一種 K-V 結(jié)構(gòu)羡棵，為了提升其查詢及插入的速度壹若，底層采用了鏈表的數(shù)組這種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的。
但是因為在計算元素所在的位置的時候，需要使用 hash 算法店展，而 HashMap 采用的 hash 算法就是鏈地址法养篓。這種方法有兩個極端。
如果 HashMap 中哈希沖突概率高赂蕴，那么 HashMap 就會退化成鏈表（不是真的退化柳弄，而是操作上像是直接操作鏈表），而我們知道概说，鏈表最大的缺點就是查詢速度比較慢碧注，他需要從表頭開始逐一遍歷。
所以糖赔，為了避免 HashMap 發(fā)生大量的哈希沖突应闯，所以需要在適當?shù)臅r候?qū)ζ溥M行擴容。
而擴容的條件是元素個數(shù)達到臨界值時挂捻。
HashMap 中臨界值的計算方法：
臨界值（threshold） = 負載因子（loadFactor） * 容量（capacity）
其中負載因子表示一個數(shù)組可以達到的最大的滿的程度碉纺。這個值不宜太大，也不宜太小刻撒。
loadFactor 太大骨田，比如等于 1，那么就會有很高的哈希沖突的概率声怔，會大大降低查詢速度态贤。
loadFactor 太小，比如等于 0.5醋火，那么頻繁擴容沒悠汽，就會大大浪費空間。
所以芥驳，這個值需要介于 0.5 和 1 之間柿冲。根據(jù)數(shù)學(xué)公式推算。這個值在 log(2) 的時候比較合理兆旬。
另外假抄，為了提升擴容效率，HashMap 的容量（capacity）有一個固定的要求丽猬，那就是一定是 2 的冪宿饱。
所以，如果 loadFactor 是 3/4 的話脚祟，那么和 capacity 的乘積結(jié)果就可以是一個整數(shù)谬以。
最后，一般情況下由桌，我們不建議修改 loadFactor 的值为黎，除非特殊原因胡陪。
