金沙澳门官网7817网址多线程下HashMap的死循环难点,二十十六线程hashmap

你会发现程序都Hang在了HashMap.get()这个方法上了,我们就知道HashMap被多个线程操作,陶邦仁,你会发现程序都Hang在了HashMap.get()这个方法上了,我们的程序性能有问题,2、多线程put非NULL元素后,导致元素丢失

金沙澳门官网7817网址 10

HashMap四线程并发难题剖判,hashmap多线程并发

原稿出处: 陶邦仁

初稿出处: 陶邦仁

陈年大家的Java代码因为部分原因使用了HashMap这几个东西,但是及时的程序是单线程的,一切都不曾难题。后来,我们的顺序品质有难点,所以须要产生多线程的,于是,产生八线程后到了线上,开采先后常常占了百分百的CPU,查看客栈,你会发觉先后都Hang在了HashMap.get()那一个方式上了,重启程序后难点消灭。可是过段时间又会来。并且,那个难题在测验情状里只怕很难重现。

八线程下HashMap的死循环难点,三十二线程hashmap

出现难题的症状

并发难点的症状

我们大约的看一下大家友好的代码,大家就明白HashMap被三个线程操作。而Java的文书档案说HashMap是非线程安全的,应该用ConcurrentHashMap。不过在此处大家得以来商量一下缘故。简单代码如下:

二十八线程下[HashMap]的问题:

1、二十二十四线程put操作后,get操作变成死循环。
2、二十多线程put非NULL成分后,get操作得到NULL值。
3、三十二线程put操作,导致元素错失。

本次重大关怀[HashMap]-死循环难题。

二十八线程put后也许导致get死循环

未来大家的Java代码因为有个别缘故使用了HashMap那几个事物,不过及时的程序是单线程的,一切都未曾难点。后来,大家的顺序品质有题目,所以需求变成二十多线程的,于是,形成二十四线程后到了线上,发现先后通常占了百分之百的CPU,查看货仓,你会发现先后都Hang在了HashMap.get()这些情势上了,重启程序后难题消灭。不过过段时间又会来。何况,这一个主题素材在测量试验碰着里只怕很难再次出现。

咱俩简要的看一下大家友好的代码,大家就了解HashMap被多少个线程操作。而Java的文书档案说HashMap是非线程安全的,应该用ConcurrentHashMap。不过在此地大家得以来商量一下缘由。轻巧代码如下:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 package com.king.hashmap;   import java.util.HashMap;   public class TestLock {       private HashMap map = new HashMap();       public TestLock() {         Thread t1 = new Thread() {             public void run() {                 for (int i = 0; i < 50000; i++) {                     map.put(new Integer(i), i);                 }                 System.out.println("t1 over");             }         };           Thread t2 = new Thread() {             public void run() {                 for (int i = 0; i < 50000; i++) {                     map.put(new Integer(i), i);                 }                   System.out.println("t2 over");             }         };           Thread t3 = new Thread() {             public void run() {                 for (int i = 0; i < 50000; i++) {                     map.put(new Integer(i), i);                 }                   System.out.println("t3 over");             }         };           Thread t4 = new Thread() {             public void run() {                 for (int i = 0; i < 50000; i++) {                     map.put(new Integer(i), i);                 }                   System.out.println("t4 over");             }         };           Thread t5 = new Thread() {             public void run() {                 for (int i = 0; i < 50000; i++) {                     map.put(new Integer(i), i);                 }                   System.out.println("t5 over");             }         };           Thread t6 = new Thread() {             public void run() {                 for (int i = 0; i < 50000; i++) {                     map.get(new Integer(i));                 }                   System.out.println("t6 over");             }         };           Thread t7 = new Thread() {             public void run() {                 for (int i = 0; i < 50000; i++) {                     map.get(new Integer(i));                 }                   System.out.println("t7 over");             }         };           Thread t8 = new Thread() {             public void run() {                 for (int i = 0; i < 50000; i++) {                     map.get(new Integer(i));                 }                   System.out.println("t8 over");             }         };           Thread t9 = new Thread() {             public void run() {                 for (int i = 0; i < 50000; i++) {                     map.get(new Integer(i));                 }                   System.out.println("t9 over");             }         };           Thread t10 = new Thread() {             public void run() {                 for (int i = 0; i < 50000; i++) {                     map.get(new Integer(i));                 }                   System.out.println("t10 over");             }         };           t1.start();         t2.start();         t3.start();         t4.start();         t5.start();           t6.start();         t7.start();         t8.start();         t9.start();         t10.start();     }       public static void main(String[] args) {         new TestLock();     } }

正是启了拾个线程,不断的往三个非线程安全的HashMap中put内容/get内容,put的开始和结果异常粗略,key和value都以从0自增的整数(那个put的故事情节做的并倒霉,以至于后来搅扰了自家剖判难题的笔触)。对HashMap做并发写操作,作者原以为只然而会爆发脏数据的景色,但频繁运转这几个程序,会油然则生线程t1、t2被hang住的图景,大多状态下是一个线程被hang住另二个成功甘休,临时会12个线程都被hang住。

发出这一个死循环的发源在于对一个未保护的分享变量 —
贰个”HashMap”数据结构的操作。当在富有操作的秘籍上加了”synchronized”后,一切复苏了健康。那算jvm的bug吗?应该说不是的,那一个情景很早从前就告知出来了。Sun的技术员并不认为这是bug,而是建议在那样的景观下应采纳”ConcurrentHashMap”,

CPU利用率过高一般是因为出现了产出了死循环,导致有的线程一向运行,占用cpu时间。难题由来就是HashMap是非线程安全的,三个线程put的时候产生了有个别key值Entry
key List的死循环,难点就这么发生了。

当别的一个线程get 这几个Entry List
死循环的key的时候,那么些get也会直接实施。最终结果是尤为多的线程死循环,最终变成服务器dang掉。大家一般感到HashMap重复插入有个别值的时候,会覆盖在此以前的值,这么些精确。不过对于二十四线程访谈的时候,由于其内部贯彻机制(在二十四线程遇到且未香港作家联谊晤面的气象下,对同二个HashMap做put操作也许引致多个或上述线程相同的时候做rehash动作,就可能产生循环键表出现,一旦出现线程将无法停止,持续攻陷CPU,导致CPU使用率愈来愈多),就大概出现安全主题素材了。

行使jstack工具dump出题指标那台服务器的栈消息。死循环的话,首先查找RUNNABLE的线程,找到标题代码如下:

java.lang.Thread.State:RUNNABLE
at java.util.HashMap.get(HashMap.java:303)
at com.sohu.twap.service.logic.TransformTweeter.doTransformTweetT5(TransformTweeter.java:183)
共出现了23次。
java.lang.Thread.State:RUNNABLE
at java.util.HashMap.put(HashMap.java:374)
at com.sohu.twap.service.logic.TransformTweeter.transformT5(TransformTweeter.java:816)
共出现了3次。

注意:不客观运用HashMap导致出现的是死循环并不是死锁。

四线程put后或许导致get死循环

现在大家的Java代码因为部分缘故使用了HashMap那些东西,然而及时的主次是单线程的,一切都没反常。后来,我们的次序品质卓殊,所以须要产生多线程的,于是,形成八线程后到了线上,开采先后平常占了百分百的CPU,查看饭店,你会发现先后都Hang在了HashMap.get()那个办法上了,重启程序后难点未有。可是过段时间又会来。何况,那一个主题素材在测量试验境遇里可能很难重现。

我们差十分的少的看一下我们和好的代码,大家就明白HashMap被七个线程操作。而Java的文书档案说HashMap是非线程安全的,应该用ConcurrentHashMap。不过在那边大家能够来商讨一下缘故。简单代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
package com.king.hashmap;
 
import java.util.HashMap;
 
public class TestLock {
 
    private HashMap map = new HashMap();
 
    public TestLock() {
        Thread t1 = new Thread() {
            public void run() {
                for (int i = 0; i < 50000; i++) {
                    map.put(new Integer(i), i);
                }
                System.out.println("t1 over");
            }
        };
 
        Thread t2 = new Thread() {
            public void run() {
                for (int i = 0; i < 50000; i++) {
                    map.put(new Integer(i), i);
                }
 
                System.out.println("t2 over");
            }
        };
 
        Thread t3 = new Thread() {
            public void run() {
                for (int i = 0; i < 50000; i++) {
                    map.put(new Integer(i), i);
                }
 
                System.out.println("t3 over");
            }
        };
 
        Thread t4 = new Thread() {
            public void run() {
                for (int i = 0; i < 50000; i++) {
                    map.put(new Integer(i), i);
                }
 
                System.out.println("t4 over");
            }
        };
 
        Thread t5 = new Thread() {
            public void run() {
                for (int i = 0; i < 50000; i++) {
                    map.put(new Integer(i), i);
                }
 
                System.out.println("t5 over");
            }
        };
 
        Thread t6 = new Thread() {
            public void run() {
                for (int i = 0; i < 50000; i++) {
                    map.get(new Integer(i));
                }
 
                System.out.println("t6 over");
            }
        };
 
        Thread t7 = new Thread() {
            public void run() {
                for (int i = 0; i < 50000; i++) {
                    map.get(new Integer(i));
                }
 
                System.out.println("t7 over");
            }
        };
 
        Thread t8 = new Thread() {
            public void run() {
                for (int i = 0; i < 50000; i++) {
                    map.get(new Integer(i));
                }
 
                System.out.println("t8 over");
            }
        };
 
        Thread t9 = new Thread() {
            public void run() {
                for (int i = 0; i < 50000; i++) {
                    map.get(new Integer(i));
                }
 
                System.out.println("t9 over");
            }
        };
 
        Thread t10 = new Thread() {
            public void run() {
                for (int i = 0; i < 50000; i++) {
                    map.get(new Integer(i));
                }
 
                System.out.println("t10 over");
            }
        };
 
        t1.start();
        t2.start();
        t3.start();
        t4.start();
        t5.start();
 
        t6.start();
        t7.start();
        t8.start();
        t9.start();
        t10.start();
    }
 
    public static void main(String[] args) {
        new TestLock();
    }
}

正是启了十个线程,不断的往三个非线程安全的HashMap中put内容/get内容,put的开始和结果很粗大略,key和value都以从0自增的莫西干发型(这一个put的内容做的并不佳,以致于后来干扰了本人解析难题的笔触)。对HashMap做并发写操作,小编原感到只可是会爆发脏数据的景色,但反复运营那一个顺序,会油然则生线程t1、t2被hang住的景况,许多意况下是一个线程被hang住另四当中标甘休,偶然会12个线程都被hang住。

发出那个死循环的发源在于对一个未爱戴的分享变量 —
多个”HashMap”数据结构的操作。当在富有操作的秘技上加了”synchronized”后,一切恢复生机了例行。那算jvm的bug吗?应该说不是的,这几个处境很早在此之前就告知出来了。Sun的程序员并不以为那是bug,而是提议在如此的景色下应运用”ConcurrentHashMap”,

CPU利用率过高级中学一年级般是因为出现了出现了死循环,导致部分线程一贯运营,占用cpu时间。难点由来正是HashMap是非线程安全的,四个线程put的时候造成了有些key值Entry
key List的死循环,难点就那样产生了。

当别的贰个线程get 那些Entry List
死循环的key的时候,那一个get也会间接进行。最终结果是更加多的线程死循环,最终导致服务器dang掉。大家一般感到HashMap重复插入有个别值的时候,会覆盖此前的值,那个准确。可是对于八线程访问的时候,由于其内部贯彻机制(在二十八线程境並且未香港作家联谊会晤的景观下,对同三个HashMap做put操作只怕引致五个或上述线程同有的时候间做rehash动作,就或许形成循环键表出现,一旦出现线程将不能够停止,持续攻克CPU,导致CPU使用率只多相当的多),就大概现身安全主题素材了。

使用jstack工具dump出难点的那台服务器的栈音信。死循环的话,首先查找RUNNABLE的线程,找到标题代码如下:

java.lang.Thread.State:RUNNABLE
at java.util.HashMap.get(HashMap.java:303)
at
com.sohu.twap.service.logic.TransformTweeter.doTransformTweetT5(TransformTweeter.java:183)
共出现了二十三遍。
java.lang.Thread.State:RUNNABLE
at java.util.HashMap.put(HashMap.java:374)
at
com.sohu.twap.service.logic.TransformTweeter.transformT5(TransformTweeter.java:816)
共出现了3次。

注意:不客观施用HashMap导致出现的是死循环并非死锁。

package com.king.hashmap;import java.util.HashMap;public class TestLock { private HashMap map = new HashMap(); public TestLock() { Thread t1 = new Thread() { public void run() { for (int i = 0; i < 50000; i++) { map.put(new Integer; } System.out.println("t1 over"); } }; Thread t2 = new Thread() { public void run() { for (int i = 0; i < 50000; i++) { map.put(new Integer; } System.out.println("t2 over"); } }; Thread t3 = new Thread() { public void run() { for (int i = 0; i < 50000; i++) { map.put(new Integer; } System.out.println("t3 over"); } }; Thread t4 = new Thread() { public void run() { for (int i = 0; i < 50000; i++) { map.put(new Integer; } System.out.println("t4 over"); } }; Thread t5 = new Thread() { public void run() { for (int i = 0; i < 50000; i++) { map.put(new Integer; } System.out.println("t5 over"); } }; Thread t6 = new Thread() { public void run() { for (int i = 0; i < 50000; i++) { map.get(new Integer; } System.out.println("t6 over"); } }; Thread t7 = new Thread() { public void run() { for (int i = 0; i < 50000; i++) { map.get(new Integer; } System.out.println("t7 over"); } }; Thread t8 = new Thread() { public void run() { for (int i = 0; i < 50000; i++) { map.get(new Integer; } System.out.println("t8 over"); } }; Thread t9 = new Thread() { public void run() { for (int i = 0; i < 50000; i++) { map.get(new Integer; } System.out.println("t9 over"); } }; Thread t10 = new Thread() { public void run() { for (int i = 0; i < 50000; i++) { map.get(new Integer; } System.out.println("t10 over"); } }; t1.start(); t2.start(); t3.start(); t4.start(); t5.start(); t6.start(); t7.start(); t8.start(); t9.start(); t10.start(); } public static void main(String[] args) { new TestLock(); }}

怎么出现死循环?

大家都驾驭,HashMap采纳链表化解Hash争辩,具体的HashMap的辨析能够参照一下Java集合—HashMap源码分析 的辨析。因为是链表结构,那么就很轻巧产生闭合的链路,那样在循环的时候借使有线程对那几个HashMap进行get操作就能够发出死循环。可是,我好奇的是,这种闭合的链路是怎样产生的吧。在单线程情形下,独有一个线程对HashMap的数据结构举行操作,是不容许发生闭合的回路的。那就唯有在八线程并发的场所下才会冒出这种气象,那正是在put操作的时候,假诺size>initialCapacity*loadFactor,那么此时候HashMap就能进展rehash操作,随之HashMap的组织就能产生天崩地裂的变通。很有相当大概率正是在多少个线程在这年还要触发了rehash操作,发生了关闭的回路。

下边大家从源码中一步一步地深入分析这种回路是哪些发生的。先看一下put操作:

十六线程put的时候也许变成成分错过

要害难点出在addEntry方法的new Entry (hash, key, value,
e),假使五个线程都同时获得了e,则他们下三个成分都以e,然后赋值给table成分的时候有一个成功有二个没有征兆就不见了。

多线程put的时候可能导致成分错失

紧要难题出在addEntry方法的new Entry (hash, key, value,
e),假使四个线程都相同的时候获得了e,则他们下一个因素都以e,然后赋值给table成分的时候有叁个得逞有多少个有失。

便是启了十二个线程,不断的往贰个非线程安全的HashMap中put/get内容,put的从头到尾的经过很不难,key和value都以从0自增的莫西干发型(那么些put的剧情做的并不佳,以至于后来困扰了本人解析难点的笔触)。对HashMap做并发写操作,笔者原认为只然则会爆发脏数据的景况,但再三运营这些顺序,会出现线程t1、t2被hang住的情况,多数情况下是一个线程被hang住另一个成功结束,偶尔会10个线程都被hang住

仓库储存数据put

public V put(K key, V value)
{
    ......
    //算Hash值
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    //如果该key已被插入,则替换掉旧的value (链接操作)
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    //该key不存在,需要增加一个结点
    addEntry(hash, key, value, i);
    return null;
}

当大家往HashMap中put成分的时候,先依照key的hash值得到这一个因素在数组中的地方(即下标),然后就足以把那些成分放到对应的岗位中了。
假使那么些因素所在的任务上早就存放有任何因素了,那么在同一个座位上的因素将以链表的款型贮存,新到场的放在链头,而原先参预的位于链尾。

put非null成分后get出来的却是null

在transfer方法中代码如下:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 void transfer(Entry[] newTable) {     Entry[] src = table;     int newCapacity = newTable.length;     for (int j = 0; j < src.length; j++) {         Entry e = src[j];         if (e != null) {             src[j] = null;             do {                 Entry next = e.next;                 int i = indexFor(e.hash, newCapacity);                 e.next = newTable[i];                 newTable[i] = e;                 e = next;             while (e != null);         }     } }

在这一个方法里,将旧数组赋值给src,遍历src,当src的要素非null时,就将src中的该成分置null,将在旧数组中的元素置null了,约等于这一句:

1 2 if (e != null) {         src[j] = null;

那时若有get方法访问这些key,它赢得的依旧旧数组,当然就取不到其相应的value了。

小结:HashMap未同步时在并发程序中会爆发过多神奇的标题,难以从外边找到原因。所以选取HashMap出现了反其道而行之直觉的场景,那么恐怕便是出新导致的了。

put非null成分后get出来的却是null

在transfer方法中代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            while (e != null);
        }
    }
}

在这些方法里,将旧数组赋值给src,遍历src,当src的要素非null时,就将src中的该成分置null,将要旧数组中的成分置null了,也正是这一句:

1
2
if (e != null) {
        src[j] = null;

那时若有get方法访谈那些key,它获得的依旧旧数组,当然就取不到其对应的value了。

小结:HashMap未同步时在并发程序中会发生比非常多神奇的主题素材,难以从外边找到原因。所以利用HashMap现身了反其道而行之直觉的光景,那么恐怕正是出新导致的了。

产生这个死循环的根源在于对一个未保护的共享变量 — 一个"HashMap"数据结构的操作。当在全体操作的主意上加了”synchronized”后,一切恢复生机了健康。这算JDK的bug吗?应该说不是的,那一个情景很早以前就告知出来了。Sun的工程师并不认为这是bug,而是建议在这样的场景下应采用"ConcurrentHashMap"

反省体积是或不是超标addEntry

能够看来,若是明日size已经超(英文名:jīng chāo)过了threshold,那么将在进行resize操作,新建四个更加大尺寸的hash表,然后把多少从老的Hash表中迁移到新的Hash表中:

HashMap数据结构

自笔者索要简单地说一下HashMap这些特出的数据结构。

HashMap经常会用二个指针数组(要是为table[])来做分散全部的key,当一个key被参预时,会通过Hash算法通过key算出这些数组的下标i,然后就把这个插到table[i]中,若是有四个不等的key被算在了同二个i,那么就叫冲突,又叫碰撞,那样会在table[i]上变成三个链表。

咱俩掌握,要是table[]的尺码异常的小,比方唯有2个,假设要放进11个keys的话,那么碰撞极其频繁,于是一个O(1)的查究算法,就产生了链表遍历,品质变成了O(n),这是Hash表的欠缺。

于是,Hash表的尺码和容积非常的尤为重要。一般的话,Hash表那一个容器当有数量要插入时,都会检讨体积有未有超过设定的thredhold,借使超越,供给增大Hash表的尺寸,不过那样一来,整个Hash表里的因素都必要被重算一次。那叫rehash,那些资金相当的大。

HashMap数据结构

自己索要简单地说一下HashMap这些精粹的数据结构。

HashMap平时会用四个指针数组(借使为table[])来做分散全体的key,当一个key被参预时,会透过Hash算法通过key算出这几个数组的下标i,然后就把这个插到table[i]中,如若有七个不等的key被算在了同三个i,那么就叫争执,又叫碰撞,那样会在table[i]上产生叁个链表。

大家精晓,假使table[]的尺寸相当的小,譬如独有2个,借使要放进13个keys的话,那么碰撞非常频仍,于是二个O(1)的追寻算法,就改为了链表遍历,品质形成了O(n),那是Hash表的毛病。

进而,Hash表的尺码和体积特别的要害。一般的话,Hash表那几个容器当有数量要插入时,都会检讨容积有未有超越设定的thredhold,假诺超过,须求增大Hash表的尺寸,可是那样一来,整个Hash表里的因素都急需被重算一回。那叫rehash,那个开销十分的大。

CPU利用率过高一般是因为出现了出现了死循环,导致部分线程一直运行,占用cpu时间。问题原因就是HashMap是非线程安全的,多个线程put的时候造成了某个key值Entry key List的死循环,问题就这么产生了。

调整Hash表大小resize

void resize(int newCapacity)
{
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    ......
    //创建一个新的Hash Table
    Entry[] newTable = new Entry[newCapacity];
    //将Old Hash Table上的数据迁移到New Hash Table上
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

当table[]数组容积相当小,轻松发生哈希碰撞,所以,Hash表的尺码和体积非常的要紧。一般的话,Hash表那个容器当有数量要插入时,都会检讨体积有未有抢先设定的thredhold,假使超越,须求增大Hash表的尺寸,那几个进程称为resize。

四个线程同偶然候往HashMap增多新成分时,数次resize会有自然可能率出现死循环,因为老是resize供给把旧的数码映射到新的哈希表,这一局地代码在HashMap#transfer()
方法,如下:

void transfer(Entry[] newTable)
{
    Entry[] src = table;
    int newCapacity = newTable.length;
    //下面这段代码的意思是:
    //  从OldTable里摘一个元素出来,然后放到NewTable中
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

金红部分代码是引致十二线程使用hashmap现身CUP使用率激增,进而多少个线程阻塞的首恶祸首。

八线程下 [HashMap] 的标题: 1、多线程put操作后,get操作产生死循环。
2、二十多线程put非NULL成分后,…

HashMap的rehash源代码

上边,大家来看一下Java的HashMap的源代码。Put七个Key,Value对到Hash表中:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public V put(K key, V value) {     ......     //算Hash值     int hash = hash(key.hashCode());     int i = indexFor(hash, table.length);     //如果该key已被插入,则替换掉旧的value (链接操作)     for (Entry<K,V> e = table[i]; e != null; e = e.next) {         Object k;         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {             V oldValue = e.value;             e.value = value;             e.recordAccess(this);             return oldValue;         }     }     modCount++;     //该key不存在,需要增加一个结点     addEntry(hash, key, value, i);     return null; }

检查体积是或不是超过标准:

1 2 3 4 5 6 7 8 void addEntry(int hash, K key, V value, int bucketIndex) {     Entry<K,V> e = table[bucketIndex];     table[bucketIndex] = new Entry<K,V>(hash, key, value, e);     //查看当前的size是否超过了我们设定的阈值threshold,如果超过,需要resize     if (size++ >= threshold)         resize(2 * table.length); }

新建三个越来越大尺寸的hash表,然后把数量从老的Hash表中迁移到新的Hash表中。

1 2 3 4 5 6 7 8 9 10 11 12 void resize(int newCapacity) {     Entry[] oldTable = table;     int oldCapacity = oldTable.length;     ......     //创建一个新的Hash Table     Entry[] newTable = new Entry[newCapacity];     //将Old Hash Table上的数据迁移到New Hash Table上     transfer(newTable);     table = newTable;     threshold = (int)(newCapacity * loadFactor); }

搬迁的源代码,注意高亮处:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 void transfer(Entry[] newTable) {     Entry[] src = table;     int newCapacity = newTable.length;     //下面这段代码的意思是:     //  从OldTable里摘一个元素出来,然后放到NewTable中     for (int j = 0; j < src.length; j++) {         Entry<K,V> e = src[j];         if (e != null) {             src[j] = null;             do {                 Entry<K,V> next = e.next;                 int i = indexFor(e.hash, newCapacity);                 e.next = newTable[i];                 newTable[i] = e;                 e = next;             while (e != null);         }     } }

好了,那么些代码算是相比符合规律的。并且从不什么难题。

HashMap的rehash源代码

下边,我们来看一下Java的HashMap的源代码。Put一个Key,Value对到Hash表中:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public V put(K key, V value)
{
    ......
    //算Hash值
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    //如果该key已被插入,则替换掉旧的value (链接操作)
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    //该key不存在,需要增加一个结点
    addEntry(hash, key, value, i);
    return null;
}

反省体积是或不是超过规范:

1
2
3
4
5
6
7
8
void addEntry(int hash, K key, V value, int bucketIndex)
{
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    //查看当前的size是否超过了我们设定的阈值threshold,如果超过,需要resize
    if (size++ >= threshold)
        resize(2 * table.length);
}

新建二个越来越大尺寸的hash表,然后把数据从老的Hash表中迁移到新的Hash表中。

1
2
3
4
5
6
7
8
9
10
11
12
void resize(int newCapacity)
{
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    ......
    //创建一个新的Hash Table
    Entry[] newTable = new Entry[newCapacity];
    //将Old Hash Table上的数据迁移到New Hash Table上
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

搬迁的源代码,注意高亮处:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void transfer(Entry[] newTable)
{
    Entry[] src = table;
    int newCapacity = newTable.length;
    //下面这段代码的意思是:
    //  从OldTable里摘一个元素出来,然后放到NewTable中
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            while (e != null);
        }
    }
}

好了,那一个代码算是比较正规的。何况尚未什么样难点。

当别的二个线程get 这几个Entry List
死循环的key的时候,那些get也会直接施行。最终结果是进一步多的线程死循环,最终产生服务器dang掉。大家一般感到HashMap重复插入某些值的时候,会覆盖从前的值,那几个准确。但是对于多线程访问的时候,由于其内部实现机制(在多线程环境且未作同步的情况下,对同一个HashMap做put操作可能导致两个或以上线程同时做rehash动作,就可能导致循环键表出现,一旦出现线程将无法终止,持续占用CPU,导致CPU使用率居高不下),就可能出现安全问题了

正常的ReHash过程

画了个图做了个示范。

金沙澳门官网7817网址 1

正常的ReHash过程

画了个图做了个示范。

  1. 笔者借使了我们的hash算法正是简约的用key mod
    一下表的深浅(也正是数组的长短)。
  2. 最下面的是old hash 表,在这之中的Hash表的size=2, 所以key = 3, 7,
    5,在mod
    2未来都争执在table1这里了。
  3. 接下去的多少个步骤是Hash表 resize成4,然后全部的 重新rehash的历程。

金沙澳门官网7817网址 2

行使jstack工具dump出难点的那台服务器的栈音讯。死循环的话,首先查找RUNNABLE的线程,找到标题代码如下:

并发的Rehash过程

(1)倘使大家有五个线程。小编用浅灰和青暗褐注解了须臾间。大家再回头看一下咱们的
transfer代码中的这么些细节:

1 2 3 4 5 6 7 do {     Entry<K,V> next = e.next; // <--假设线程一执行到这里就被调度挂起了     int i = indexFor(e.hash, newCapacity);     e.next = newTable[i];     newTable[i] = e;     e = next; while (e != null);

而作者辈的线程二实施到位了。于是我们有上面包车型客车那么些样子。
金沙澳门官网7817网址 3

专注:因为Thread1的 e
指向了key(3),而next指向了key(7),其在线程二rehash后,指向了线程二重组后的链表。大家得以看来链表的次第被反转后。
(2)线程一被调整回来施行。

金沙澳门官网7817网址 4
(3)一切安好。
线程一随之专业。把key(7)摘下来,放到newTable[i]的第八个,然后把e和next往下移。
金沙澳门官网7817网址 5
(4)环形链接现身。
e.next = newTable[i] 导致 key(3).next 指向了
key(7)。注意:此时的key(7).next 已经针对了key(3),
环形链表就那样出现了。
金沙澳门官网7817网址 6
于是,当大家的线程一调用到,HashTable.get(11)时,正剧就应际而生了——Infinite
Loop。

并发的Rehash过程

(1)借使大家有多个线程。自己用紫铁黄和青绿蓝标明了瞬间。大家再回头看一下大家的
transfer代码中的那些细节:

1
2
3
4
5
6
7
do {
    Entry<K,V> next = e.next; // <--假设线程一执行到这里就被调度挂起了
    int i = indexFor(e.hash, newCapacity);
    e.next = newTable[i];
    newTable[i] = e;
    e = next;
while (e != null);

而大家的线程二进行到位了。于是大家有下边包车型地铁那一个样子。
金沙澳门官网7817网址 7

专注:因为Thread1的 e
指向了key(3),而next指向了key(7),其在线程二rehash后,指向了线程二重组后的链表。大家得以看出链表的顺序被反转后。
(2)线程一被调解回来实践。

  1. 第一实践 newTalbe[i] = e。
  2. 然后是e = next,导致了e指向了key(7)。
  3. 而下三回巡回的next = e.next导致了next指向了key(3)。

金沙澳门官网7817网址 8
(3)一切安好。
线程一接着专业。把key(7)摘下来,放到newTable[i]的第二个,然后把e和next往下移。
金沙澳门官网7817网址 9
(4)环形链接出现。
e.next = newTable[i] 导致 key(3).next 指向了
key(7)。注意:此时的key(7).next 已经针对了key(3),
环形链表就这么出现了。
金沙澳门官网7817网址 10
于是,当我们的线程一调用到,HashTable.get(11)时,正剧就应际而生了——Infinite
Loop。

java.lang.Thread.State:RUNNABLEat
java.util.HashMap.get(HashMap.java:303)at
com.sohu.twap.service.logic.TransformTweeter.doTransformTweetT5(TransformTweeter.java:183)共出现了25回。java.lang.Thread.State:RUNNABLEat
java.util.HashMap.put(HashMap.java:374)at
com.sohu.twap.service.logic.TransformTweeter.transformT5(TransformTweeter.java:816)共出现了3次。

注意:不成立运用HashMap导致现身的是死循环实际不是死锁。

三种减轻方案

两种减轻方案

十分重要难题出在addEntry方法的new Entry<K,V>(hash, key, value,
e),若是多个线程都相同的时候得到了e,则他们下叁个元素都以e,然后赋值给table成分的时候有贰当中标有二个放任。

Hashtable替换HashMap

Hashtable 是同台的,但由迭代器再次来到的 Iterator 和由具备 Hashtable
的“collection 视图方法”重临的 Collection 的 listIterator
方法都以全速退步的:在开创 Iterator 之后,如若从组织上对 Hashtable
进行退换,除非通过 Iterator
自己的移除或增加方法,不然在其余时间以其余措施对其进展退换,Iterator
都将抛出 ConcurrentModificationException。因而,面临并发的修改,Iterator
相当的慢就能够完全退步,而不冒在未来有些不明确的年月产生自便不显然行为的高风险。由
Hashtable 的键和值方法重回的 Enumeration 不是快速退步的。

瞩目,迭代器的迅速失利行为不可能获得保证,因为相似的话,不可能对是不是出现不相同台出现修改做出其余硬性保障。快速退步迭代器会尽最大大力抛出
ConcurrentModificationException。因而,为增高那类迭代器的没有错而编写叁个借助于此至极的主次是错误做法:迭代器的火速战败行为应当仅用于检查评定程序错误。

Hashtable替换HashMap

Hashtable 是一块的,但由迭代器再次回到的 Iterator 和由具有 Hashtable
的“collection 视图方法”再次来到的 Collection 的 listIterator
方法都以高效战败的:在开立 Iterator 之后,若是从布局上对 Hashtable
进行改变,除非通过 Iterator
本身的移除或丰盛方法,不然在其余时刻以另外措施对其进展修改,Iterator
都将抛出 ConcurrentModificationException。由此,面临并发的更动,Iterator
异常快就能全盘战败,而不冒在今后某些不鲜明的大运发出率性不分明行为的高危害。由
Hashtable 的键和值方法重回的 Enumeration 不是便捷战败的。

瞩目,迭代器的高效战败行为不也许获取保证,因为一般的话,不可能对是还是不是出现不一同出现修改做出别的硬性保障。急迅战败迭代器会尽最大大力抛出
ConcurrentModificationException。因而,为巩固那类迭代器的不利而编辑两个依赖于此卓殊的次第是错误做法:迭代器的迅猛退步行为应该仅用于检查实验程序不当。

在transfer方法中代码如下:

Collections.synchronizedMap将HashMap包装起来

再次回到由钦赐映射扶助的一路(线程安全的)映射。为了确定保证按顺序访问,必须透过重返的映照达成对底层映射的有着访谈。在回来的照耀或其肆意collection 视图上拓展迭代时,强制用户手工在回到的炫彩上进行同步:

1 2 3 4 5 6 7 8 9 Map m = Collections.synchronizedMap(new HashMap()); ... Set s = m.keySet();  // Needn't be in synchronized block ... synchronized(m) {  // Synchronizing on m, not s! Iterator i = s.iterator(); // Must be in synchronized block     while (i.hasNext())         foo(i.next()); }

不遵守此建议将产生不能够鲜明的一坐一起。若是钦点映射是可连串化的,则赶回的炫丽也将是可种类化的。

Collections.synchronizedMap将HashMap包装起来

回来由内定映射帮忙的一块(线程安全的)映射。为了保障按梯次访谈,必须透过重临的映射完毕对底层映射的具备访谈。在回到的映照或其放肆collection 视图上开始展览迭代时,强制用户手工业在再次回到的照耀上海展览中心开协同:

1
2
3
4
5
6
7
8
9
Map m = Collections.synchronizedMap(new HashMap());
...
Set s = m.keySet();  // Needn't be in synchronized block
...
synchronized(m) {  // Synchronizing on m, not s!
Iterator i = s.iterator(); // Must be in synchronized block
    while (i.hasNext())
        foo(i.next());
}

不服从此建议将招致力不能及鲜明的表现。假若钦点映射是可系列化的,则赶回的照耀也将是可种类化的。

void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry e = src[j]; if (e != null) { src[j] = null; do { Entry next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } }}

ConcurrentHashMap替换HashMap

援救检索的通通并发和翻新的所企望可调动现身的哈希表。此类遵循与 Hashtable
同样的功效规范,並且囊括对应于 Hashtable
的每一种方法的法门版本。可是,即便有所操作都是线程安全的,但搜索操作不必锁定,而且不帮忙以某种幸免全体访谈的措施锁定任何表。此类能够因而程序完全与
Hashtable 举办互操作,那取决其线程安全,而与其一齐细节毫无干系。
找寻操作(富含 get)常常不会受阻塞,由此,恐怕与更新操作交迭(包罗 put
和 remove)。检索会耳熏目染如今形成的换代操作的结果。对于部分汇集操作,比方putAll 和
clear,并发检索大概只影响有些条约的插入和移除。类似地,在开创迭代器/枚举时或未来之后,Iterators
和 Enumerations 再次回到在某临时间点上海电影制片厂响哈希表状态的要素。它们不会抛出
ConcurrentModificationException。然而,迭代器被设计成每一次仅由三个线程使用。

QQ技能交换群290551701 

原著出处:陶邦仁 并发难点的症状 十二线程put后恐怕引致get死循环
在此以前我们的Java代码因为有的…

ConcurrentHashMap替换HashMap

支撑检索的完全并发和更新的所愿意可调动出现的哈希表。此类遵循与 Hashtable
同样的效果规范,并且包涵对应于 Hashtable
的各类方法的方法版本。可是,就算具有操作都以线程安全的,但寻觅操作不必锁定,并且不支持以某种幸免全体访谈的办法锁定任何表。此类能够透进度序完全与
Hashtable 实行互操作,那取决其线程安全,而与其伙同细节无关。
检索操作(包涵 get)平日不会受阻塞,由此,只怕与立异操作交迭(包罗 put
和 remove)。检索会耳闻则诵近期达成的立异操作的结果。对于部分会晤操作,比如putAll 和
clear,并发检索只怕只影响某个条目的插入和移除。类似地,在创造迭代器/枚举时或之后未来,Iterators
和 Enumerations 再次来到在某一时间点上海电影制片厂响哈希表状态的要素。它们不会抛出
ConcurrentModificationException。可是,迭代器被规划成每一次仅由三个线程使用。

QQ本领交换群290551701 

在这几个方法里,将旧数组赋值给src,遍历src,当src的成分非null时,就将src中的该成分置null,就要旧数组中的成分置null了,也正是这一句: