詳細的解釋 ↓
Java 8系列之重新認識HashMap
Java源碼分析：關(guān)于 HashMap 1.8 的重大更新

• 由 數(shù)組+鏈表 的結(jié)構(gòu)改為 數(shù)組+鏈表+紅黑樹 。
  拉鏈過長會嚴重影響hashmap的性能，所以1.8的hashmap引入了紅黑樹。
  在鏈表元素數(shù)量超過8時改為紅黑樹，少于6時改為鏈表，中間7不改是避免頻繁轉(zhuǎn)換降低性能。
  相對于鏈表，改為紅黑樹后碰撞元素越多查詢效率越高。鏈表O(n)，紅黑樹O(logn)。
• 優(yōu)化了高位運算的hash算法：h^(h>>>16)
  將hashcode無符號右移16位，讓高16位和低16位進行異或。
• 擴容后，元素要么是在原位置，要么是在原位置再移動2次冪的位置，且鏈表順序不變。
  不需要重新計算hash，只需要根據(jù)原來hash值新增的bit是1還是0分別放進兩個鏈表lo和hi（非紅黑樹的情況）里，0的話索引沒變，1的話索引變?yōu)樵饕釉瓉淼臄?shù)組長度。
  因為用的尾插法所以新數(shù)組鏈表不會倒置，多線程下不會出現(xiàn)死循環(huán)。

42                 else if (e instanceof TreeNode)
43                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
44                 else { // 鏈表優(yōu)化重hash的代碼塊
45                     Node<K,V> loHead = null, loTail = null;
46                     Node<K,V> hiHead = null, hiTail = null;
47                     Node<K,V> next;
48                     do {
49                         next = e.next;
50                         // 原索引
51                         if ((e.hash & oldCap) == 0) {
52                             if (loTail == null)
53                                 loHead = e;
54                             else
55                                 loTail.next = e;
56                             loTail = e;
57                         }
58                         // 原索引+oldCap
59                         else {
60                             if (hiTail == null)
61                                 hiHead = e;
62                             else
63                                 hiTail.next = e;
64                             hiTail = e;
65                         }
66                     } while ((e = next) != null);
67                     // 原索引放到bucket里
68                     if (loTail != null) {
69                         loTail.next = null;
70                         newTab[j] = loHead;
71                     }
72                     // 原索引+oldCap放到bucket里
73                     if (hiTail != null) {
74                         hiTail.next = null;
75                         newTab[j + oldCap] = hiHead;
76                     }
77                 }

• put 方法鏈表頭插改為尾插