JDK1.8 对 HashMap 的优化
2018-06-01 本文已影响0人
pluss
详细的解释 ↓
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 方法链表头插改为尾插
