[数据结构与算法]图解JDK7中HashMap扩容时会产生环形链表的原因

HashMap中扩容时转移数据的方法

• transfer方法：

扩容时就是调用这个方法来转移数据的

void transfer(Entry[] newTable, boolean rehash) {
	int newCapacity = newTable.length;
	for (Entry<K,V> e : table) {//直接遍历table变量
		//链表跟table[i]断裂遍历，头部往后遍历插入到newTable中
		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;
		}
	}
}

单线程扩容转移数据

注意：如果是单线程扩容，是不会出现环形链表的，步骤如下图：

假设扩容前HashMap容量为4，扩容后为8

• 第一步：
  
• 第二步：e.next = newTable[i];
  
• 第三步： newTable[i] = e;
  
• 第四步：e = next;
  
• 通过上面的步骤，第一个数据转移完毕，下面是第二个：
  
• 第三个数据转移：
  

通过上面的分析可以看出，单线程的数据转移是没有为题的，但是多线程下面就不一样了。

多线程扩容转移数据

假设有两个线程进行可扩容，举个极端的例子，就像数学中的反证法一样，只要有一种情况能出现，就是线程不安全的。

• 线程1执行到这里，被线程2占用
  
• 线程2完成转移完成
  
• 线程1获得执行权，接着之前的执行，完成第一个数据转移
  
• 完成二个数据转移，
  
• 完成第三个数据转移，问题来了，出来一个环形链表。
  

总结

我举的是一个比较极端的例子，也就是在扩容的时候，整个链表都被完整的转移过来了，一般情况下是不会整条链表都转移过来，会被分散，这也是扩容的目的，使之前密集分布的数据散开。

虽然是个极端的例子，但还是有出现的概率的。

JDK7中多线程下对HashMap的扩容可能会形成环形链表