Jdk1.8 在实现HashMap时，在涉及到数组扩容之后需要原数组中的元素复制到新的数组时，jdk 1.7是再给每一个节点的做一次hash运算，而jdk1.8 是采用效率更高的与预算来保证正式的效果。
需要准备的代码，其中 AA0,AA20,AA31,AA42这个key经过hash运算之后正好能够保证都是落在一个坑位的。
public static void main(String[] args) {
Map<String,String> singleMap = new HashMap<>();
singleMap.put("AA0","BBBB");
singleMap.put("AA20","BBBB");
singleMap.put("AA31","BBBB");
singleMap.put("AA42","BBBB");
for(int i=1;i<12;i++){
singleMap.put("AA"+i,"BBBB");
}
}
当HashMap中节点数超过预设值threshold时，需要扩容和将旧数组中的元素复制到新数组中去。具体代码如下resize()数组复制的代码：
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
解析实现流程：
1遍历旧的数组发现坑位为0的位置节点不为空，而且当前节点的下一个节点也不为空，创建四个空的节点分别为loHead,loTail,hiHead,hiTail.
2.jpg
2 遍历坑位为0的节点链表，判断：链表的第一节点的hash&oldLength！=0(原数组长度)时，而且hiTail为空时。将当前节点赋值给hiHead,和hiTail.
3.jpg
3 遍历链表的第二个节点的hash&oldLength==0,而且loTail为空时，将当前节点赋值个loHead和loTail
4.jpg
4 遍历链表的第三个节点hash&oldLength==0时，hiTail不为空，将当前节点赋值给hiTail.next和hiTail
5.jpg
5 遍历链表的第四个节点hash&oldLength==0时，hiTail不为空，将当前节点赋值给hiTail.next和hiTail
6.jpg
6 链表遍历完成之后，判断loTail!=null时，需要将整个loHead节点挂到新数组的0坑位。
7.jpg
7 判断hiTail!=null时，需要将整个hiHead节点挂接到新数组的0+oldLength坑位
8.jpg
新数组坑位确定的逻辑：
HashMap在扩容之后进行数组复制的时候为何要采用 当前节点的hash&旧数组的长度来判断节点在动态数组下标是在原来的位置还是加上扩容的长度呢？因为当前节点的hash&oldLength==0时，那么节点在新数组的坑位是不变的。确定坑位的算法如下图所示：
newTab[e.hash & (newCap - 1)] = e;
现在就举个例子证明：
假如一个节点的hash值是10100，当前节点的hash&oldLength！=0，通过hash算法计算的坑位是100.扩容之后计算的坑位是10100
当一个节点的hash值是00100时，当前节点的hash&oldLength==0，通过hash算法计算得到的坑位是100,扩容之后计算的坑位还是100.由此可见HashMap 通过节点的hash&oldLength==0的算法是有道理的。
微信图片_20190727223904.jpg
网友评论