问题出现条件
- JDK1.7及以下版本
- 并发使用HashMap
- HashMap发生resize（扩容）
总结成一句话，有多个线程并发向该HashMap中添加hash冲突的元素，直至HashMap发生扩容。
HashMap初始容量
首先我们看HashMap的3种构造方法（JDK1.7）：
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
参数说明：
| 参数名 | 说明 | 默认值 |
|---|---|---|
| initialCapacity | HashMap的初始容量 | 2^4=16 |
| loadFactor | 负载因子 | 0.75f |
我们常用的Map<K,V> map = new HashMap<>();其实是第3个构造方法，从该构造方法上方的注释可以看出，initialCapacity默认是16，loadFactor默认是0.75f。从HashMap的静态变量也可找到对应值：
那loadFactor到底有什么用呢？请往下看。
HashMap何时扩容
扩容肯定发生在HashMap的塞不下的情况下，那这里面的玄机肯定藏在put方法里面：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
我们看到几个关键的方法：
| 方法 | 说明 |
|---|---|
hash() |
计算Key的hash值 |
indexFor() |
计算Value在数组中存放的下标位置 |
addEntry() |
执行插入操作 |
乍一看没有扩容相关的代码，其实是在倒数第二行的addEntry()方法里面(其他两个方法的分析)：
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
我们看到，如果HashMap当前size >= threshod ，且数组当前位置不为null时，会进行扩容！
其中resize(2 * table.length)可以看出，每次扩容为原来容量的2倍。
我们再来看resize()方法：
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);
}
我们看到，关键步骤为倒数3行和倒数1行：
- 步骤1.
transfer()方法把当前数组转换为扩容后的新数组，大小就是入参传进来的，是原来大小的2倍； - 步骤2. 重新计算
threhold，（新容量*负载因子）与（最大容量+1）两个值取小；
对于步骤2，我们引申一下：我们看构造方法中，threhold = initialCapacity。可能大家会有疑问，说好的负载因子呢？其实在构造方法中，尚未对HashMap进行初始化，即还没有正真去创建桶。在put方法中，我们看到了inflateTable(threshold);方法，这才是初始化Map的方法，有兴趣的同学可以去研究一下。为了尽量避免resize，当你知道你最多会往HashMap塞N个对象的时候，一开始就申请N个容量的HashMap，内部会自动帮你计算转换成2的倍数。（为什么是2的倍数）。
HashMap扩容时数组转换(头插法)
接下来就是扩容的重头戏——transfer()方法：
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;
}
}
}
我们可以看到，该算法有两个主要步骤：
（TODO 什么时候需要rehash）
- 把当前节点的next指向链表的起始位置（即数组的下标
i的地址）：e.next = newTable[i]; - 把当前节点赋值给链表起始位置：
newTable[i] = e;
该算法会倒转整个链表的顺序。这也是会出现死循环的根本原因！
下面我们举个例子并结合图例来说明：
-
假设我们有一个HashMap
初始容量为4，目前已有3个冲突元素a,b,c在一条链上，那么该HashMap结构如下图：
-
在非并发情况下，继续put一个冲突元素d，则会发生resize，具体步骤如下图：
我们看到，transfer方法会把原有链表顺序倒过来，这就是jdk1.7使用的头插法。
上面的例子演示的是正常情况下，resize方法执行后，HashMap内的结构。
下面我们看并发时候为什么会出现死循环：
并发下的tranfer方法
假设我们有一个HashMap初始容量为4，目前已有3个冲突元素a,b,c在一条链上，有两个线程 T1 与 T2同时往该HashMap中插入元素。那么这个时候，两个线程同时对此HashMap执行了tranfer方法。
我们假设T2先执行到中间状态：
此状态是for循环第一次，变量e指向抵一个节点c，变量next指向e.next 也就是b，但是节点的next指向尚未发生任何改变。
这时T1也开始：
这与上文正常的transfer方法执行结果是相同的，即把链表顺序倒转。
此时线程T2继续执行transfer方法，for循环的第二次：
由于T1改变了b.next ,使得b.next指向了c；此时继续执行transfer方法，则会得到如下状态：
上图这个结构其实已经产生了死循环的条件了——a的下个节点是b，而b的下个节点是a，产生了一个环形链表。
此时当我们get一个此链表的元素的时候，会用equals方法遍历判断链表元素是否一致，遍历结束条件是next为null，而环形链表会导致遍历永远无法结束，即发生了死循环！
总结
以上分析基于JDK1.7，所幸的是JDK1.8已经修复了此问题，transfer方法由头插法改为尾插法，从根源上杜绝了这种情况的发生。但是如果要在并发情况下使用Map的话，建议使用Concurrent包下的，支持并发的容器类。
网友评论