JDK1.8 对 HashMap 的优化

详细的解释 ↓
Java 8系列之重新认识HashMap
Java源码分析：关于 HashMap 1.8 的重大更新

• 由 数组+链表 的结构改为 数组+链表+红黑树 。
  拉链过长会严重影响hashmap的性能，所以1.8的hashmap引入了红黑树。
  在链表元素数量超过8时改为红黑树，少于6时改为链表，中间7不改是避免频繁转换降低性能。
  相对于链表，改为红黑树后碰撞元素越多查询效率越高。链表O(n)，红黑树O(logn)。
• 优化了高位运算的hash算法：h^(h>>>16)
  将hashcode无符号右移16位，让高16位和低16位进行异或。
• 扩容后，元素要么是在原位置，要么是在原位置再移动2次幂的位置，且链表顺序不变。
  不需要重新计算hash，只需要根据原来hash值新增的bit是1还是0分别放进两个链表lo和hi（非红黑树的情况）里，0的话索引没变，1的话索引变为原索引加原来的数组长度。
  因为用的尾插法所以新数组链表不会倒置，多线程下不会出现死循环。

42                 else if (e instanceof TreeNode)
43                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
44                 else { // 链表优化重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 方法链表头插改为尾插