（一）HashMap系列：負載因子0.75
（二）HashMap系列：樹化閥值8，退化閥值6
（三）HashMap系列：2次方擴容
（四）HashMap系列：put元素（不看完將后悔一生６塾颉）
紅黑樹系列：
一释牺、《算法—深入淺出》N叉樹的介紹
二罪针、《算法—深入淺出》紅黑樹的旋轉(zhuǎn)
三、《算法—深入淺出》紅黑樹的插入
四、《算法—深入淺出》紅黑樹的刪除
一拂酣、前言
HashMap在JDK7與JDK8有些不同，主要是在 hash 沖突后比原，數(shù)據(jù)結(jié)構(gòu)的改變：
- JDK7：數(shù)組 + 單鏈表插佛；
- JDK8：數(shù)組 + 單鏈表 + 紅黑樹；
本篇的主題是負載因子（0.75）量窘，因此是針對數(shù)組來分析雇寇，為何是0.75這個值！
二蚌铜、負載因子的作用
在HashMap中锨侯，所有的對象都存儲在類型為 Node 的變量名為 table 的數(shù)組中：
transient Node<K,V>[] table;
該數(shù)組初始大小（capacity = 16）冬殃。
當 hash(key) 算出來的值囚痴，與已存在的發(fā)生沖突時，會在沖突的結(jié)點后添加新的結(jié)點审葬，此時就變成了鏈表深滚。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
每個 Node 對象初始時的 next 為 null ，只有在沖突時耳璧，next 才會指向下一個相同 hash(key) 但 key 不同的新的 Node 對象成箫。
當鏈表長度超過 8 時，將轉(zhuǎn)成『紅黑樹』旨枯；當『紅黑樹』的個數(shù)低于 6 時蹬昌，會重新轉(zhuǎn)化為鏈表；
隨著 table 中的數(shù)據(jù)越來越多攀隔，沖突會越來越頻繁皂贩，就會影響 HashMap 的執(zhí)行效率，無非時間或者空間昆汹，那到底是如何影響的呢明刷？
2.1、負載因子 = 1.0
負載因子為1.0時满粗，意味著辈末，只有當 table 全部被填滿，table 才會擴容映皆；當 table 中的元素越來越多時挤聘，會出現(xiàn)大量的沖突：
- 若此時是鏈表，則查詢效率是 O(n)捅彻，即線性组去；（插入/刪除結(jié)點也要遍歷到鏈表）；
- 若此時是紅黑樹步淹，查詢效率是 O(logN)从隆，但紅黑樹的插入與刪除就異常復雜诚撵，每次都要調(diào)整樹；
因此键闺，負載因子1.0寿烟，實際是犧牲了時間，但保證了空間的利用率艾杏。
2.2韧衣、負載因子 = 0.5
負載因子為0.5時，意味著购桑，當 table 中的元素達到一半時，就發(fā)生擴容氏淑，table 容量擴大一倍：
- hash 沖突減少勃蜘；
- 鏈表長度不會很長；
- 即便鏈表長度超過8時轉(zhuǎn)成紅黑樹假残，樹的高度也不會很高缭贡；
查詢效率提高了，但這里辉懒，我們發(fā)現(xiàn)阳惹，會有大量的內(nèi)存浪費，因為數(shù)組中的個數(shù)永遠小于數(shù)組長度的一半眶俩。
因此莹汤，負載因子0.5，實際是犧牲了空間颠印，但保證了時間效率纲岭。
2.3、負載因子 = 0.75
經(jīng)過上面的分析线罕，我們發(fā)現(xiàn) [0.5 , 1.0] 對應(yīng)著 [時間極端, 空間極端]止潮，那我們就需要找一個平衡點，這個點就是合理的負載因子值钞楼。
源碼中有解釋：
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). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.
其意思為：負載因子0.75較好的平衡了時間和空間成本喇闸，因子太高增加了查詢成本。
