jdk源码分析之HashMap--并发情况下put导致死链

*以下代码分析基于jdk1.7

接着上一篇jdk源码分析之HashMap--并发情况下remove失败分析，HashMap非线程安全一般体现在删除、新增或者扩容过程中，此篇就最常用的操作之一，put方法引起扩容(resize)操作导致的死链问题做一下分析。

首先我们看一下put方法的源码：

简单对put方法所做的事情做一下描述:

1. 第一步，如果内部table是一个空数组(常发生在new HashMap()后，put操作)，给table初始化一个默认长度。
2. 第二步，如果key是null值，插入到指定位置，固定为数组0号位置，如果已经存在元素，直接覆盖（HashMap只允许一个key为null）；也看一下代码

很明显，直接找数组的0号位置，for循环是找0号位置链表中key为null的节点，如果已经存在直接覆盖返回，否则在0号位置直接插入key为null 的节点,原来在0号位置的节点后移（此处也是调用addEntry方法，后边一起分析）。

1. 第三步，先根据key的hash值计算出数组位置，然后for循环遍历该bucketindex位置上的节点和key做对比，如果有重复的key，直接用当前key对应的value覆盖并返回旧值，如果该位置链表没有找到相等的key或者当前位置还没有任何节点元素，那么直接在该位置新建节点，next指针指向原来的table[i]位置的节点(如果之前table[i]==null,那么新节点key.next = null,如果之前table[i]!=null,table[i]指向新节点key，并且key.next指向之前table[i]位置的节点，也就是说之前的链表位置后移)。
2. 第四步，如果上一步for循环中的return没有执行到，就执行addEntry操作，返回null(新插入一个节点，该节点位置之前没有元素，所以旧值也是null)。

以上流程中前三步操作问题都不大，出现线程安全问题是第四步中的addEntry方法，接下来我们将详细分析一下该方法的执行流程和出现问题的地方,还是先看一下addEntry方法的源码：

从方法签名中大概得知，增加一个key-value键值对到指定的bucket位置，如果有必要，将进行扩容操作。

还是间简单分析一下该方法所做的事情：

1. 如果当前size(元素个数)达到阈值且要插入元素的bucket位置不是空，进行扩容操作，尝试将容量扩为原来的2倍，并计算新key在扩容后的table中的位置(resize操作做了两件事，一是将容量扩大为原来2倍，二是将旧table中的元素复制到新的table中)
2. 根据计算的hash子和bucketIndex新增节点。

而今天我想要说的造成死链的操作就是在扩容的过程中导致的，看一下resize代码:

图中一并贴出了resize中用到的元素迁移的transfer方法。

方法签名的意思是，对旧table中的元素重新做hash计算然后迁移到扩容后的数组中，方法是在元素个数到达阈值的时候自动调用。

首先分析一下resize方法中做的事情：

1. 如果table长度已经到达最大限制，直接返回调用。
2. 根据扩容后的长度新建一个Entry数组，执行迁移操作，然后将table指向新的数组。
3. 根据扩容后的参数修改阈值后返回。

而真正在并发环境下致使或扩容操作产生死链的，是transfer方法，为什么呢？我们继续分析。

为了立体形象，清晰易懂，我们假设一个HashMap容量是3，现在已经有两个元素（假设A和B在容量扩大为6时hash到的位置仍然相同）：

Entry[0] = A(.next) --> B(.next) --> null

此时如果两个线程同时调用put操作，会同时触发resize操作，两个线程分别是1和2。

假如线程2执行到Entry<K,V> next = e.next，此时其获取到的e为A，next为B。而此时线程1已经执行完transfer操作，但是还没有执行后续操作，那么此时transfer中的newTable的结构变成：

Entry[0] = B(.next) --> A(.next) --> null

此时线程2继续执行，进入这段代码：

do {
// 此时e为A，e.next为B，此行相当于next = B;
Entry<K,V> next = e.next;
// 假设i=0
int i = indexFor(e.hash, newCapacity);
// newTable[0]为null，此行相当于A.next = null;
e.next = newTable[i];
// 此行相当于newTable[0] = A;
newTable[i] = e;
// 此行相当于e = B;
e = next;
} while (e != null);

此时newTable的结构为：

Entry[0] = A(.next) --> null

e不为null，继续执行：

do {
// 此时e为B，e.next为A（第一个线程修改的），此行相当于next = A;
Entry<K,V> next = e.next;
// 假设i = 0
int i = indexFor(e.hash, newCapacity);
// newTable[0]为A，此行相当于B.next = A;
e.next = newTable[i];
// 此行相当于newTable[0] = B;
newTable[i] = e;
// 此行相当于e = A;
e = next;
} while (e != null);

此时newTable的结构为：

Entry[0] = B(.next) --> A(.next) --> null

e!=null，继续执行：

do {
// 此时e为A，A.next为null，此行相当于next = null
Entry<K,V> next = e.next;
// 假设i = 0
int i = indexFor(e.hash, newCapacity);
// newTable[0]为B，此行相当于A.next = B;
e.next = newTable[i];
// 此行相当于newTable[0] = A;
newTable[i] = e;
// 此行相当于e = null;
e = next;
} while (e != null);

此时newTable的结构为：

Entry[0] = A(.next) <--> B(.next)，也就是造成了死链，死链的后果很严重，导致后续的get操作造成无线循环，耗光CPU。

此篇介绍了多线程情况下HashMap的put操作致使扩容，从而导致产生死链而带来的线程安全问题，后边会继续对jdk源码做分析，若带来帮助，荣幸至极！