以下先講解HashMap
開始先簡單總結：
- HashMap在JDK8之前底層：數(shù)組 + 鏈表
- HashMap在JDK8之后底層：數(shù)組 + 鏈表 + 紅黑樹
在底層存儲的時候必定有數(shù)組，鏈表與紅黑樹是在特定情況下產(chǎn)生的。
1.HashMap底層
1.1Hash底層存儲結構
1.首先HashMap中的Key與Value是存儲在Node對象中，作為Node對象的屬性出現(xiàn)：
2.Node對象是存儲在Node數(shù)組中：
3.最重要的一點，Node存儲在數(shù)組中的模式使用的是Set集合的存儲思想：無序、不可重復
無序：在存儲到
Node[]數(shù)組的時候，并不是順序存儲，而是根據(jù)key的hash值計算得來的存儲位置。
不可重復：Key是不可重復的，為什么呢？后面會講。
現(xiàn)在我們知道了：HashMap集合Key與Value存儲在對象中，對象存儲在數(shù)組中
Key、Value --> 對象 --> 數(shù)組
如下圖：
1.2 HashMap為什么是無序的？不可重復的？
1.向HashMap中添加一組值：map.put(key, value);
-
計算hash值：這時系統(tǒng)會根據(jù)key值，調(diào)用key所在類的
hashCode()方法計算hash值
所以為什么存儲在map中的對象，需要所在類重寫hashCode()方法
-
計算index值：再根據(jù)hash值計算index
index = (length - 1) & hash(length當前底層數(shù)組的長度) index就是存儲在數(shù)組中的位置（下標）。
總結：因為Node對象存儲在數(shù)組中的位置是根據(jù)Key值計算得來，所以并不是順序存儲進去的（所以是無序的），同時因為相同的Key計算出來的index也是相同的，當Key相同時會用當前node替換原始的node，但是還是保持一個map中key值是唯一的（不可重復性）體現(xiàn)在下面源碼中：
其中 p 是新增的 node，e是原始的 node：如果hash值相同，key相同，就用新增的替換原來的
我們看到還調(diào)用了
key.equals(k), 前面的 k == key 判斷地址，后面 equals 判斷內(nèi)容，保持絕對相等
所以我們除了為什么無序、不可重復，還得出結論：存儲在HashMap中的對象需要重寫
hashCode()與equals()這兩個方法
為什么要使用hash值計算index進行無序存儲呢？當我們查找一個key對應的value的時候，就不需要順序遍歷底層數(shù)組了，直接計算index值，去對應位置拿就行。比list查找效率大大提升。而且map集合設計之初就是用來根據(jù)key取value值的存儲結構，需要承擔大量查找操作。
1.3 鏈表與紅黑樹是如何產(chǎn)生的
1.當我們添加一組值的時候，map.put(key, value);通過key的hash值計算得到的index，拿著index去數(shù)組中存儲的時候發(fā)現(xiàn)該位置已經(jīng)有數(shù)據(jù)了怎么辦？
2.那么就會先比較 hash 值，再比較 key 地址值，最后比較key的內(nèi)容是否相等，如果還是相等呢？那么node中的next屬性就派上用場了：
3.系統(tǒng)就會將當前對象node賦值給next，讓它鏈接到原始node的后面（jdk8之后是新node鏈接到原始的后面，jdk8之前是把新的對象放在數(shù)組中，把原始對象鏈接到新node的后面，總之都是形成一個單向鏈表）就形成了：數(shù)組 + 鏈表：
4.什么時候會形成紅黑樹呢？提到下面兩個關鍵的變量：
5.當鏈表長度達到8，且數(shù)組長度達到64時候就會轉換為紅黑樹進行存儲。如果鏈表長度達到8，數(shù)組長度還未小于64，就會先進性擴容。
HashMap的每一次擴容都會重新計算每個node的index，因為
index = (length - 1) & hash,index與數(shù)組長度有關。這樣也能減少鏈表與紅黑樹的出現(xiàn)。
6.所以后續(xù)就有可能形成：數(shù)組+鏈表+紅黑樹 的情況（也不排除偶然：每個計算的index都不相同，只有數(shù)組，那就太爽了）：
1.4 HashMap何時會進行擴容？
List 默認底層默認是長度為10的數(shù)組，存滿了（進來第11個元素），就擴容。
HashMap 底層默認是長度為16的數(shù)組，加載因子是0.75，也就是說存儲超過數(shù)組長度在75%也就第一次擴容是12個的時候就會進行擴容。
為什么不存儲滿了再擴容呢？因為存儲位置是計算出來的，萬一計算出來的index就是不會出現(xiàn)2，那么2這個位置永遠不會存儲元素。那就完蛋。
同時，如上面描述的也會在長度未達到64，鏈表長度就達到8的時候擴容。
現(xiàn)在我們就基本講完了HashMap的底層了。
2.LinkedHashMap
其實也就是在HashMap的基礎上增加了雙向指針，指向前一個，后一個，方便遍歷。
3.HashSet
為什么放在最后講，因為Set集合的底層就是調(diào)用了HashMap：
創(chuàng)建的時候構造器new了一個HashMap：
添加的時候調(diào)用HashMap的put方法：
只不過在一開始new了一個單例的Object作為value：
4.LinkedHashSet
實際上LinkedHashSet底層就是一個LinkedHashMap
LinkedHashSet構造器調(diào)用了HashSet中的構造器
HashSet中的這個構造器創(chuàng)建LinkedHashMap對象返回。
總結：
HashMap
默認初始化數(shù)組長度：16
擴容倍數(shù)：2倍
HashMap的默認加載因子：0.75
Bucket中鏈表長度大于該默認值，轉化為紅黑樹 : 8
桶中的Node被樹化時最小的hash表容量：64
HashMap 是大哥
LinkedHashMap 就是在 HashMap 基礎上增加雙向鏈表
HashSet 底層就是 HashMap
LinkedHashSet 底層就是 LinkedHashMap
