jdk源码分析之HashMap--并发情况下remove失败

以下源码分析全部基于jdk1.7

了解过jdk源码的都知道，Hash底层是使用数组+链表的方式实现的，大概如下图：

此篇对HashMap其他部分不做过多解读，针对具体场景做一下分析。如上图中结构，如果我想根据key删除某一个元素，当然单线程场景下不会出现任何问题，但是假如说多个线程执行删除操作呢？具体点，假如有两个并发线程，线程A删除1，线程B删除33，会有怎样的结果呢？这里先把结果说出来，33这个元素删不掉，无论是A线程先删除1成功，B再删除33，还是B先删除33成功，A再删除1，最终33都无法删除。

有可能各位看得一脸懵逼，啥也别说了上代码，我们在jdk1.7中看到HashMap的源码中remove方法:

我们可以看到，remove(key)最终调用了removeEntryForKey(key)方法，再看一下该方法的具体实现:

上述代码的大致思路是，根据key算出hash值，然后映射到HashMap中具体的数据位置，然后遍历该数组位置链表找到满足条件的key的位置，让key的前一个元素指向key的后一个元素(不再有元素指向key了)，就完成了删除操作。

就此篇而言，为什么文章开头的数据结构中在多线程场景下可能33删不掉呢？我们一步一步分析，首先分析A线程删除元素1操作流程：

1. 进入方法并执行while循环一次

第一次比较发现不满足条件，然后prev和e都向后移动一个节点(由于刚开始prev和e都指向第一个节点，所以第一个循环后prev指向e依旧是第一个节点，e指向链表上第二个节点1)。

1. 由于null ！= e，所以A线程在while中执行第二次循环：

该步骤执行结束后完成了1节点的删除，然后HashMap的结构变成了下图这样：

然后我们分析B线程的操作流程，由于是并发场景下并且没有加同步控制，B线程可能做了一些和A线程重复的操作或者拿到了一些失效的数据：

1. B线程进入方法并执行第一次循环比较操作：

第一个循环结束后可能得到了和A线程第一次循环一样的结果，实际上正常情况下下这时候1节点已经被删除，e.next应该指向33节点，但是由于是并发环境，可能A和B线程同时进入循环并且同事拿到next的值是1。

2.B线程在while中执行第二次循环对比：

第二次循环对比结束后，e指向33节点，prev指向1节点。

3.B线程在while中执行第三次对比操作：

表面上此时已经实现了B线程删除节点33操作，但是由于HashMap是线程共享的，A和B线程同时操作HashMap，此时B线程操作的结果可能是下图：

可以看到，B线程最终的操作结果是将节点1的next指针指向了节点44，问题就在于节点1已经是被A线程删除了的，也就是说随便修改节点1的next指向对HashMap已经没有任何影响（因为已经没有节点指向节点1了）。

此案例之所以A和B线程同时进行删除有一个可能失败，是因为有一个线程拿到的prev节点可能是已经过期了的。

当然线程安全问题是在单线程环境下是不会出现的，在并发线程环境下可能会出现，所以使用HashMap的时候一定要注意。

此篇只介绍了删除元素存在的线程安全问题，后续会依次对其他的问题作分析，谢谢翻阅，如带来帮助，荣幸至极！