HashMap成环分析
调用put方法时,计算obj的hash值,如果该hash是一个新值则会调用addEntry新增一个结点。
addEntry方法中会先判断添加一个元素后会不会超过阀值(阀值threshold = 负载因子 × 最大容量大小
),如果超过了threshold
则会扩容,也就是执行resize
操作,resize
操作会先创造一个是原来大小2倍的新容器,然后会有一个对原来旧数据的一个迁移的过程,这个过程就是transfer
方法,接下来要说的重点点也是transfer
方法。
源码如下:
void transfer(Entry[] newTable)
{
Entry[] src = table;
intnewCapacity = newTable.length;
// 下面这段代码的意思是:
// 从OldTable里摘一个元素出来,然后放到NewTable中
for(intj = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if(e != null) {
src[j] = null;
do{
Entry<K,V> next = e.next;
inti = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}while (e != null);
}
}
}
单线程下resize:
并发情况下,线程A和线程B同时put,线程Aresize完毕,而线程B只是进入了while循环后时间片就用完了,此时B中e指向a,next指向b。
线程B进入循环的第一次,会把e指向的内容,也就是a,摘下来放到新table里,并且e和next顺延:e->b,next->a。
线程B进入循环的第二次,会把e指向的内容,现在是b,摘下来放到新table中a的前面(头插入法,作者认为后插入的元素用到的可能性会大一点),此时e->a b->a,代码会让e指向b,也就是a->b,从而a和b相互引用形成环路。
总结
jdk1.7下的hashmap采用的是头插入法,所谓的头插入,可以理解为,原来是a->b->c->null
,transfer后是c->b->a->null
,并发的情况下,有一个线程已经transfer完毕,也就是链表已经反序,另一个线程才刚开始,该线程的e和next指向的还是原来正序节点,所以会成环。
所以这也是为什么jdk8采用尾插入法避免并发的情况下成环,不过虽然jdk8避免的成环,但多线程环境下还是不能使用hashmap,因为hashmap并没有代码同步,如果一个线程put中,另一个线程get会产生脏读。并发情况下使用ConcurrentHashMap。
参考: