多线程环境下HashMap导致CPU100%

╰半夏微凉° 2023-02-24 08:48 32阅读 0赞

引言

昨天早上线上系统开始作业了一段时间以后，突然收到服务器报警，服务器CPU持续占用100%，导致线上系统不能正常使用，我登录服务器top了一下，发现java进程占用cpu400%, 由于前天晚上上线了一些新的功能，所以我分析应该是某处代码出现了死循环导致，于是根据前面解决性能问题的经验来搞一下。具体流程参考我前面的博文《[快速定位线上CPU100%问题][CPU100]》。

排查结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNDU0Mzc_size_16_color_FFFFFF_t_70][]

快速找到具体的代码，那么问题就可以很好的解决了，看一下具体代码

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNDU0Mzc_size_16_color_FFFFFF_t_70 1][]

public static Map<String, List<String>> mobileAnsweredLineNameMap = new HashedMap();

当看到这的时候有经验的读者可能一眼知道问题了，我看到这个代码的第一反应，这个地方怎么使用了 一个这么单纯的HashMap，这在多线程环境下必死啊。至少我们要是用ConcurrentHashMap，或者 Collections.synchronizedMap(new HashedMap());不能在这裸奔啊。

# **下面我们分析一下HashMap为什么导致CPU100%** #

这个问题相关的知识点，有以下几个：

1.  HashMap 的底层数据结构是什么？
2.  什么是哈希碰撞？如何该解决这个问题？
3.  什么是扩展因子？它有什么用？
4.  还有对 HashMap 源码的理解，为什么 HashMap 会导致死循环？

### 1.HashMap 的底层数据结构 ###

先来说 HashMap 的底层数据结构，看过 HashMap 的源码我们就会发现，JDK 1.7 和 JDK 1.8 HashMap 的组成是不同的，JDK 1.7 HashMap 的组成是数组 + 链表的形式，而 JDK 1.8 新增了红黑树的数据结构，当 HashMap 中的链表长度大于 8 时，链表结构就会转换为红黑树，如下图所示：

![format_png][]

### 2.哈希碰撞及解决方案 ###

所谓的**哈希碰撞指的是不同的值，经过哈希之后得到的值确是相同的，这种情况就叫做哈希碰撞或哈希冲突**。解决哈希碰撞的常用方法是：**开放定址法和链表地址法**，而 **HashMap 采用的就是链表地址法**。它的**实现原理就是将 HashMap 中相同的哈希值以链表的形式存储起来**。

### 3.扩展因子 ###

扩展因子也叫加载因子或负载因子是 HashMap 中的一个属性，如下图所示：![format_png 1][]假如数组的默认长度为 10，扩展因子为 0.5，那么当数组超过 10\*0.5=5 个时，HashMap 就会扩容为之前容量的两倍，所以说扩展因子就是用来判定 HashMap 是否满足扩容条件的。

### 4.HashMap死循环分析 ###

HashMap 导致 CPU 100% 的原因就是因为 HashMap 死循环导致的，那 HashMap 是如何造成死循环的？接下来我们一起来看。

以 JDK 1.7 为例，假设 HashMap 的默认大小为 2，HashMap 本身中有一个键值 key(5)，我们再使用两个线程：t1 添加 key(3)，t2 添加 key(7)，首先两个线程先把 key(3) 和 key(7) 都添加到 HashMap 中，此时因为 HashMap 的长度不够用了就会进行扩容操作，然后这时线程 t1 在执行到 Entry<K,V> next = e.next; 时，交出了 CPU 的使用权，源代码如下：

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next; // 线程一执行此处
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

那么此时线程 t1 中的 e 指向了 key(3)，而 next 指向了 key(7) ；之后线程 t2 重新 rehash 之后链表的顺序被反转，链表的位置变成了 key(5) -> key(7) -> key(3)，其中 “->” 用来表示下一个元素，当 t1 重新获得执行权之后，先执行 newTalbe\[i\] = e 把 key(3) 的 next 设置为 key(7)，而下次循环时查询到 key(7) 的 e.next 为 key(3)，于是就形 成了 key(3) 和 key(7) 的环形引用，就导致了死循环的产生，如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNDU0Mzc_size_16_color_FFFFFF_t_70 2][]

HashMap 发生死循环的一个重要原因是 JDK 1.7 时链表的插入是首部倒序插入的，而 JDK 1.8 时已经变成了尾部插入，有人把这个死循环的问题反馈给了 Sun 公司，但它们认为这不是一个问题，因为 HashMap 本身就是非线程安全的，如果要在多线程使用建议使用 ConcurrentHashMap 替代 HashMap，但面试中这个问题被问的频率比较高，所以在这里就特殊说明一下。

## 小结 ##

HashMap 是非线程安全的，以 JDK 1.7 为例，当多线程并发扩容时就会出现环形引用的问题，从而导致死循环的出现，一直死循环就会导致 CPU 运行 100%，所以在多线程使用时，我们需要使用 ConcurrentHashMap 来替代 HashMap。

[CPU100]: https://blog.csdn.net/hao134838/article/details/103261116?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522159425731019724845061586%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=159425731019724845061586&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_v1~rank_blog_v1-1-103261116.pc_v1_rank_blog_v1&utm_term=cpu
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNDU0Mzc_size_16_color_FFFFFF_t_70]: /images/20230209/13318637f99f489da674926a0be68b5a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNDU0Mzc_size_16_color_FFFFFF_t_70 1]: /images/20230209/a8681f16d03844a1a70f32f6fabb156c.png
[format_png]: /images/20230209/6a776ec646724857bc95e7bed03021d8.png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9Icld3Nlp1WENzaHNTN0JpY1ZQREhNWUloNG1FSXNpY3VlOW5DSlRHSUsybTZFeURHSW1sc3ZWTXRuWmljbDdmZ1RGZWxERlRtb1FVakRRRUYxbms3ZmRxdy82NDA?x-oss-process=image/format,png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNDU0Mzc_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200709092927799.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNDU0Mzc=,size_16,color_FFFFFF,t_70