博客分类：
在多线程环境中，使用HashMap进行put操作时会引起死循环，导致CPU使用接近100%，下面通过代码分析一下为什么会发生死循环。
首先先分析一下HashMap的数据结构：HashMap底层数据结构是有一个链表数据构成的，HashMap中定义了一个静态内部类作为链表，代码如下（与本文无关的代码省略）：
static class Entry&K,V& implements Map.Entry&K,V& {
Entry&K,V&
* Creates new entry.
Entry(int h, K k, V v, Entry&K,V& n) {
* The table, resized as necessary. Length MUST Always be a power of two.
transient Entry[]
之所以会导致HashMap出现死循环是因为多线程会导致HashMap的Entry节点形成环链，这样当遍历集合时Entry的next节点用于不为空，从而形成死循环
单添加元素时会通过key的hash值确认链表数组下标
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
//确认链表数组位置
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
//如果key相同则覆盖value部分
for (Entry&K,V& e = table[i]; e != e = e.next) {
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.
e.recordAccess(this);
return oldV
modCount++;
//添加链表节点
addEntry(hash, key, value, i);
下面看一下HashMap添加节点的实现
void addEntry(int hash, K key, V value, int bucketIndex) {
//bucketIndex 通过key的hash值与链表数组的长度计算得出
Entry&K,V& e = table[bucketIndex];
//创建链表节点
table[bucketIndex] = new Entry&K,V&(hash, key, value, e);
//判断是否需要扩容
if (size++ &= threshold)
resize(2 * table.length);
以上部分的实现不会导致链路出现环链，环链一般会出现HashMap扩容是，下面看看扩容的实现:
void resize(int newCapacity) {
Entry[] oldTable =
int oldCapacity = oldTable.
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);//可能导致环链
table = newT
threshold = (int)(newCapacity * loadFactor);
下面transfer的实现
void transfer(Entry[] newTable) {
Entry[] src =
int newCapacity = newTable.
for (int j = 0; j & src. j++) {
Entry&K,V& e = src[j];
if (e != null) {
Entry&K,V& next = e.
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] =
} while (e != null);
这个方法的目的是将原链表数据的数组拷到新的链表数组中，拷贝过程中如果形成环链的呢？下面用一个简单的例子来说明一下：
public class InfiniteLoop {
static final Map&Integer, Integer& map = new HashMap&Integer, Integer&(2, 0.75f);
public static void main(String[] args) throws InterruptedException {
map.put(5, 55);
new Thread("Thread1") {
public void run() {
map.put(7, 77);
System.out.println(map);
}.start();
new Thread("Thread2") {
public void run() {
map.put(3, 33);
System.out.println(map);
}.start();
下面通过debug跟踪调试来看看如果导致HashMap形成环链，断点位置：
线程1的put操作
线程2的put操作
线程2的输出操作
HashMap源码transfer方法中的第一行、第六行、第九行
使线程1进入transfer方法第一行，此时map的结构如下
使线程2进入transfer方法第一行,此时map的结构如下：
3.接着切换回线程1，执行到transfer的第六行，此时map的结构如下：
4.然后切换回线程2使其执行到transfer方法的第六行，此时map的结够如上
5.接着切换回线程1使其执行到transfer方法的第九行，然后切换回线程2使其执行完，此时map的结构如下：
6.切换回线程1执行循环，因为线程1之前是停在HashMap的transfer方法的第九行处，所以此时transfer方法的节点e的key=3，e.next的key=7
void transfer(Entry[] newTable) {
Entry[] src =
int newCapacity = newTable.
for (int j = 0; j & src. j++) {
Entry&K,V& e = src[j];
if (e != null) {
Entry&K,V& next = e.
int i = indexFor(e.hash, newCapacity);//线程1等线程2执行结束后
//从此处开始执行
//此时e的key=3,e.next.key=7
//但是此时的e.next.next的key=3了
//（被线程2修改了）
e.next = newTable[i];
newTable[i] =
} while (e != null);
下面线程1开始执行第一次循环，循环后的map结构如下：
接着执行第二次循环：e.key=7,e.next.key=3，e.next.next=null
接着执行第三次循环，从而导致环链形成，map结构如下
并且此时的map中还丢失了key=5的节点
浏览: 133436 次
你好，代码麻烦发一份给我，谢谢，@qq.c ...
大神发我一份，
兄弟，你好！
能给我发一份吗？@qq.c ...
最后一步图是不是画错了，3应该在前面吧
(window.slotbydup=window.slotbydup || []).push({
id: '4773203',
container: s,
size: '200,200',
display: 'inlay-fix'在ConcurrentHashMap没有出现以前，jdk使用hashtable来实现线程安全，但是hashtable是将整个hash表锁住，所以效率很低下。
ConcurrentHashMap将数据分别放到多个Segment中，默认16个，每一个Segment中又包含了多个HashEntry列表数组，
对于一个key，需要经过三次hash操作，才能最终定位这个元素的位置，这三次hash分别为：
对于一个key，先进行一次hash操作，得到hash值h1，也即h1 = hash1(key)；
将得到的h1的高几位进行第二次hash，得到hash值h2，也即h2 = hash2(h1高几位)，通过h2能够确定该元素的放在哪个Segment；
将得到的h1进行第三次hash，得到hash值h3，也即h3 = hash3(h1)，通过h3能够确定该元素放置在哪个HashEntry。
每一个Segment都拥有一个锁，当进行写操作时，只需要锁定一个Segment，而其它Segment中的数据是可以访问的。
阅读(...) 评论()博客分类：
ConcurrentHashMap是线程安全的概念已经深入人心，让我们在使用的时候有些大意了，我也懒得动脑子，直接使用，结果碰到钉子了.
这个问题让我很郁闷，程序逻辑全是对的，但是问题却明明摆在那边，最后怀疑是HashMap的问题。
package com.taobao.mmp.
import java.util.HashM
import java.util.M
import java.util.concurrent.ConcurrentHashM
import com.taobao.mmp.dataobject.ServiceDO;
public class TTTT {
private static Map&Long, ServiceDO& widgetCacheMap = new ConcurrentHashMap&Long, ServiceDO&();
* @param args
public static void main(String[] args) {
// TODO Auto-generated method stub
for(int i=0;i&10000;i++){
Thread tt = new Thread(new Rund());
tt.start();
static class Rund implements Runnable{
public void run() {
// TODO Auto-generated method stub
* 1W次，总有那么几次线程不安全
public void test(){
TTTT tt = new TTTT();
int s1 = widgetCacheMap.get(1L).getStatus();
tt.change();
int s2 = widgetCacheMap.get(1L).getStatus();
if(s1==s2){
System.out.println(s1+":"+s2);
public void set() {
Map mm= new HashMap();
ServiceDO ss = new ServiceDO();
ss.setStatus(1);
mm.put(1L, ss);
widgetCacheMap =
public void change(){
Map mm= new HashMap();
ServiceDO ss = new ServiceDO();
ss.setStatus(2);
mm.put(1L, ss);
widgetCacheMap =
执行10000次，多执行几次，或许你会发现，真的一般情况下是线程安全的，但是在大量并发的时候，线程就变得不那么安全了.
输出结果如下:
为什么出现这种情况，我在第一个地方设置值，然后取值，第二个地方再设置值，然后取值，两个值应该不同的，判断相同的时候，既然出现了。有人怀疑是ConcurrentHashMap,那你可以换成HashMap试试.结果一样.
为什么是2,2不是1,1；当然一般情况下是1:2，并发情况下就变成2,2了.
有人怀疑是初始化widgetCacheMap的问题，那么改代码如下:
public void set() {
//Map mm= new HashMap();
ServiceDO ss = new ServiceDO();
ss.setStatus(1);
widgetCacheMap.put(1L, ss);
//widgetCacheMap =
public void change(){
//Map mm= new HashMap();
ServiceDO ss = new ServiceDO();
ss.setStatus(2);
widgetCacheMap.put(1L, ss);
//widgetCacheMap =
真是不改不知道，一改吓一跳，这回出现刚才说的情况1,1
而且改了之后其并发问题更严重了，因为这里每一次put都需要加行锁，其并发的概念也就上升了.
推荐写法还是按第一次方法，对象的覆盖是原子的，最好加一把锁，否则你第一次覆盖了，第二次又被别人覆盖了.
于是代码如下:
public void set() {
synchronized (widgetCacheMap) {
Map mm= new HashMap();
ServiceDO ss = new ServiceDO();
ss.setStatus(1);
mm.put(1L, ss);
widgetCacheMap =
public void change(){
synchronized (widgetCacheMap) {
Map mm= new HashMap();
ServiceDO ss = new ServiceDO();
ss.setStatus(2);
mm.put(1L, ss);
widgetCacheMap =
保持widgetCacheMap的变更成原子状态。当然还会出现上面的情况，这是为什么呢。
因为每一个线程获取的时候，可能取的是原子1,也可能是原子2,如果在多线程获取的时候加一把锁，那么获取的就是原子X,但至少是一个原子，要么1,要么2.
于是代码如下:
public void test(){
synchronized (widgetCacheMap) {
TTTT tt = new TTTT();
int s1 = widgetCacheMap.get(1L).getStatus();
tt.change();
int s2 = widgetCacheMap.get(1L).getStatus();
if(s1==s2){
System.out.println(s1+":"+s2);
结果又出现如上现象，这是为什么呢，因为锁里面还加着锁，锁最好是原子化，尽量保持最小范围，不能价懒，像我一样就悲剧了.
* 1W次，总有那么几次线程不安全
public void test(){
TTTT tt = new TTTT();
int s1 = -1;
synchronized (widgetCacheMap) {
s1 = widgetCacheMap.get(1L).getStatus();
tt.change();
int s2 = -2;
synchronized (widgetCacheMap) {
s2 = widgetCacheMap.get(1L).getStatus();
if(s1==s2){
System.out.println(s1+":"+s2);
还是出现上面这种情况，通阅全码，发现每一次都是原子了，应该没问题了。
但是还需要考虑run方法是多线程的，只有一个线程进入test，那就算原子了.如下:
唉，这是为什么呢，syn不起作用？
开始怀疑，于是去掉所有的syn，只添加run方法中的如下:
* 1W次，总有那么几次线程不安全
void test(){
synchronized (widgetCacheMap) {
TTTT tt = new TTTT();
int s1 = -1;
s1 = widgetCacheMap.get(1L).getStatus();
tt.change();
int s2 = -2;
s2 = widgetCacheMap.get(1L).getStatus();
if(s1==s2){
System.out.println(s1+":"+s2);
整个进行原子操作，结果让人晕死。还是出现在，最后想了想，原来Hash或者CurrentHashMap也一样，在中间change了一下，而syn锁定的是一个不变的东西。
于如改代码如下:
* 1W次，总有那么几次线程不安全
void test(){
synchronized ("") {
TTTT tt = new TTTT();
int s1 = -1;
s1 = widgetCacheMap.get(1L).getStatus();
tt.change();
int s2 = -2;
s2 = widgetCacheMap.get(1L).getStatus();
if(s1==s2){
System.out.println(s1+":"+s2);
这回你怎么执行都是原子操作了。
总结：ConcurrentHashMap是线程安全的，那是在他们的内部操作，其外部操作还是需要自己来保证其同步的，特别是静态的ConcurrentHashMap,其有更新和查询的过程，要保证其线程安全，需要syn一个不可变的参数才能保证其原子性
浏览 19250
论坛回复 /
(12 / 3745)
今天无意中看到你这篇博客，我觉得有问题：&&& 1.widgetCacheMap = mm你这样一来，widgetCacheMap指向了一个HashMap,它已经不是一个ConcurrentHashMap了；&&& 2.ConcurrentHashMap本身确实是一个线程安全的数据结构，但它的线程安全是有条件的，你的这个test方法：&&& public void test(){& &&&&&&&&&&&&&&& TTTT tt = new TTTT();& &&&&&&&&&&&&&&& tt.set();& &&&&&&&&&&&&&&& int s1 = widgetCacheMap.get(1L).getStatus();& &&&&&&&&&&&&&&& tt.change();& &&&&&&&&&&&&&&& int s2 = widgetCacheMap.get(1L).getStatus();& &&&&&&&&&&&&&&& if(s1==s2){& &&&&&&&&&&&&&&&&&&& System.out.println(s1+":"+s2);& &&&&&&&&&&&&&&& }& &&&&&&& } 本身是有问题的，假如某一个线程刚执行完tt.set()中的 widgetCacheMap.put(1L,ss);然后另个线程立刻开始执行tt.change()中的 widgetCacheMap.put(1L,ss);并且执行完毕，那么第一个数就变成了2，同理第二个数也可能变成1.这个测试用例是有问题的，有事务的意途，但没有事务的约束，你测的不是ConcurrentHashMap，而是两个set和change的事务性保证
这个内部put和get是原子的，就是说肯定不会出现内部数据结构错误吧。至于put和get的对象，这个状态的变化的同步可能还是需要我们自己来做。是的
浏览: 302143 次
来自: 杭州
public static final Logger log ...
java程序语言学习教程 地址http://www.zuida ...
[img][/img]
(window.slotbydup=window.slotbydup || []).push({
id: '4773203',
container: s,
size: '200,200',
display: 'inlay-fix'Java HashMap笔记之三：ConcurrentHashMap线程安全原理
Java HashMap笔记之三：ConcurrentHashMap线程安全原理
科学的小巷
在《Java HashMap笔记之一：基本原理》和《Java HashMap笔记之二：线程不安全原理》已经介绍了Java中HashMap的基本工作原理和线程不安全的原理这里先简单回顾总结下：内部Entry数组默认大小是16，默认负载因子是0.75内部Entry数组大小是2的幂元素个数超过当前大小*默认因子的时候会扩容到当前大小的2倍扩容是为了减少单个Entry数组链表的平均长度HashMap线程不安全的主要因素的put过程中会发生扩容，多个线程会同时操作同一块内存导致JDK7使用数组+链表方式实现；JDK8使用数组+链表/红黑树的方式实现：链表长度为8，链表转化为红黑树；红黑树节点个数为6，红黑树会转化为链表HashMap是线程不安全的，在多线程环境下，可以使用HashTable和ConcurrentHashMap。HashTable的get和put方法都使用synchronized修饰，导致线程1在get元素的时候，线程2不仅不可以put元素，也不可以get元素，在竞争环境激烈的情况下，会出现比较严重的性能问题。下面我们来看下ConcurrentHashMap使用哪种方式解决了性能问题（以JDK7为示例）。ConcurrentHashMap基本思想ConcurrentHashMap数据结构ConcurrentHashMap的初始化ConcurrentHashMap的get方法ConcurrentHashMap的put方法ConcurrentHashMap的size方法ConcurrentHashMap的弱一致性举2个比较简单的例子就可以看出ConcurrentHashMap的弱一致性。第一个，就是clear方法。假设线程1执行到Segment[1].clear()的时候，Segment[0]中的元素元素已经被clear，但是线程2此时可以在Segment[0]中增加元素（clear不需要加锁），这样线程1执行结束的时候就ConcurrentHashMap并不是空的。第二个例子，判断key是否存在，不存在则进行put。假设线程1判断key不存在后挂起，线程2判断key也不存在，然后线程2执行put操作，之后线程1执行put操作，此时线程2读取到的会是线程1设置的值而不是线程2设置的值。当然此时应该是应用putIfAbsent方法。小结ConcurrentHashMap在设计思路对效率和一致性上的平衡以及一些lock-free的方法非常值得借鉴，同时注意虽然类本身是线程安全的，但是不要认为使用该类就一定是线程安全的。
本文仅代表作者观点，不代表百度立场。系作者授权百家号发表，未经许可不得转载。
科学的小巷
百家号 最近更新：
简介: 爱数码，爱生活，观察科技发展的每一天。
作者最新文章