CSDN话题挑战赛第2期
参赛话题：学习笔记
前言
JDK8里，HashMap的数据结构是由数组+链表+红黑树组成。当1oldTable[index]1的链表元素达到8个时，若再添加元素，此时会尝试转换为红黑树。但是，如果，此时数组上所有元素（包括链表、红黑树）还未达到64时，仍然只是进行数组扩容。下面，就数组扩容过程中，旧数组中元素是如何移动至新数组的过程进行推演和总结。
一、场景
当数组发生扩容时，链表中所有元素需要移动至新数组相应位置。在JDK7中，是遍历链表，依次将元素移动至新数组相应位置。而在JDK8中，是将原有链表逻辑拆分成两个链表，移动将两个链表的头节点，直接放至新数组的相应下标位置。这里的思路与JDK7中的ConcurrentHashMap相似，只是实现不一样。
二、详细步骤
1.推演过程
数组扩容以及链表拆分的核心逻辑在源码的resize()方法，下面通过LinkTest链表的示例代码模拟，如下：
public class LinkTest {
private LinkTest next;
private int value;
private int hash;
public LinkTest(int value,LinkTest next,int hash){
this.value = value;
this.next = next;
this.hash = hash;//模拟key的hash值
}
public static void main(String[] args) {
mockJDK8(generate());
}
public static LinkTest generate(){
LinkTest tail = new LinkTest(55,null,1);
LinkTest l2 = new LinkTest(44,tail,1);
LinkTest l3 = new LinkTest(33,l2,2);
LinkTest l4 = new LinkTest(22,l3,2);
LinkTest l5 = new LinkTest(11,l4,1);
return l5;
}
/**
* 模拟jdk8中HashMap数组扩容后，链表拆分及元素移动逻辑
* @param head 链表首节点
*/
public static void mockJDK8(LinkTest head){
LinkTest loHead = null, loTail = null;//链表一（低位链表），保存原 index 位置的所有元素
LinkTest hiHead = null, hiTail = null;//链表二（高位链表），保存原index + oldCapacity 位置的所有元素
LinkTest next;
LinkTest e = head;
do {//将链表拆分成2个链表，然后移动链表首元素至新扩容数组2个对应的index位置
next = e.next;
if(e.hash == 1){//模拟源码的逻辑：hash=1或不等于1
//源码：原数组长度oldCap为2的幂次方。如16: 0001 0000,所以&的结果结果要么为0，要么不为0
//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;//这一点重要，
//至此，第一个链表，即需要移动至扩容后的新数组newCap[index]的链表已形成，这里的Index就是oldCap中的位置
//newTab[j] = loHead;//源码中：移动至扩容后数组的原index位置
}
if (hiTail != null) {
hiTail.next = null;//这一点重要，如果它不是最原链表最后一个元素，那么hiHead最后一个元素必然是多出来的元素（属于loHead链表),所以要摘除
//至今，第二个链表也形成，即需要移动至扩容后的新数组newCap[index + oldCapLength]的位置
//newTab[j + oldCap] = hiHead;//源码中：移动至扩容后数组的原index + oldCapLength位置
}
StringBuffer sb2 = new StringBuffer();
LinkTest print = loHead;
while(print != null){
sb2.append(print).append(",");
print = print.next;
}
System.out.println("the original list2: " + sb2);
StringBuffer sb3 = new StringBuffer();
print = hiHead;
while(print != null){
sb3.append(print).append(",");
print = print.next;
}
System.out.println("the original list3: " + sb3);
}
public static LinkTest generate(){
//简化场景，hash值只模拟1、2
LinkTest tail = new LinkTest(55,null,1);
LinkTest l2 = new LinkTest(44,tail,2);
LinkTest l3 = new LinkTest(33,l2,1);
LinkTest l4 = new LinkTest(22,l3,2);
LinkTest l5 = new LinkTest(11,l4,1);//返回头节点
return l5;
}
}
2.代码输出
原始链表输出：
Node{value=11,hash=1, next=22},Node{value=22,hash=2, next=33},Node{value=33,hash=1, next=44},Node{value=44,hash=2, next=55},Node{value=55,hash=1, next=null}
while循环结束：
Node{value=11,hash=1, next=33},Node{value=33,hash=1, next=55},Node{value=55,hash=1, next=null}
Node{value=22,hash=2, next=44},Node{value=44,hash=2, next=55},Node{value=55,hash=1, next=null}
注意while循环结束，链表二仍然保留了Node{value=55,hash=1, next=null}元素。再详细推演一个链表二的过程：
第二次循环结束后： hiHead = hiTail = Node{value=22,hash=2, next=33}
打印hiHead链表： Node{value=22,hash=2, next=33},,Node{value=33,hash=1, next=44},Node{value=44,hash=2, next=55},Node{value=55,hash=1, next=null}
第四次循环结束后： hiHead = Node{value=22,hash=2, next=44}，Node{value=44,hash=2, next=55}
打印hiHead链表： Node{value=22,hash=2, next=44}，Node{value=44,hash=2, next=55} ,Node{value=55,hash=1, next=null}
第五次循环结束后： e = null，循环结束，链表二无变化
所以需要执行hiTail.next = null，这样就可以摘除Node{value=55,hash=1, next=null} 节点，保证链表二的正确性
图示演示过程
用图演示链表拆分过程中，低位链表形成过程:
总结
- 在JDK7中的ConcurrentHashMap也用到了链表拆分的思路，实现不一样；
- 链表拆分后，只需分别将低、高位链表的头节点，直接放至新数组的第
index、index+newTable.length位置即可完成oldTable[index]下所有链表元素的转移； - 这种拆分成2个链表的方式，移动效率相比，JDK7中HashMap逐个移动元素的方式性能会高效；