infinite loop

Java-HashMap多线程安全解析

多线程put后可能导致get死循环

从前我们的Java代码因为⼀些原因使⽤了HashMap这个东西，但是当时的程序是单线程的，⼀切都没有问题。后来，我们的程序性能有问

题，所以需要变成多线程的，于是，变成多线程后到了线上，发现程序经常占了100%的CPU，查看堆栈，你会发现程序都Hang在了

()这个⽅法上了，重启程序后问题消失。但是过段时间⼜会来。⽽且，这个问题在测试环境⾥可能很难重现。

我们简单的看⼀下我们⾃⼰的代码，我们就知道HashMap被多个线程操作。⽽Java的⽂档说HashMap是⾮线程安全的，应该⽤

ConcurrentHashMap。但是在这⾥我们可以来研究⼀下原因。简单代码如下：

publicclassTestLock{

privateHashMapmap=newHashMap();

publicTestLock(){

Threadt1=newThread(){

publicvoidrun(){

for(inti=0;i<50000;i++){

(newInteger(i),i);

}

n("t1over");

}

};

Threadt2=newThread(){

publicvoidrun(){

for(inti=0;i<50000;i++){

(newInteger(i),i);

}

n("t2over");

}

};

Threadt3=newThread(){

publicvoidrun(){

for(inti=0;i<50000;i++){

(newInteger(i),i);

}

n("t3over");

}

};

Threadt4=newThread(){

publicvoidrun(){

for(inti=0;i<50000;i++){

(newInteger(i),i);

}

n("t4over");

}

};

Threadt5=newThread(){

publicvoidrun(){

for(inti=0;i<50000;i++){

(newInteger(i),i);

}

n("t5over");

n("t5over");

}

};

Threadt6=newThread(){

publicvoidrun(){

for(inti=0;i<50000;i++){

(newInteger(i));

}

n("t6over");

}

};

Threadt7=newThread(){

publicvoidrun(){

for(inti=0;i<50000;i++){

(newInteger(i));

}

n("t7over");

}

};

Threadt8=newThread(){

publicvoidrun(){

for(inti=0;i<50000;i++){

(newInteger(i));

}

n("t8over");

}

};

Threadt9=newThread(){

publicvoidrun(){

for(inti=0;i<50000;i++){

(newInteger(i));

}

n("t9over");

}

};

Threadt10=newThread(){

publicvoidrun(){

for(inti=0;i<50000;i++){

(newInteger(i));

}

n("t10over");

}

};

();

();

();

();

();

();

();

();

();

();

}

}

publicstaticvoidmain(String[]args){

newTestLock();

}

}

就是启了10个线程，不断的往⼀个⾮线程安全的HashMap中put内容/get内容，put的内容很简单，key和value都是从0⾃增的整数（这

个put的内容做的并不好，以致于后来⼲扰了我分析问题的思路）。对HashMap做并发写操作，我原以为只不过会产⽣脏数据的情况，但

反复运⾏这个程序，会出现线程t1、t2被hang住的情况，多数情况下是⼀个线程被hang住另⼀个成功结束，偶尔会10个线程都被hang

住。

产⽣这个死循环的根源在于对⼀个未保护的共享变量—⼀个"HashMap"数据结构的操作。当在所有操作的⽅法上加

了"synchronized"后，⼀切恢复了正常。这算jvm的bug吗？应该说不是的，这个现象很早以前就报告出来了。Sun的⼯程师并不认为这是

bug，⽽是建议在这样的场景下应采⽤"ConcurrentHashMap”，

CPU利⽤率过⾼⼀般是因为出现了出现了死循环，导致部分线程⼀直运⾏，占⽤cpu时间。问题原因就是HashMap是⾮线程安全的，多个

线程put的时候造成了某个key值EntrykeyList的死循环，问题就这么产⽣了。

当另外⼀个线程get这个EntryList死循环的key的时候，这个get也会⼀直执⾏。最后结果是越来越多的线程死循环，最后导致服务器

dang掉。我们⼀般认为HashMap重复插⼊某个值的时候，会覆盖之前的值，这个没错。但是对于多线程访问的时候，由于其内部实现机制

(在多线程环境且未作同步的情况下，对同⼀个HashMap做put操作可能导致两个或以上线程同时做rehash动作，就可能导致循环键表出

现，⼀旦出现线程将⽆法终⽌，持续占⽤CPU，导致CPU使⽤率居⾼不下)，就可能出现安全问题了。

使⽤jstack⼯具dump出问题的那台服务器的栈信息。死循环的话，⾸先查找RUNNABLE的线程，找到问题代码如下：

:RUNNABLE

(:303)

sformTweetT5(:183)

共出现了23次。

:RUNNABLE

(:374)

ormT5(:816)

共出现了3次。

注意：不合理使⽤HashMap导致出现的是死循环⽽不是死锁。

多线程put的时候可能导致元素丢失

主要问题出在addEntry⽅法的newEntry(hash,key,value,e)，如果两个线程都同时取得了e,则他们下⼀个元素都是e，然后赋值给table

元素的时候有⼀个成功有⼀个丢失。

put⾮null元素后get出来的却是null

在transfer⽅法中代码如下：

voidtransfer(Entry[]newTable){

Entry[]src=table;

intnewCapacity=;

for(intj=0;j<;j++){

Entrye=src[j];

if(e!=null){

src[j]=null;

do{

Entrynext=;

inti=indexFor(,newCapacity);

=newTable[i];

newTable[i]=e;

e=next;

}while(e!=null);

}

}

}

在这个⽅法⾥，将旧数组赋值给src，遍历src，当src的元素⾮null时，就将src中的该元素置null，即将旧数组中的元素置null了，也就是

这⼀句：

if(e!=null){

src[j]=null;

关于HashMap线程不安全这⼀点，《Java并发编程的艺术》⼀书中是这样说的：

HashMap在并发执⾏put操作时会引起死循环，导致CPU利⽤率接近100%。因为多线程会导致HashMap的Node链表形成环形数据

结构，⼀旦形成环形数据结构，Node的next节点永远不为空，就会在获取Node时产⽣死循环。

哇塞，听上去si不si好神奇，居然会产⽣死循环。。。。google了⼀下，才知道死循环并不是发⽣在put操作时，⽽是发⽣在扩容时。详细

的解释可以看下⾯⼏篇博客：

HashMap数据结构

我需要简单地说⼀下HashMap这个经典的数据结构。

HashMap通常会⽤⼀个指针数组（假设为table[]）来做分散所有的key，当⼀个key被加⼊时，会通过Hash算法通过key算出这个数组的

下标i，然后就把这个插到table[i]中，如果有两个不同的key被算在了同⼀个i，那么就叫冲突，⼜叫碰撞，这样会在table[i]上形成⼀个链

表。

我们知道，如果table[]的尺⼨很⼩，⽐如只有2个，如果要放进10个keys的话，那么碰撞⾮常频繁，于是⼀个O(1)的查找算法，就变成了

链表遍历，性能变成了O(n)，这是Hash表的缺陷。

所以，Hash表的尺⼨和容量⾮常的重要。⼀般来说，Hash表这个容器当有数据要插⼊时，都会检查容量有没有超过设定的thredhold，如

果超过，需要增⼤Hash表的尺⼨，但是这样⼀来，整个Hash表⾥的元素都需要被重算⼀遍。这叫rehash，这个成本相当的⼤。

HashMap的rehash源代码

下⾯，我们来看⼀下Java的HashMap的源代码。Put⼀个Key,Value对到Hash表中：

新建⼀个更⼤尺⼨的hash表，然后把数据从⽼的Hash表中迁移到新的Hash表中。

voidresize(intnewCapacity)

{

Entry[]oldTable=table;

intoldCapacity=;

......

//创建⼀个新的HashTable

Entry[]newTable=newEntry[newCapacity];

//将OldHashTable上的数据迁移到NewHashTable上

transfer(newTable);

table=newTable;

threshold=(int)(newCapacity*loadFactor);

}

迁移的源代码，注意⾼亮处：

voidtransfer(Entry[]newTable)

{

Entry[]src=table;

intnewCapacity=;

//下⾯这段代码的意思是：

//从OldTable⾥摘⼀个元素出来，然后放到NewTable中

for(intj=0;j<;j++){

Entrye=src[j];

if(e!=null){

src[j]=null;

do{

Entrynext=;

inti=indexFor(,newCapacity);

=newTable[i];

newTable[i]=e;

e=next;

}while(e!=null);

}

}

}

好了，这个代码算是⽐较正常的。⽽且没有什么问题。

正常的ReHash过程

画了个图做了个演⽰。

1.我假设了我们的hash算法就是简单的⽤keymod⼀下表的⼤⼩（也就是数组的长度）。

2.最上⾯的是oldhash表，其中的Hash表的size=2,所以key=3,7,5，在mod2以后都冲突在table1这⾥了。

3.接下来的三个步骤是Hash表resize成4，然后所有的重新rehash的过程。

并发的Rehash过程

（1）假设我们有两个线程。我⽤红⾊和浅蓝⾊标注了⼀下。我们再回头看⼀下我们的transfer代码中

的这个细节：

do{

Entrynext=;//<--假设线程⼀执⾏到这⾥就被调度挂起了

inti=indexFor(,newCapacity);

=newTable[i];

newTable[i]=e;

e=next;

}while(e!=null);

⽽我们的线程⼆执⾏完成了。于是我们有下⾯的这个样⼦。

注意：因为Thread1的e指向了key(3)，⽽next指向了key(7)，其在线程⼆rehash后，指向了线程⼆重组后的链表。我们可以看到链表的

顺序被反转后。

（2）线程⼀被调度回来执⾏。

1.先是执⾏newTalbe[i]=e。

2.然后是e=next，导致了e指向了key(7)。

3.⽽下⼀次循环的next=导致了next指向了key(3)。

（3）⼀切安好。

线程⼀接着⼯作。把key(7)摘下来，放到newTable[i]的第⼀个，然后把e和next往下移。

（4）环形链接出现。

=newTable[i]导致key(3).next指向了key(7)。注意：此时的key(7).next已经指向了key(3)，环形链表就这样出现了。

于是，当我们的线程⼀调⽤到，(11)时，悲剧就出现了——InfiniteLoop。

三种解决⽅案

Hashtable替换HashMap

Hashtable是同步的，但由迭代器返回的Iterator和由所有Hashtable的“collection视图⽅法”返回的Collection的listIterator⽅法

都是快速失败的：在创建Iterator之后，如果从结构上对Hashtable进⾏修改，除⾮通过Iterator⾃⾝的移除或添加⽅法，否则在任何时

间以任何⽅式对其进⾏修改，Iterator都将抛出ConcurrentModificationException。因此，⾯对并发的修改，Iterator很快就会完全失

败，⽽不冒在将来某个不确定的时间发⽣任意不确定⾏为的风险。由Hashtable的键和值⽅法返回的Enumeration不是快速失败的。

注意，迭代器的快速失败⾏为⽆法得到保证，因为⼀般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最

⼤努⼒抛出ConcurrentModificationException。因此，为提⾼这类迭代器的正确性⽽编写⼀个依赖于此异常的程序是错误做法：迭代器

的快速失败⾏为应该仅⽤于检测程序错误。

先稍微吐槽⼀下，为啥命名不是HashTable啊，看着好难受，不管了就装作它叫HashTable吧。这货已经不常⽤了，就简单说说吧。

HashTable源码中是使⽤synchronized来保证线程安全的，⽐如下⾯的get⽅法和put⽅法：

publicsynchronizedVget(Objectkey){

//省略实现

}

publicsynchronizedVput(Kkey,Vvalue){

//省略实现

}

所以当⼀个线程访问HashTable的同步⽅法时，其他线程如果也要访问同步⽅法，会被阻塞住。举个例⼦，当⼀个线程使⽤put⽅法时，另

⼀个线程不但不可以使⽤put⽅法，连get⽅法都不可以，好霸道啊so~~，效率很低，现在基本不会选择它了。

onizedMap将HashMap包装起来

返回由指定映射⽀持的同步（线程安全的）映射。为了保证按顺序访问，必须通过返回的映射完成对底层映射的所有访问。在返回的映射或

其任意collection视图上进⾏迭代时，强制⽤户⼿⼯在返回的映射上进⾏同步：

Mapm=onizedMap(newHashMap());

...

Sets=();//Needn'tbeinsynchronizedblock

...

synchronized(m){//Synchronizingonm,nots!

Iteratori=or();//Mustbeinsynchronizedblock

while(t())

foo(());

}

不遵从此建议将导致⽆法确定的⾏为。如果指定映射是可序列化的，则返回的映射也将是可序列化的。

看了⼀下源码，SynchronizedMap的实现还是很简单的。

//synchronizedMap⽅法

publicstaticMapsynchronizedMap(Mapm){

returnnewSynchronizedMap<>(m);

}

//SynchronizedMap类

privatestaticclassSynchronizedMap

implementsMap,Serializable{

privatestaticfinallongrialVersionUID=59022715L;

privatefinalMapm;//BackingMap

finalObjectmutex;//Objectonwhichtosynchronize

SynchronizedMap(Mapm){

this.m=eNonNull(m);

mutex=this;

}

SynchronizedMap(Mapm,Objectmutex){

this.m=m;

=mutex;

}

publicintsize(){

synchronized(mutex){();}

}

publicbooleanisEmpty(){

synchronized(mutex){y();}

}

publicbooleancontainsKey(Objectkey){

synchronized(mutex){nsKey(key);}

}

publicbooleancontainsValue(Objectvalue){

synchronized(mutex){nsValue(value);}

}

publicVget(Objectkey){

synchronized(mutex){(key);}

}

publicVput(Kkey,Vvalue){

synchronized(mutex){(key,value);}

}

publicVremove(Objectkey){

synchronized(mutex){(key);}

}

//省略其他⽅法

}

通过onizedMap()来封装所有不安全的HashMap的⽅法,就连toString,hashCode都进⾏了封装.封装的关键点有2

处,1)使⽤了经典的synchronized来进⾏互斥,2)使⽤了代理模式new了⼀个新的类,这个类同样实现了Map接⼝.

⽅法⼀使⽤的是的synchronized⽅法,是⼀种悲观锁.在进⼊之前需要获得锁,确保独享当前对象,然后做相应的修改/读取.

ConcurrentHashMap替换HashMap

⽀持检索的完全并发和更新的所期望可调整并发的哈希表。此类遵守与Hashtable相同的功能规范，并且包括对应于Hashtable的每个⽅

法的⽅法版本。不过，尽管所有操作都是线程安全的，但检索操作不必锁定，并且不⽀持以某种防⽌所有访问的⽅式锁定整个表。此类可以

通过程序完全与Hashtable进⾏互操作，这取决于其线程安全，⽽与其同步细节⽆关。

检索操作（包括get）通常不会受阻塞，因此，可能与更新操作交迭（包括put和remove）。检索会影响最近完成的更新操作的结果。对

于⼀些聚合操作，⽐如putAll和clear，并发检索可能只影响某些条⽬的插⼊和移除。类似地，在创建迭代器/枚举时或⾃此之

后，Iterators和Enumerations返回在某⼀时间点上影响哈希表状态的元素。它们不会抛出ConcurrentModificationException。不

过，迭代器被设计成每次仅由⼀个线程使⽤。

ConcurrentHashMap(以下简称CHM)是JUC包中的⼀个类，Spring的源码中有很多使⽤CHM的地⽅。之前已经翻译过⼀篇关于

ConcurrentHashMap的博客，，⾥⾯介绍了CHM在Java中的实现，CHM的⼀些重要特性和什么情况下应该使⽤CHM。需要注意的是，

上⾯博客是基于Java7的，和8有区别,在8中CHM摒弃了Segment（锁段）的概念，⽽是启⽤了⼀种全新的⽅式实现,利⽤CAS算法，有时

间会重新总结⼀下。

重新写了HashMap,⽐较⼤的改变有如下⼏点.

使⽤了新的锁机制(可以理解为乐观锁)稍后详细介绍

把HashMap进⾏了拆分,拆分成了多个独⽴的块,这样在⾼并发的情况下减少了锁冲突的可能

⽅法⼆使⽤的是乐观锁,只有在需要修改对象时,⽐较和之前的值是否被⼈修改了,如果被其他线程修改了,那么就会返回失败.锁的实现,使⽤的

是NonfairSync.这个特性要确保修改的原⼦性,互斥性,⽆法在JDK这个级别得到解决,JDK在此次需要调⽤JNI⽅法,⽽JNI则调⽤CAS指令来

确保原⼦性与互斥性.读者可以⾃⾏GoogleJAVACAS来了解更多.JAVA的乐观锁是如何实现的.

当如果多个线程恰好操作到ConcurrentHashMap同⼀个gment上⾯,那么只会有⼀个线程得到运⾏,其他的线程会被

(),稍后执⾏完成后,会⾃动挑选⼀个线程来执⾏().

如何得到/释放锁

得到锁:

⽅法⼀:在Hashmap上⾯,synchronized锁住的是对象(不是Class),所以第⼀个申请的得到锁,其他线程将进⼊阻塞,等待唤醒.

⽅法⼆:检查,如果为0,则得到锁,或者申请者已经得到锁,则也能再辞得到锁,并且state也加1.

释放锁:

都是得到锁的逆操作,并且使⽤正确,⼆种⽅法都是⾃动选取⼀个队列中的线程得到锁可以获得CPU资源.