关于后端:面试突击17HashMap除了死循环还有什么问题

面试合集：https://gitee.com/mydb/interview

本篇的这个问题是一个开放性问题，HashMap 除了死循环之外，还有其余什么问题？总体来说 HashMap 的所有“问题”，都是因为应用（HashMap）不当才导致的，这些问题大抵能够分为两类：

1. 程序问题：比方 HashMap 在 JDK 1.7 中，并发插入时可能会产生死循环或数据笼罩的问题。
2. 业务问题：比方 HashMap 无序性造成查问后果和预期后果不相符的问题。

接下来咱们一个一个来看。

1. 死循环问题

死循环问题产生在 JDK 1.7 版本中，造成的起因是 JDK 1.7 HashMap 应用的是头插法，那么在并发扩容时可能就会导致死循环的问题，具体产生的过程如下流程所示。
HashMap 失常状况下的扩容实现如下图所示：

旧 HashMap 的节点会顺次转移到新 HashMap 中，旧 HashMap 转移的程序是 A、B、C，而新 HashMap 应用的是头插法，所以最终在新 HashMap 中的程序是 C、B、A，也就是上图展现的那样。有了这些前置常识之后，咱们来看死循环是如何诞生的？

1.1 死循环执行流程一

死循环是因为并发 HashMap 扩容导致的，并发扩容的第一步，线程 T1 和线程 T2 要对 HashMap 进行扩容操作，此时 T1 和 T2 指向的是链表的头结点元素 A，而 T1 和 T2 的下一个节点，也就是 T1.next 和 T2.next 指向的是 B 节点，如下图所示：

1.2 死循环执行流程二

死循环的第二步操作是，线程 T2 工夫片用完进入休眠状态，而线程 T1 开始执行扩容操作，始终到线程 T1 扩容实现后，线程 T2 才被唤醒，扩容之后的场景如下图所示：

从上图可知线程 T1 执行之后，因为是头插法，所以 HashMap 的程序曾经产生了扭转，但线程 T2 对于产生的所有是不可知的，所以它的指向元素仍然没变，如上图展现的那样，T2 指向的是 A 元素，T2.next 指向的节点是 B 元素。

1.3 死循环执行流程三

当线程 T1 执行完，而线程 T2 复原执行时，死循环就建设了，如下图所示：

因为 T1 执行完扩容之后 B 节点的下一个节点是 A，而 T2 线程指向的首节点是 A，第二个节点是 B，这个程序刚好和 T1 扩完容完之后的节点程序是相同的。T1 执行完之后的程序是 B 到 A，而 T2 的程序是 A 到 B，这样 A 节点和 B 节点就造成死循环了，这就是 HashMap 死循环导致的起因。

1.4 解决方案

应用线程平安的容器来代替 HashMap，比方 ConcurrentHashMap 或 Hashtable，因为 ConcurrentHashMap 的性能远高于 Hashtable，因而举荐应用 ConcurrentHashMap 来代替 HashMap。

2. 数据笼罩问题

数据笼罩问题产生在并发增加元素的场景下，它不止呈现在 JDK 1.7 版本中，其余版本中也存在此问题，数据笼罩产生的流程如下：

1. 线程 T1 进行增加时，判断某个地位能够插入元素，但还没有真正的进行插入操作，本人工夫片就用完了。
2. 线程 T2 也执行增加操作，并且 T2 产生的哈希值和 T1 雷同，也就是 T2 行将要存储的地位和 T1 雷同，因为此地位尚未插入值（T1 线程执行了一半），于是 T2 就把本人的值存入到以后地位了。
3. T1 复原执行之后，因为非空判断曾经执行完了，它感知不到此地位曾经有值了，于是就把本人的值也插入到了此地位，那么 T2 的值就被笼罩了。

具体执行流程如下图所示。

2.1 数据笼罩执行流程一

线程 T1 筹备将数据 k1:v1 插入到 Null 处，但还没有真正的执行，本人的工夫片就用完了，进入休眠状态了，如下图所示：

2.2 数据笼罩执行流程二

线程 T2 筹备将数据 k2:v2 插入到 Null 处，因为此处当初并未有值，如果此处有值的话，它会应用链式法将数据插入到下一个没值的地位上，但判断之后发现此处并未有值，那么就间接进行数据插入了，如下图所示：

2.3 数据笼罩执行流程三

线程 T2 执行实现之后，线程 T1 复原执行，因为线程 T1 之前曾经判断过此地位没值了，所以会直接插入，此时线程 T2 插入的值就被笼罩了，如下图所示：

2.4 解决方案

解决方案和第一个解决方案雷同，应用 ConcurrentHashMap 来代替 HashMap 就能够解决此问题了。

3. 无序性问题

这里的 无序性问题指的是 HashMap 增加和查问的程序不统一，导致程序执行的后果和程序员预期的后果不相符，如以下代码所示：

HashMap<String, String> map = new HashMap<>();
// 增加元素
for (int i = 1; i <= 5; i++) {map.put("2022-10-" + i, "Hello，Java：" + i);
}
// 查问元素
map.forEach((k, v) -> {System.out.println(k + "：" + v);
});

咱们增加的程序：

咱们冀望查问的程序和增加的程序是统一的，然而以上代码输入的后果却是：

执行后果和咱们预期后果不相符，这就是 HashMap 的无序性问题。咱们冀望输入的后果是 Hello，Java 1、2、3、4、5，而失去的程序却是 2、1、4、3、5。

解决方案

想要解决 HashMap 无序问题，咱们只须要将 HashMap 替换成 LinkedHashMap 就能够了，如下代码所示：

LinkedHashMap<String, String> map = new LinkedHashMap<>();
// 增加元素
for (int i = 1; i <= 5; i++) {map.put("2022-10-" + i, "Hello，Java：" + i);
}
// 查问元素
map.forEach((k, v) -> {System.out.println(k + "：" + v);
});

以上程序的执行后果如下图所示：

总结

本文演示了 3 个 HashMap 的经典问题，其中死循环和数据笼罩是产生在并发增加元素时，而无序问题是增加元素的程序和查问的程序不统一的问题，这些问题实质来说都是对 HashMap 使用不当才会造成的问题，比方在多线程状况下就应该应用 ConcurrentHashMap，想要保障插入程序和查问程序统一就应该应用 LinkedHashMap，但刚开始时咱们对 HashMap 不相熟，所以才会造成这些问题，不过理解了它们之后，就能更好的应用它和更好的应答面试了。
​

是非审之于己，毁誉听之于人，得失安之于数。

公众号：Java 面试真题解析