面试官:JDK1.8HashMap会发生死循环吗?

一、直击面试现场

面试官:你觉得HashMap在多线程并发的情况下会出现死循环吗?

我(暗自窃喜,还好准备了):HashMap在jdk1.8之前,会因为多线程put元素操作共享hashmap会出现,原因是向链表添加元素时采用的是头插法,多线程操作链表会发生环化,此时产生死循环

面试官(紧着追问):那你说jdk1.8不会产生死循环吗?

我(心头一紧):是…是吧

面试官笑道:回去再看下吧(我知道肯定答错了)

面试官:JDK1.8HashMap会发生死循环吗?
虽不是为了面试而学习,但我觉得面试中提到的问题要不就是技术易错点,要么就是经验之谈,值得再次试验验证

二、实验开始

实验环境是jdk1.8.0_60,我们程序的含义是两个线程向同一个map添加元素,分别添加50000个不重复的元素,程序如下

public class HashMapMultiThread {      static Map<String,String> map = new HashMap<>();      public static class AddThread implements Runnable{          int start;         public AddThread(int start){             this.start=start;         }         @Override         public void run() {             System.out.println(Thread.currentThread().getName());             //添加元素             for(int i = start ; i<10000000;i+=2){                 map.put(Integer.toString(i),Integer.toBinaryString(i));             }         }     }      public static void main(String[] args) throws InterruptedException {         //开启两个线程         Thread t1 = new Thread(new AddThread(0));         Thread t2 = new Thread(new AddThread(1));         t1.start();         t2.start();         //主线程等待两个线程执行完         t1.join();         t2.join();         System.out.println(map.size());     } } 

该程序预测会产生三种结果

  • 1.程序正常运行,得出结果为10万元素
  • 2.结果小于10万,比如94509
  • 3.产生死循环,程序永远无法结束

经过多次实验,没有出现第一种结果,第二种结果和第三种结果可以得到,这时就可以得出一个结论多线程并发操作共享hashmap是线程不安全的,多个线程操作hashmap同一个位置,由于hashmap没有线程可见性,此时后一个线程会将前一个线程添加的元素覆盖掉(第二种结果说明),有时会产生死循环(第三种结果)

面试官:JDK1.8HashMap会发生死循环吗?

三、验证死循环结果

我们使用jps和jstC:UsersSJS>jps 30336 Main 21048 HashMapMultiThread C:UsersSJS>jstack 21048

打印出的堆栈Full thread dump Java HotSpot(TM) 64-Bit Server VM (25.60-b23 mixed mode): //重点看这里 "Thread-1" #15 prio=5 os_prio=0 tid=0x000000001d389000 nid=0x1340 runnable [0x000000001ddce000] java.lang.Thread.State: RUNNABLE at java.util.HashMap$TreeNode.balanceInsertion(HashMap.java:2221) at java.util.HashMap$TreeNode.treeify(HashMap.java:1930) at java.util.HashMap$TreeNode.split(HashMap.java:2153) at java.util.HashMap.resize(HashMap.java:713) at java.util.HashMap.putVal(HashMap.java:662) at java.util.HashMap.put(HashMap.java:611) at com.thinkcoder.concurrenterror.HashMapMultiThread$AddThread.run(HashMapMultiThread.java:38) at java.lang.Thread.run(Thread.java:745) "Thread-0" #14 prio=5 os_prio=0 tid=0x000000001d38b000 nid=0x98c4 runnable [0x000000001dcce000] java.lang.Thread.State: RUNNABLE at java.util.HashMap$TreeNode.putTreeVal(HashMap.java:2002) at java.util.HashMap.putVal(HashMap.java:637) at java.util.HashMap.put(HashMap.java:611) at com.thinkcoder.concurrenterror.HashMapMultiThread$AddThread.run(HashMapMultiThread.java:38) at java.lang.Thread.run(Thread.java:745) //主线程在等待,是由于join的效果 "main" #1 prio=5 os_prio=0 tid=0x0000000003644000 nid=0x96c8 in Object.wait() [0x000000000343e000] java.lang.Thread.State: WAITING (on object monitor) at java.lang.Object.wait(Native Method) - waiting on <0x0000000702a2f420> (a java.lang.Thread) at java.lang.Thread.join(Thread.java:1245) - locked <0x0000000702a2f420> (a java.lang.Thread) at java.lang.Thread.join(Thread.java:1319) at com.thinkcoder.concurrenterror.HashMapMultiThread.main(HashMapMultiThread.java:49)

从线程堆栈信息中可以看出,Thread0和Thread1处于运行状态而main(主)线程处于等待状态,就是等着Thread0和Thread1执行完。但是无奈啊,这两个线程都在正常运行但是程序一直结束不了,这就是死循环的现象

我们按照Thread1的线程信息定位到balanceInsertion方法第2221行代码
面试官:JDK1.8HashMap会发生死循环吗?
断点调试该行代码,发现该方法中的for循环不会终止,确实发现了死循环现象
面试官:JDK1.8HashMap会发生死循环吗?
面试官:JDK1.8HashMap会发生死循环吗?

四、为什么会发生死循环呢?

那咱们得研究下balanceInsertion方法,方法名的意思是平衡插入,方法的作用就是,当向已经树化的桶位添加元素时,为了保持红黑树的特性,需要对树进行重新结构化。

分析一下balanceInsertion方法源代码

 static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,                                              TreeNode<K,V> x) {      //新插入的节点标为红色      x.red = true;            //无限for循环,定义xp、xpp、xppl、xppr变量,在循环体进行赋值,p就是parents      //- root:当前根节点      //- x   :新插入的节点      //- xp  :新插入节点的父节点      //- xpp :新插入节点的祖父节点      //- xppl:新插入节点的左叔叔节点      //- xppr:新插入节点的右叔叔节点      for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {      	       	 //为定义的各个变量赋值的过程          if ((xp = x.parent) == null) {              x.red = false;              return x;          }          else if (!xp.red || (xpp = xp.parent) == null)              return root;          //重点看这里          //如果父节点是爷爷节点的左孩子          if (xp == (xppl = xpp.left)) {          	 //如果右叔叔不为空且为红色              if ((xppr = xpp.right) != null && xppr.red) {              	 //右叔叔变为黑色                  xppr.red = false;                  //父节点变为黑色                  xp.red = false;                  //爷爷节点变为黑色                  xpp.red = true;                  //将爷爷节点当作起始节点,再次循环,请注意再次循环!!!                  x = xpp;              } 		//省略其他代码  } 

总结一下上边的源码就是,新插入一个节点,该方法要保持红黑树的五个性质

性质1. 节点是红色或黑色。

性质2. 根节点是黑色。

性质3 每个叶节点(NIL节点,空节点)是黑色的。

性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点到其每个叶子的路径上包含的黑色节点数量都相同。

解释下上面的例子为什么会产生死循环,我们把上面的图片复制下来
面试官:JDK1.8HashMap会发生死循环吗?
发现一个问题,根节点、爷爷节点、父节点、左叔叔节点、右叔叔节点、新插入的节点都是一个元素667700,证明当前循环的树只有一个值,并且永远不会退出,因为它满足下面两个判断条件

//如果父节点是爷爷节点的左孩子 if (xp == (xppl = xpp.left)) {  	 //如果右叔叔不为空且为红色      if ((xppr = xpp.right) != null && xppr.red) 

--------------------------------------------------------------------------分割线-------------------------------------------------------------------------------------

经过这波分析后,你学废了吗?,祝愿大家在学习的路上,不变秃只变强
面试官:JDK1.8HashMap会发生死循环吗?

版权声明:玥玥 发表于 2021-06-02 22:23:19。
转载请注明:面试官:JDK1.8HashMap会发生死循环吗? | 女黑客导航