在[深入淺出集合Map]中,已講述了HashMap在jdk7中實現,在此就不再細說了

JDK7中的HashMap

基於鏈表+數組實現,底層維護一個Entry數組

Entry<K,V>[] table;

根據計算的hashCode將對應的KV鍵值對存儲到該table中，一旦發生hashCode衝突，那麼就會將該KV鍵值對放到對應的已有元素的後面， 此時，形成了一個鏈表式的存儲結構,如下圖

JDK8中的HashMap

基於位桶+鏈表/紅黑樹的方式實現,底層維護一個Node數組

Node<K,V>[] table;

在JDK7中HashMap,當成百上千個節點在hash時發生碰撞，存儲一個鏈表中，那麼如果要查找其中一個節點，那就不可避免的花費O(N)的查找時間，這將是多麼大的性能損失,這個問題終於在JDK8中得到了解決。

JDK8中,HashMap採用的是位桶+鏈表/紅黑樹的方式,當鏈表的存儲的數據個數大於等於8的時候，不再採用鏈表存儲，而採用了紅黑樹存儲結構。這是JDK7與JDK8中HashMap實現的最大區別。 如下圖所示：

這麼做主要是再查詢的時間複雜度上進行優化，鏈表為O(n)，而紅黑樹一直是O(logn)，衝突（即為相同的hash值存儲的元素個數） 超過8個，可以大大的提高查找性能。

其他異同

共同點

1.容量(capacity):容量為底層數組的長度,JDK7中為Entry數組,JDK8中為Node數組 a. 容量一定為2的次冪

static int indexFor(int h, int length) { return h & (length-1); }

這段代碼是用來計算出鍵值對存放在一個數組的索引,h是int hash = hash(key.hashCode())計算出來的,SUN大師們發現, 「當容量一定是2^n時，h & (length - 1) == h % length」 ,按位運算特別快 。 源碼中大量使用運算，對於計算機,位運算計算效率特別快，畢竟二進位纔是親兒子呀

b. 默認初始容量16(容量為低層數組的長度,JDK7中為Entry數組,JDK8中為Node數組)

c.最大容量1<<30,即2的30次方

1 << 30 = 10737418241 << 31 = -21474836481 << 32 = 11 << 33 = 21 << -1 = -2147483648

hashmap的「最大容量「其實是Integer.MAX_VALUE

2.載入因子(Load factor)：HashMap在其容量自動增加前可達到多滿的一種尺度 a. 默認載入因子 = 0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f

  • 載入因子越大、填滿的元素越多 = 空間利用率高、但衝突的機會加大、查找效率變低（因為鏈表變長了）
  • 載入因子越小、填滿的元素越少 = 空間利用率小、衝突的機會減小、查找效率高（鏈表不長） 0.75是一個"衝突的機會"與"空間利用率"之間尋找一種平衡與折衷的選擇

3.擴容機制：擴容時resize(2 * table.length)，擴容到原數組長度的2倍。

4.key為null:若key == null，則hash(key) = 0，則將該鍵-值 存放到數組table 中的第1個位置，即table [0]

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

不同點

1.發生hash衝突時 JDK7:發生hash衝突時，新元素插入到鏈表頭中，即新元素總是添加到數組中，就元素移動到鏈表中。 JDK8：發生hash衝突後，會優先判斷該節點的數據結構式是紅黑樹還是鏈表，如果是紅黑樹，則在紅黑樹中插入數據；如果是鏈表，則將數據插入到鏈表的尾部並判斷鏈表長度是否大於8，如果大於8要轉成紅黑樹。

2.擴容時 JDK7:在擴容resize（）過程中，採用單鏈表的頭插入方式，在將舊數組上的數據 轉移到 新數組上時，轉移操作 = 按舊鏈表的正序遍歷鏈表、在新鏈表的頭部依次插入，即在轉移數據、擴容後，容易出現鏈表逆序的情況 。 多線程下resize()容易出現死循環。此時若（多線程）並發執行 put（）操作，一旦出現擴容情況，則 容易出現 環形鏈表，從而在獲取數據、遍歷鏈表時 形成死循環（Infinite Loop），即 死鎖的狀態 。

JDK8:由於 JDK 1.8 轉移數據操作 = 按舊鏈表的正序遍歷鏈表、在新鏈表的尾部依次插入，所以不會出現鏈表 逆序、倒置的情況，故不容易出現環形鏈表的情況 ，但jdk1.8仍是線程不安全的，因為沒有加同步鎖保護。

建議: 1.使用時設置初始值,避免多次擴容的性能消耗 2.使用自定義對象作為key時,需要重寫hashCode和equals方法 3.多線程下,使用CurrentHashMap代替HashMap

推薦閱讀:

「深入淺出」集合Map

javaWeb傳收參數方式總結

週末了,笑久一點~

如果覺得不錯，請給個「好看」

分享給你的朋友！

THANDKS

  • End -

一個立志成大腿而每天努力奮鬥的年輕人

伴學習伴成長，成長之路你並不孤單!

推薦閱讀：

相關文章