Java HashMap源碼學習

一 HashMap介紹

1. HashMap存儲key-value鍵值對；
2. 關鍵參數 capacity：哈希表中桶的個數 loadFactor：加載因子，表示哈希表可以多滿。數目大於capacity*loadFactor時，2倍擴容rehash；
3. 實現 jdk1.7：數組+鏈表 jdk1.8：數組+鏈表/紅黑樹（鏈表長於8時變為紅黑樹,紅黑樹小時變為鏈表）
   

二 HashMap主要函數實現

1）put

• jdk1.7 添加節點時，插入鏈表頭部； void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); }
• jdk1.8 鏈表添加節點時，插入鏈表尾部； Node e; K k; // 節點key存在，直接覆蓋value if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) //判斷該鏈為紅黑樹 e = ((TreeNode)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); //鏈表長度大於8轉換為紅黑樹進行處理 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // key已經存在直接覆蓋value if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //新節點插入最後 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; }

2）擴容

• jdk1.7：對於每個key-value重新哈希計算位置，注意插入鏈表頭部，鏈表被反轉； void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry e : table) { while(null != e) { Entry next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } }

jdk1.7擴容例圖.png

• JDK1.8：計算哈希位置優化 由於是2倍擴容，只需要考慮對應增長的這一位是0還是1,如果是0桶的位置不變化，如果是1桶的位置+oldCapcity； 因此不需要每一個重新計算哈希值
  
  final Node[] resize() { ... Node[] newTab = (Node[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node 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)e).split(this, newTab, j, oldCap); else { // preserve order Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; do { next = e.next; if ((e.hash & oldCap) == 0) { // 桶index不變化 if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { // 桶index變化 if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { //不變化的部分 loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { //變化的部分 hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }

3）安全性問題

1. JDK1.7實現，多線程重哈希會導致循環鏈表問題。 疫苗：JAVA HASHMAP的死循環 原因在於：rehash時，node節點會插入鏈表頭部 do { Entry next = e.next; //
   線程1恢復繼續執行，產生循環鏈表；
   
2. JDK1.8實現，我認為不會出現循環鏈表的問題，多線程不安全是肯定的； JDK1.8桶中鏈表的順序會維持，因此不會出現1.7中後節點移到前節點的前邊，循環鏈表的風險。 //某個桶裡的鏈表處理過程： Node loHead = null, loTail = null; //桶號不變，存一個鏈表 Node hiHead = null, hiTail = null;//桶號改變，存另一個鏈表 Node next;do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } //直接將兩個鏈表分別放入新桶 while((e=next)!=null);if(loTail!=null) { loTail.next = null; newTab[j] = loHead; }if(hiTail!=null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }

關注我，私信回覆“資料”獲取更多學習資料spring，MyBatis，Netty源碼分析，高併發、高性能、分佈式、微服務架構

閱讀更多 java互聯網高級架構 的文章

關鍵字: 源碼 學習 Java