JDK1.8开始HashMap为什么要先插入后扩容,网上查找有说先扩容再插入可以少遍历之类的,其实不管是先扩容还是先插入,它的原则还是尾插法都是避免不了要遍历的,那它为什么还是要先插入呢，只要看插入逻辑和扩充逻辑做了哪些操作就知道了,以下也 只是个人的理解,如有错误欢迎指点
首先看下JDK1.8 HashMap插入的源码
1:插入操作如果数组中的节点是红黑树是往节点中插入节点, 如果是链表的时候可能会要从链表升级成红黑树,似乎先插入再扩容还是先扩容后插入都是没影响的都是要遍历, 那问题原因就在扩容机制里
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)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);
/**
* 这里要满足当前链表的长度>=7，遍历是从根节点开始,因此相当于包括根节点有8个时再插入就会调用此方法
*/
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
2:再看看扩容的源码中有个关键的代码((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
扩容的时候如果红黑树节点的个数<=6个时,就会降级成链表了
HashMap为何将红黑树降级链表的阈值设置成6而不是7, 就是防止节点在红黑树与链表之间因插入扩容而频繁的转变,频繁的转变是要消耗性能,而插入时的操作中将红黑树变成链表的触发条件就是扩容
下面就举例频繁转变临界点的情况 ,根据频繁转变临界点的情况对比来说明原因,假设插入的节点刚好都在当前的链表或者红黑树的索引位置上
临界点情形一
假设当前插入节点是红黑树结构有7个, 如果先扩容后会有1个节点移到别的index索引时,导致当前红黑树的节点变成6个就会降级成链表再插入变成7个节点的链表。
而如果是先插入的话就是8个节点红黑树,然后扩容即使有1个节点移到别的位置也还是7个节点也不会转变成链表
临界点情形二
和情形一逻辑相反的情况,如果当前插入节点为8个且为链表的时候,如果先扩容后会有1个节点移到别的index索引时再插入还是8个节点链表不会变红黑树,而如果是先插入就会变成红黑树再扩容有1节点移动时变成8个节点的红黑树,如果此时移除节点又有可能降成链表,先分析下移除节点时降链表条件的源码
//这是移除时的部分源码
if (root == null || root.right == null || (rl = root.left) == null || rl.left == null) {
tab[index] = first.untreeify(map); // too small
return;
}
可以看出在移除节点的时候不一定是6个节点就会导致红黑树降级成链表,根据红黑树的特点有可能当前链表 3 <= Nodes <=6时才会降级成链表
这里也给一个模拟HashMap造出红黑树的测试代码,红黑树为7个节点的时候,从64扩容到128时导致了key为64的节点移到第64的索引中去,而红黑树就变成了链表了
public static void main(String[] args) {
//默认64个大小hashMap,只要数组长度>=64, 且链表 》=8时时才会转红黑树
HashMap<Integer, String> map = new HashMap<>(64);
map.put(0, "王二麻子 0");
map.put(64, "王二麻子 1");
map.put(128, "王二麻子 2");
map.put(256, "王二麻子 3");
map.put(512, "王二麻子 4");
map.put(1024, "王二麻子 5");
map.put(2048, "王二麻子 6");
map.put(4096, "王二麻子 7");
map.put(8192, "王二麻子 8");
//以上步骤就会生成在第0的索引上的一个9个节点的红黑树结构
map.remove(8192);
map.remove(4096);
//移除二个后此时是一个有7个节点的红黑树
//这一步添加41个其他位置上的节点,只要不在0节点上就行,让节点总数达到 64*0.75 = 48个
for (int i = 1; i <= 41; i++) {
map.put(i, "张三 " + i);
}
//插入第49个时触发扩容,此后红黑树结构就变成链表结构了
map.put(42, "李四");
}
