前面三篇系列文章分别介绍了

  1. HashMap详解(1)- 注释解读
  2. HashMap详解(2)- 存储结构、Entry、get/put方法
  3. HashMap详解(3)- rehash(resize)的过程

通过这三篇文章,基本上了解了HashMap是怎么回事,在使用Hashmap时也更加的得心应手,不过HashMap在多线程使用的过程中是存在问题的,这一点在第一篇文章里介绍过,即javadoc里面明确说了,在多线程的环境中,HashMap是有问题的,尽量不要使用,即在一个多线程环境中,HashMap作为一个共享资源,它在被使用的过程中是会出现问题,具体表现为下面三个问题,本篇文章就来介绍一下。

(1)多线程put导致数据丢失

首先来看一下出问题的这段代码:

addEntry

 

主要问题出在addEntry方法的new Entry<K,V>(hash, key, value, e),如果两个线程都同时取得了e,即同时执行到了上图中红色标注的这行,比如A线程的a元素以及B线程的b元素,他们下一个元素都是e,这是后假设A线程先执行,这样,table[bucketIndex] = a,然后B线程执行,table[bucketIndex] = b,这样就造成了赋值给table[bucketIndex]时,一个成功了,一个失败了,失败的这个就是所谓了数据丢失。

(2)多线程put非null元素,但是get时却是null

这段代码主要是出现在resize的过程中,关于resize,前一篇文章介绍过    HashMap详解(3)- rehash(resize)的过程 ,即在put的过程中,程序会判断容量情况,如果需要扩容,就会调用resize函数,resize里面有一个transfer函数,这个函数截图如下:

transfer

出问题的就是标红的这段代码   src[j] = null;  当多线程执行的过程中,某一个线程正好put元素的时候,触发了resize,然后执行到这行,把这个 src[j]置为null,这里实际上就是把原始table变为null,至于这里为什么变为null,是因为代码中新建了一个newTable,resize操作完成后,就是用这个newTable了,所以原来table自然就没用了。但是在多线程环境中,如果有线程正好在别的线程把这个 src[j]置为null的时候需要get这个元素,那么get到的结果就是null。这就是所谓的多线程put非null元素,但是get时却是null

(3)多线程put后,get可能出现死循环

前面两个HashMap多线程的问题比较好理解,而第三个这个问题得深入到代码中理解了,发生的场景依旧是多线程对同一个HashMap的多次put操作触发了resize操作,而就是这个transfer函数导致出现的这个问题。http://my.oschina.net/xianggao/blog/393990   这篇文章分析了这个问题,而且画图动态展示了一下。本身觉得我这里就不画了,不过为了加强自己的记忆。我这里也画画图,来更加清晰的表达这个问题争取让所有人看一次就知道transfer里到底是怎么操作的。

前提准备,我们先建立一个容量是4的hashmap,负载因子使用默认的0.75。然后往里面put进3,5,11,0当put 0的时候,由于前面已经有了3个数字,达到了4*0.75 =3 的扩容条件,这里分析的就是当put 0 完成时,hashmap内部的resize的过程,下面是测试的程序。

Map<Integer,Integer> map = new HashMap<Integer,Integer>(4);
 map.put(3,3);
 map.put(5,5);
 map.put(11,11);
 map.put(0,0);

当put 0的时候,此时当HashMap内部执行到resize之前的结构是:

befresize

 

下面讨论一下,正常情况下resize的过程以及多线程下出现死循环的resize的过程:

正常resize:

前两个步骤很简单,就是把0和5,重新再容量为8的table里放进去而已:

firststep

 

接下来是重点了,就是3和11的位置,由于3和11,在容量4和8的index都是一样的,意味着他们在一个table[index]里

thirdstep

 

以上四步就是正常的resize里面 transfer函数的流程。

下面说一下多线程情况下出现死循环的情况,假设目前有线程A和线程B两个线程,两个线程都触发了从4到8的这个resize操作,假设线程B已经执行到上面正常resize的第三步,具体来说假设他执行到这行代码:

bug

 

即刚执行完479行,准备执行480行。从代码执行的角度来讲,此时e=key(11),而next=key(3),注意当准备执行480行的时候,假设线程A已经执行完毕,table情况如下:

threadA

我们现在来分析这几行代码:


void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
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;   //1
int i = indexFor(e.hash, newCapacity);  //2
e.next = newTable[i]; //3
newTable[i] = e;  //4
e = next;  //5
} while (e != null);  //6
}
}
}

  1. 线程B目前已经执行完1,准备执行2,目前e为key(11),next为key(3),就在此时线程A已经执行完了。
  2. 第二行是在计算index,这里index计算结果是3。
  3. 第三行表示的是把当前 newTable[3]交给e,即key(11).next = null; 因为当前newTable[3]是null。
  4. 第四行是把e赋给newTable[3],即目前newTable[3]=key(11)
  5. 第五行是将next赋给e,next在第一行那里已经得到了是key(3),所以这里e变成了key(3)
  6. 第六行判断e是否为null,这里e是key(3),不为null,继续循环

第一次while循环后,线程B的table如下:

ThreadB

 

重点来了,注意看第二次循环的情况,第二次循环是e变成了key(3)。

  1. 第一行,Entry<K,V> next = e.next;  注意这里e是key(3),而key(3).next是什么呢?由于线程A的操作,注意看上面线程A操作后的示意图,key(3).next是key(11)。注意,就是这里和单线程不一样,单线程这里key(3).next = null。注意啊
  2. 第二行计算index,为3
  3. 第三行表示的是 key(3).next = key(11)。
  4. 第四行newTable[3]=key(3)
  5. 第五行e=key(11),这里的e是第一行那里得到的。
  6. 第六行判断,e是key(11),不为null,继续循环。如果是单线程,这里是null,就会跳出while循环。

第二次执行完后,线程B的table情况

threadB2

第三次循环,e变成了key(11)

  1. 第一行Entry<K,V> next = e.next;  这时e是key(11),而next是null。
  2. 第二行计算index为3
  3. 第三行key(11).next = key(3),注意啊   此时 key(3).next 也等于 key(11),循环链表出现。
  4. 第四行newTable[3]=key(11)
  5. 第五行e = null
  6. 第六行跳出while循环

此时线程B执行结束之后的table为:

threadB3

出现了循环链表,此时如果出现了put(27)之类的操作,3,11,27都位于同一个index里就会触发这个死循环,因为put的时候首先会判断新添加的元素key是否已经存在,如果存在就直接更新value值就行,如果没找到,就新添加一个,但是在判断是否有这个key是时候,如果碰上这个循环链表,就会出现无限循环下去的结果,造成死循环,如下图所示,如果添加27进入hashmap,首先要在标红的for循环里判断,但如果碰上上面的这种循环链表的情况,这个for循环就变成了死循环。类似的如果map里没有27这个元素,get(27)的时候也会出现死循环。

put

get

介绍完多线程下HashMap的问题之后,就会出现另一个问题,碰到这种情况要怎么办呢?实际上上面提到了 http://my.oschina.net/xianggao/blog/393990  这位仁兄的博客里介绍了三种方法来替代

Hashtable替换HashMap

Hashtable 是同步的,但由迭代器返回的 Iterator 和由所有 Hashtable 的“collection 视图方法”返回的 Collection 的 listIterator 方法都是快速失败的:在创建 Iterator 之后,如果从结构上对 Hashtable 进行修改,除非通过 Iterator 自身的移除或添加方法,否则在任何时间以任何方式对其进行修改,Iterator 都将抛出 ConcurrentModificationException。因此,面对并发的修改,Iterator 很快就会完全失败,而不冒在将来某个不确定的时间发生任意不确定行为的风险。由 Hashtable 的键和值方法返回的 Enumeration 不是快速失败的。

注意,迭代器的快速失败行为无法得到保证,因为一般来说,不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此,为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误做法:迭代器的快速失败行为应该仅用于检测程序错误。

Collections.synchronizedMap将HashMap包装起来

返回由指定映射支持的同步(线程安全的)映射。为了保证按顺序访问,必须通过返回的映射完成对底层映射的所有访问。在返回的映射或其任意 collection 视图上进行迭代时,强制用户手工在返回的映射上进行同步:

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());
}

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

ConcurrentHashMap替换HashMap

支持检索的完全并发和更新的所期望可调整并发的哈希表。此类遵守与 Hashtable 相同的功能规范,并且包括对应于 Hashtable 的每个方法的方法版本。不过,尽管所有操作都是线程安全的,但检索操作不必锁定,并且不支持以某种防止所有访问的方式锁定整个表。此类可以通过程序完全与 Hashtable 进行互操作,这取决于其线程安全,而与其同步细节无关。 检索操作(包括 get)通常不会受阻塞,因此,可能与更新操作交迭(包括 put 和 remove)。检索会影响最近完成的更新操作的结果。对于一些聚合操作,比如 putAll 和 clear,并发检索可能只影响某些条目的插入和移除。类似地,在创建迭代器/枚举时或自此之后,Iterators 和 Enumerations 返回在某一时间点上影响哈希表状态的元素。它们不会抛出 ConcurrentModificationException。不过,迭代器被设计成每次仅由一个线程使用。

 

第一种方案是使用HashTable,由于HashTable是早期jdk的版本,对于整个table的操作 一次性使用synchronized来锁定全表,效率太低,故不建议使用。

第二种方案是使用 Collections.synchronizedMap 将map包装起来,同时 在使用时外部上锁,也不建议使用。

第三种方案是使用ConcurrentHashMap 来代替,这是jdk1.5的并发包带来的新的线程安全的集合类,建议使用这种方案替代,至于ConcurrentHashMap是怎么实现的,以及与HashMap和HashTable的区别,在后续的文章中会介绍。

 

 

HashMap详解(3)- rehash(resize)的过程

前面的文章介绍了 HashMap的注释,以及get,put方法和重要的Entry的内部类,今天这篇文章将主要介绍一下HashMap的rehash过程,rehash也叫作resize,实际上就...

阅读全文

HashMap详解(2)- 存储结构、Entry、get/put方法

前一章主要介绍了HashMap的总体注释,对于HashMap有一个大概的了解,这一章是最为关键的一章,里面会重点介绍HashMap的构造函数,关键属性以及存储结构,只有...

阅读全文

HashMap详解(1)- 注释解读

其实一直想认真读一下 jdk的源码,让自己感受一下高端的感觉,那么就从HashMap开始吧,因为当初自己面试就被问到HashMap的各种问题,与此同时,实际开发过程...

阅读全文

欢迎留言