HashMap死锁原因及替代方案

1、首先我们需要简单地了解一下HashMap数据结构
HashMap通常会用一个指针数组（假设为table[]）来做分散所有的key，当一个key被加入时，会通过Hash算
法通过key算出这个数组的下标i，然后就把这个<key, value>插到table[i]中，如果有两个不同的key被算了。
但有时候两个key算出的下标会是一个i，那么就叫冲突，又叫碰撞，这样会在table[i]上形成一个链表。所以
如果链表过多或过长，查找算法则会变成低性能的链表遍历，这是Hash表的缺陷。

我们都知道HashMap初始容量大小为16,一般来说，Hash表这个容器当有数据要插入时，都会检查容量有没有超过设定的thredhold，如果超过，需要增大Hash表的尺寸，但是这样一来，整个Hash表里的元素都需要被重算一遍。这叫rehash，这个成本相当的大。具体大家可以看看JDK源码

2、现在来讨论死锁产生的原因
HashMap是非线程安全，死锁一般都是产生于并发情况下。我们假设有二个进程T1、T2，HashMap容量为2,T1线程放入key A、B、C、D、E。在T1线程中A、B、C Hash值相同，于是形成一个链接，假设为A->C->B，而D、E Hash值不同，于是容量不足，需要新建一个更大尺寸的hash表，然后把数据从老的Hash表中
迁移到新的Hash表中(refresh)。这时T2进程闯进来了，T1暂时挂起，T2进程也准备放入新的key，这时也
发现容量不足，也refresh一把。refresh之后原来的链表结构假设为C->A，之后T1进程继续执行，链接结构
为A->C,这时就形成A.next=B,B.next=A的环形链表。一旦取值进入这个环形链表就会陷入死循环。

 

3、替代方案
使用ConcurrentHashMap进行替代，ConcurrentHashMap是一个线程安全的Hash Table。可能有人会使用HashTable。当然HashTable也是线程安全,但HashTable锁定的是整个Hash表，效率相对比较低。而ConcurrentHashMap可以做到读取数据不加锁，并且其内部的结构可以让其在进行写操作的时候能够将锁的粒度保持地尽量地小，

评论

2 楼 steafler 2014-01-27  

java中只有线程的概念

1 楼 snipertarget 2013-07-02  

HashMap本身并没有错，错的是使用它的人把它用错了地方。说它造成死锁，造成cpu100%，只能说使用者没不太清楚应用场景.工具只是工具，如果程序出了问题，归根还是人的问题。