HashMap1.7與1.8的區別
1）1.7底層：陣列+鏈表；1.8：陣列+鏈表+紅黑樹
2）1.7：頭插法；1.8：尾插法
ps:HashMap在jdk1.7中采用頭插入法，在擴容時會改變鏈表中元素原本的順序，以至于在并發場景下可能導致鏈表成環，在進行下次put操作的時候程式會陷入死回圈，而在jdk1.8中采用尾插入法，在擴容時會保持鏈表元素原本的順序，就不會出現鏈表成環的問題了，
3）1.7：先擴容后插入；1.8：先插入后擴容
4）1.7：計算hash運算多；1.8：計算hash運算少
JDK1.8以后的hashmap為什么在鏈表長度為8的時候變為紅黑樹，以及為啥使用紅黑樹
1）為啥不直接使用紅黑樹，反而要加上鏈表了？
因為樹節點所占空間差不多是普通節點的兩倍，所以只有當節點足夠多的時候，才會使用樹節點，也就是說，節點少的時候，盡管時間復雜度上，紅黑樹比鏈表好一點，但是紅黑樹所占空間比較大，綜合考慮，認為只能在節點太多的時候，紅黑樹占空間大這一劣勢不太明顯的時候，才會舍棄鏈表，使用紅黑樹，
2）為啥8以后就選擇紅黑樹
鏈表轉紅黑樹本身就是一種性能開銷，選擇為8的話應該是避免頻繁的轉換，在jdk原始碼中有說明，一個哈希桶上鏈表長度為8的概率大約為1億分之8，可見概率很低，這樣就避免了頻繁地轉化
3）既然概率低為啥還要在底層實作鏈表轉紅黑樹的操作
事實上，鏈表長度超過 8 就轉為紅黑樹的設計，更多的是為了防止用戶自己實作了不好的哈希演算法時導致鏈表過長，從而導致查詢效率低，而此時轉為紅黑樹更多的是一種保底策略，用來保證極端情況下查詢的效率，
HashMap擴容機制
jdk1.7:
1）創建物件時會初始化一個空陣列
2）先擴容后添加元素
3）擴容的條件（滿足以下兩個）
1、存放新值的時候當前已有元素的個數必須大于等于閾值
2、 存放新值的時候當前存放資料發生hash碰撞（當前key計算的hash值換算出來的陣列下標位置已經存在值，好處在于可以保證資料結構更簡單）
jdk1.8:
1）創建物件時不會初始化hash表，會在第一次進行.put（）方法進行初始化
2）先添加元素后擴容++size>threshold
3）擴容的條件（滿足其中一個就行）：
1、當map實際數量大于threshold容量的閾值時，會進行兩倍擴容，
2、當map中陣列中某個桶的鏈表長度大于樹形化閾值TREEIFY_THRESHOLD=8時，
并且map元素的數量小于樹形化最小容量MIN_TREEIFY_CAPACITY=64時候，容量進行兩倍擴容，（其實就是用擴容代替鏈表轉紅黑樹操作）
HashMap初始容量注意事項：
1）當使用無參構造方法時，默認容量為16
2）當使用有參構造方法時，其容量為大于你傳入的數字的最小的2的n次冪（最小1，2的0次冪，傳入0容量就是1）
HashMap容量為啥定義為2的n次冪
只要陣列大小是2的冪，則 (n-1) & hash 的結果等效于： hash % (n-1)；即與運算、求余運算通過這個前提，實作了等效，通過將質數參與到hash運算中可以提高資料插入后的分散性，降低hash沖突發生的概率
HashMap鏈表轉紅黑樹，紅黑樹轉鏈表
static final int TREEIFY_THRESHOLD = 8; 鏈表轉紅黑樹的閾值
static final int UNTREEIFY_THRESHOLD = 6; 紅黑樹轉鏈表的閾值
static final int MIN_TREEIFY_CAPACITY = 64; 鏈表轉紅黑樹所需達到的最小容量
當鏈表需要轉紅黑樹時如果此時map容量沒有達到64會用擴容操作來代替轉化操作
總結：
1）hashMap并不是在鏈表元素個數大于8就一定會轉換為紅黑樹，而是先考慮擴容，擴容達到默認限制后才轉換
2）hashMap的紅黑樹不一定小于等于6的時候就會轉換為鏈表，而是只有在resize的時候才會根據 UNTREEIFY_THRESHOLD 進行轉換
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/258933.html
標籤：java