高并发下的HashMap
HashMap不是一个线程安全的类，在并发下可能会出现死循环（JDK1.7）,今天我们来聊聊这个死循环是如何形成的
本文基于 jdk-7u76 进行分析
温馨提示
本文对照着源码看并在纸上画画效果会更佳
代码回顾
师傅，我常常听别人说，不要在并发情况下使用HashMap，可能会出现死循环，这个死循环是怎么形成的呢？
一尘
慧能
这个听为师慢慢道来
我们都知道，HashMap的底层是由数组加链表来实现的
对HashMap底层不了解的可先看：
什么是HashMap？（讲了HashMap的底层原理）
神速Hash上（讲了Hash函数的设计）
神速Hash下（讲了链表法解决冲突及扩容）
当往HashMap中put一个键值对时，如果HashMap中的键值对数量 size 大于或等于阈值(threshold) 并且null != table[bucketIndex] 时会进行扩容
bucketIndex为该键值对最后被散列到hash表table的位置
比如 table的初始容量为4,加载因子为0.75,此时阈值为3，table已有三个元素，现在put一个元素<1,"A">,<1,"A">被散列到table[1]处，而table[1] != null,此时满足扩容条件
阈值 = 容量 * 加载因子
threshold = capacity * loadFactor
扩容时先生成一个是table大小2倍的newTable，然后把table中的元素迁移到newTable中，迁移的工作就由 transfer方法来完成，这个方法就是引起死循环的原因所在
环的形成
现在我们来模拟一下环是如何形成的，设HashMap的初始容量为4，先往HashMap中依次put三个元素<5,"B">、<9,"C">、<1,"A">，它们都被散列到table[1]处，形成了链
假设此时有两个线程并发对该HashMap进行put，线程1 put <13,"D">时，这个键值对被散列到table[1]处，满足扩容条件，进行扩容（生成newTable并进行迁移）
此时，线程1用 transfer 方法将 table中的元素迁移到 newTable 中，假设线程1执行完 transfer 方法中的 Entry<K,V> next = e.next 语句后时间片用完，挂起
此时，线程1内的 e 指向 <1,“A”>，next指向<9,"C">
然后线程2 put <16,"E">,同样这个键值对被散列到table[1]处，满足扩容条件，进行扩容
生成完newTable后用transfer方法进行迁移，执行完Entry<K,V> next = e.next;后与线程1一样，e指向<1,"A">,next指向<9,"C">
线程2 然后执行循环体下面的语句
线程2执行完之后为下图
然后线程2按照同样的逻辑进行第二次循环（while循环），下面是第二遍循环后的结果
下面是第三遍循环后的结果
此时，线程2时间片用完，线程1得到时间片，开始执行
注意，此时线程1的e指向<1,A>,next指向<9,C>,在线程2操作链表的时候，线程1 中的e,next指向的元素没变(一直是红色的e和next)
线程一和线程二整体图为：
然后线程1开始执行循环内剩下的代码
执行完后为下图
线程1继续执行第二遍循环
执行完为下图
线程1继续第三遍循环（注意：此次循环会形成环）
先执行 Entry<K,V> next = <1,A>.next
然后执行 <1,A>.next = newTable[1]
此时环已经形成
然后执行剩余的两行代码
执行完，e 为 null,退出循环
死循环的发生
当形成环后,当给HashMap中put元素的时候，这个元素恰巧落在了table[1]（不管有没有更新table），而这个元素的Key不在table[1]这条链上，此时会发生死循环
或者在get元素的时候，该元素恰巧落在table[1]上，并且该元素的Key不在该链上，会发生死循环
原来死循环是这样形成的
一尘
慧能
对，核心就是线程2修改了原来的链表结构，而线程1却以原来的逻辑执行迁移
那并发下我还想使用散列表这种数据结构怎么办呢
一尘
慧能
用ConcurrentHashMap
推荐阅读：
后记
想深入研究的伙伴可以用代码调试跑一遍