微信号:javalm

介绍:莫道君行早,更有早行人;;全心敲代码,天道自酬勤

Java面试题7 | HashMap并发问题

2019-01-11 11:30 Java程序员联盟

点击蓝色文字关注我们哦

       


我们知道HashMap线程不安全,在并发环境下会发生死锁问题,将导致CPU占用率接近100%。其实死锁的说法并不很贴切,应该说是一种死循环。在JDK 1.8中,Map相关类的实现发生了很大变化,引入了红黑树的概念,本篇以JDK 1.7中的实现方式讲解HashMap的并发问题,以方便理解。





说明

JDK 1.8和JDK 1.7中,Map相关类的大体实现思想变化不大,知识引入了红黑树的概念,使得类中增加了生成红黑树的方法,相关的一些重要方法,例如添加元素,重置集合大小等方法也做出相应改变。
上述这些变化主要是为了提高集合的查询效率,思想还是原来的思想,因此JDK 1.7中的源代码更能方便理解。

HashMap并发死锁问题

该问题的成因涉及到四个方法,最初的起因是调用put()方法,跟着方法走一遍:
put()方法源码(只给出核心部分):


   
             
  1. public V put(K key, V value)

  2. {

  3. ......

  4. //计算Hash值

  5. int hash = hash(key.hashCode());

  6. int i = indexFor(hash, table.length);

  7. //如果该key已存在,则替换掉旧的value

  8. for (Entry<K,V> e = table[i]; e != null; e = e.next) {

  9. Object k;

  10. if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

  11. V oldValue = e.value;

  12. e.value = value;

  13. e.recordAccess(this);

  14. return oldValue;

  15. }

  16. }

  17. modCount++;

  18. //该key不存在,需要增加一个结点

  19. addEntry(hash, key, value, i);

  20. return null;

  21. }

当key不存在时,调用addEntry()方法添加新节点。方法源码如下:


   
             
  1. void addEntry(int hash, K key, V value, int bucketIndex)

  2. {

  3. Entry<K,V> e = table[bucketIndex];

  4. table[bucketIndex] = new Entry<K,V>(hash, key, value, e);

  5. //查看当前的size是否超过了阈值threshold,如果超过,需要resize

  6. if (size++ >= threshold)

  7. resize(2 * table.length);

  8. }

resize()方法就是产生并发死锁的原因


   
             
  1. void resize(int newCapacity)

  2. {

  3. Entry[] oldTable = table;

  4. int oldCapacity = oldTable.length;

  5. ......

  6. //创建一个新的Hash Table

  7. Entry[] newTable = new Entry[newCapacity];

  8. //将Old Hash Table上的数据迁移到New Hash Table上

  9. transfer(newTable);

  10. table = newTable;

  11. threshold = (int)(newCapacity * loadFactor);

  12. }

resize()方法的本质就是创建新的Entry数组,将原Map中的元素重新计算位置,加入到新的Map中。虽然死锁的成因是扩充时调用resize()方法,但真正的产生是发生在倒数第三行的transfer()方法中。


   
             
  1. void transfer(Entry[] newTable)

  2. {

  3. Entry[] src = table;

  4. int newCapacity = newTable.length;

  5. //从OldTable将元素一个个拿出来,然后放到NewTable中

  6. for (int j = 0; j < src.length; j++) {

  7. Entry<K,V> e = src[j];

  8. if (e != null) {

  9. src[j] = null;

  10. do {

  11. Entry<K,V> next = e.next;

  12. //计算节点在新的Map中的位置

  13. int i = indexFor(e.hash, newCapacity);

  14. e.next = newTable[i];

  15. newTable[i] = e;

  16. e = next;

  17. } while (e != null);

  18. }

  19. }

  20. }



大体过程如下(摘自网上大神的博客)

 

transfe过程

假设hash算法就是简单的用key mod Entry数组的长度。这里一定注意e和next的指向,当并发resize()时,这两个指针对于死锁产生起着至关重要的作用。根据方法执行情况,原Map中的链表元素在新的Map中将顺序颠倒,如上图所示,经过一次resize()后key为7的节点排在了key为3的节点之前。


   
             
  1. do {

  2. Entry<K,V> next = e.next;

  3. //计算节点在新的Map中的位置

  4. int i = indexFor(e.hash, newCapacity);

  5. e.next = newTable[i];

  6. newTable[i] = e;

  7. e = next;

  8. } while (e != null);

再次黏贴这段代码就是强调这个do while循环就是产生死锁的罪魁祸首。下面模拟死锁产生的过程。
注意,并非所有情况下都会产生死锁,这也需要线程之间的默契配合,怎么讲呢,如图所示:


   
             
  1. do {

  2. Entry<K,V> next = e.next; //假设线程一执行至此被挂起,执行线程二

  3. int i = indexFor(e.hash, newCapacity);

  4. e.next = newTable[i];

  5. newTable[i] = e;

  6. e = next;

  7. } while (e != null);

线程一的记录状态

此时线程一,e指向key为3的节点,next指向key为7的节点。这点很重要,记下来。去执行线程二。
假设线程二正常执行,结束后的状态如下:

线程二正常执行

此时线程一被唤醒,线程一的工作空间里,e和next指向的元素依旧是key为3和7的节点。线程一开始执行。


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

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

  3. 而下一次循环的next = e.next导致了next指向了key(3)。

线程一执行

目前还没发生问题,线程一接着工作。把key(7)摘下来,放到newTable[i]的第一个,然后把e和next往下移。

线程一执行

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



死锁产生
这个过程不好理解,最好多读几遍,当产生带环链表后,如果调用get()方法,将会陷入死循环,CPU占用将达到100%。解决这一问题的方式有多种。比较low的可以使用HashTable和调用Collections工具类的synchronizedMap()方法达到线程安全的目的。但由于synchronized是串行执行,在访问量很大的情况下效率很低,不推荐使用。
另外一种方式就是使用JUC包下的ConcurrentHashMap类,这个类很好的解决了多线程环境下的并发问题。

【面试必备】常见Java面试题大综合



作者:CSDN   lby0307

原文: 

https://blog.csdn.net/lby0307/article/details/81836307


欢迎关注 Java程序员联盟(javalm)

 
Java程序员联盟 更多文章 Java面试题 | Java泛型深入理解 Java面试题 | Java实现动态代理的两种方式 Java面试题 | 线程池原理及调度过程1 产品经理历险记1 | 记录一次重大线上事故 产品经理历险记2 | 如何把需求聊得更细
猜您喜欢 有了CodinGame,玩着游戏就能学编程 Javascript核心 白话蓝石链(CefaChain) 制定大数据纲要,李克强强调三个“关键词” 前世今生走一走,方知套路有没有!