核心变化
- hash 算法优化
- 链表插入改为尾插法
- 引入红黑树
hash 算法优化
旨在提升hash计算性能
- JDK1.7 扰动9次
- JDK1.8 扰动2次
// 1.7
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
// 1.8
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
链表插入改为尾插法
避免了多线程下链表成环问题
// 1.7
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
// 1.8
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
....
}
...
}
引入红黑树
在极端情况下，碰撞个数达到8时使用红黑树，查询效率从链表的 O(N) 优化为 O(logN)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash); // 构造红黑树
break;
}
