本文為轉貼: HaspMap源碼分析(JDK 1.8)
作者:zuckerbergJu2.0
鏈接:https://juejin.im/post/5a7719456fb9a0633e51ae14
HashMap是我們在編程中遇到極其頻繁、非常重要的一個集合類,如果能對HashMap做進一步的性能優化是非常有價值的而JDK 1.8做到了,所以非常有必要學習HashMap的重點源碼,瞭解大師的手法。
二、底層數據結構
畫圖真的是個累活,好的畫圖工具很重要啊,上面這兩張圖分別畫出了JDK 1.7、1.8底層數據結構,在JDK 1.7、1.8中都使用
那為什麼不將鏈表全部換成二叉樹呢?這裡主要有兩個方面。
數組+鏈表+紅黑樹的結構不一定比數組+鏈表的結構性能高。
3.1 類結構
上圖是HashMap的類結構,大家看看有個概念
3.2 類注釋
我建議大家在讀源碼時可以先看看類注釋,往往類注釋會給我們一些重要的信息,這裡LZ給大家總結一下。
(1)允許NULL值,NULL鍵
(2)不要輕易改變負載因子,負載因子過高會導致鏈表過長,查找鍵值對時間複雜度就會增高,負載因子過低會導致hash桶的 數量過多,空間複雜度會增高
(3)Hash表每次會擴容長度為以前的2倍
(4)HashMap是多線程不安全的,我在JDK1.7進行多線程put操作,之後遍歷,直接死循環,CPU飆到100%,在JDK 1.8中進行多線程操作會出現節點和value值丟失,為什麼JDK1.7與JDK1.8多線程操作會出現很大不同,是因為JDK 1.8的作者對resize方法進行了優化不會產生鏈表閉環。這也是本章的重點之一,具體的細節大家可以去查閱資料。這裡我就不解釋太多了
(5)盡量設置HashMap的初始容量,尤其在數據量大的時候,防止多次resize
3.3 類常量
//默認hash桶初始長度16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//hash表最大容量2的30次冪 static final int MAXIMUM_CAPACITY = 1 << 30;
//默認負載因子 0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f;
//鏈表的數量大於等於8個並且桶的數量大於等於64時鏈表樹化 static final int TREEIFY_THRESHOLD = 8;
//hash表某個節點鏈表的數量小於等於6時樹拆分 static final int UNTREEIFY_THRESHOLD = 6;
//樹化時最小桶的數量 static final int MIN_TREEIFY_CAPACITY = 64;
3.4 實例變數
//hash桶 transient Node<K,V>[] table;
//鍵值對的數量 transient int size;
//HashMap結構修改的次數 transient int modCount;
//擴容的閥值,當鍵值對的數量超過這個閥值會產生擴容 int threshold;
//負載因子 final float loadFactor;
3.5 構造函數
public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; //下面介紹一下這行代碼的作用 this.threshold = tableSizeFor(initialCapacity); }
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }
public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }
HashMap有4個構造函數。
hash桶沒有在構造函數中初始化,而是在第一次存儲鍵值對的時候進行初始化。 這裡重點看下tableSizeFor(initialCapacity)方法,這個方法的作用是,將你傳入的initialCapacity做計算,返回一個大於等於initialCapacity 最小的2的冪次方。
所以這個操作保證無論你傳入的初始化Hash桶長度參數是多少,最後hash表初始化的長度都是2的冪次方。比如你輸入的是6,計算出來結果就是8。
下面貼出源碼。
static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
3.6 插入
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //當table為空時,這裡初始化table,不是通過構造函數初始化,而是在插入時通過擴容初始化,有效防止了初始化HashMap沒有數據插入造成空間浪費可能造成內存泄露的情況 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //存放新鍵值對 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; //舊鍵值對的覆蓋 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //在紅黑樹中查找舊鍵值對更新 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //將新鍵值對放在鏈表的最後 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //當鏈表的長度大於等於樹化閥值,並且hash桶的長度大於等於MIN_TREEIFY_CAPACITY,鏈錶轉化為紅黑樹 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //鏈表中包含鍵值對 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //map中含有舊key,返回舊值 if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } //map調整次數加1 ++modCount; //鍵值對的數量達到閾值需要擴容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
HashMap插入跟我們平時使用時的感覺差不多,下面總結一下。
(1)插入的鍵值對是新鍵值對,如果hash表沒有初始化會進行初始化,否則將鍵值對插入鏈表尾部,可能需要鏈表樹化和
(2)插入的鍵值對中的key已經存在,更新鍵值對在put的方法裏我們注意看下hash(key)方法,這是計算鍵值對hash值的方法,下面給出源碼
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
hashCode()是一個int類型的本地方法,也就將key的hashCode無符號右移16位然後與hashCode異或從而得到hash值在putVal方法中(n - 1)& hash計算得到桶的索引位置 ,那麼現在有兩個疑問,為什麼要計算hash值?為什麼不用 hash % n?
上圖 hash&(n - 1)的結果是2,而其實hash%n 的結果也是2, hash&(n - 1)與hash%n的結果是等價的。
3.7 擴容
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; //如果舊hash桶不為空 if (oldCap > 0) { //超過hash桶的最大長度,將閥值設為最大值 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //新的hash桶的長度2被擴容沒有超過最大長度,將新容量閥值擴容為以前的2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } //如果hash表閾值已經初始化過 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; //如果舊hash桶,並且hash桶容量閾值沒有初始化,那麼需要初始化新的hash桶的容量和新容量閥值 else { newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //新的局部變數閥值賦值 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //為當前容量閥值賦值 threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) //初始化hash桶 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; //如果舊的hash桶不為空,需要將舊的hash表裡的鍵值對重新映射到新的hash桶中 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; //只有一個節點,通過索引位置直接映射 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; //如果是紅黑樹,需要進行樹拆分然後映射 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { //如果是多個節點的鏈表,將原鏈表拆分為兩個鏈表,兩個鏈表的索引位置,一個為原索引,一個為原索引加上舊Hash桶長度的偏移量 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; //鏈表1 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } //鏈表2 else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); //鏈表1存於原索引 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } //鏈表2存於原索引加上原hash桶長度的偏移量 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
那麼什麼時候回產生擴容呢?
(1)初始化HashMap時,第一次進行put操作
(2)當鍵值對的個數大於threshold閥值時產生擴容,threshold=size*loadFactor
上面就是HashMap擴容的源代碼,我已經加上了注釋,相信大家都能看懂了。總結一下,HaspMap擴容就是就是先計算新的hash表容量和新的容量閥值,然後初始化一個新的hash表,將舊的鍵值對重新映射在新的hash表裡。這裡實現的細節當然沒有我說的那麼簡單,如果在舊的hash表裡涉及到紅黑樹,那麼在映射到新的hash表中還涉及到紅黑樹的拆分。
在擴容的源代碼中作者有一個使用很巧妙的地方,是鍵值對分佈更均勻,不知道讀者是否有看出來。在遍歷原hash桶時的一個鏈表時,因為擴容後長度為原hash表的2倍,假設把擴容後的hash表分為兩半,分為低位和高位,如果能把原鏈表的鍵值對, 一半放在低位,一半放在高位,這樣的索引效率是最高的。那看看源碼裏是怎樣寫的。大師通過e.hash & oldCap == 0來判斷, 這和e.hash & (oldCap - 1) 有什麼區別呢。下面我通過畫圖來解釋一下。
因為n是2的整次冪,二進位表示除了最高位為1外,其他低位全為0,那麼e.hash & oldCap 是否等於0,取決於n對應最高位. 相對於e.hash那一位是0還是1,比如說n = 16,二進位為10000,第5位為1,e.hash & oldCap 是否等於0就取決於e.hash第5
其實,到這裡基本上HashMap的核心內容都講完了,相信大家對HashMap的源碼有一定了解了。在源碼中還有鍵值對的查詢和刪除都比較簡單,這裡就不在過多贅述了,對於紅黑樹的構造、旋轉、著色,我覺得大家有興趣可以瞭解一下,畢竟我們不
3.8 清除
本來到這裡就要結束了,但是LZ還是想跟大家聊一下HashMap總的clear()方法,下面貼出源碼。
public void clear() { Node<K,V>[] tab; modCount++; if ((tab = table) != null && size > 0) { size = 0; for (int i = 0; i < tab.length; ++i) tab[i] = null; } }
HashMap其實這段代碼特別簡單,為什麼貼出來呢,是因為我在看過別的博客裏產生過疑問,到底是clear好還是新建一個HashMap好。我認為clear()比新建一個HashMap好。下面從空間複雜度和時間複雜度來解釋一下。
從時間角度來看,這個循環是非常簡單無複雜邏輯,並不十分耗資源。而新建一HashMap,首先他在在堆內存中年輕代中查看是否有足夠空間能夠存儲,如果能夠存儲,那麼創建順利完成,但如果HashMap非常大,年輕代很難有足夠的空間存儲,如果老年代中有足夠空間存儲這個HashMap,那麼jvm會將HashMap直接存儲在老年代中,如果老年代中空間不夠,這時候會觸發一次minor gc,會產生小規模的gc停頓,如果發生minor gc之後仍不能存儲HashMap,那麼會發生整個堆的gc,也就是full gc,這個gc停頓是很恐怖的。實際上的gc順序就是這樣的,並且可能發生多次minor gc和full gc,如果發現年輕代和老年代均不能存儲HashMap,那麼就會觸發OOM,而clear()是肯定不會觸發OOM的,所以數據裏特別大的情況下,千萬不要創建一個新的HashMap代替clear()方法。
從空間角度看,原HashMap雖然不用,如果數據未被清空,是不可能被jvm回收的,因為HashMap是強引用類型的,從而造成內存泄漏。所以綜上所述我
(1)HashMap允許NULL值,NULL鍵
(2)不要輕易改變負載因子,負載因子過高會導致鏈表過長,查找鍵值對時間複雜度就會增高,負載因子過低會導致hash桶的數量過多,空間複雜度會增高
(4)HashMap是多線程不安全的,我在JDK 1.7進行多線程put操作,之後遍歷,直接死循環,CPU飆到100%,在JDK 1.8中
進行多線程操作會出現節點和value值丟失,為什麼JDK1.7與JDK1.8多線程操作會出現很大不同,是因為JDK 1.8的作者對resize
(6)HashMap在JDK 1.8在做了很好性能的提升,我看到過在JDK1.7和JDK1.8get操作性能對比JDK1.8是要優於JDK 1.7的,大家感興趣的可以自己做個測試,所以還沒有升級到JDK1.8的小夥伴趕緊的吧。
總結就把類注釋的給搬過來了,其實在本篇文章中有一個知識點沒有詳細分析,就是HashMap在多線程不安全的原因,尤其擴容在JDK 1.7 會產生鏈表閉環,因為要畫很多圖,我還沒找到合適的工具,後期補充吧。