之前的文章已经分析了HashMap在JDK1.7的实现,这篇文章就只分析HashMap死循环形成的原因
死循环形成是在扩容转移元素的时候发生的
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
发生的具体时机在transfer函数中,默认情况下rehash为 false
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
正常的transfer过程
例子不考虑扩容 阈值 ,假设放4个元素时开始扩容
主要有2个有意思的地方
当跑完这次循环时key7被放入线程1的table中,e指向key3,next指向null
e不为null,还能再次执行循环,key3再次插入线程1中table[3]的头节点,此时e变为null,循环完毕。结构如下
环形链表形成,此时无论将线程1还是线程2的table设置为newTable,当调用get方法执行到这条链上时,死循环形成。
关注私信【555】获取面试视频,还可领取更多Java面试题资料