0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395  HashMap 为什么会导致 CPU 100%?文章看不懂?来看这个视频吧!——面试突击 006 期
英语文化交流 > 技术博客 > HashMap 为什么会导致 CPU 100%?文章看不懂?来看这个视频吧!——面试突击 006 期
HashMap 为什么会导致 CPU 100%?文章看不懂?来看这个视频吧!——面试突击 006 期
时间: 分类:技术博客

哈喽,大家好,我是老王,欢迎来到 Java 面试突击,我们今天来开始第 6 期的内容。
本期的问题是:HashMap 为什会导致 CPU 运行 100%?这是一个比较常见的经典问题了,但是有很多人读者朋友给我反馈,尼玛,看文章根本看不懂啊?Sun 公司都不知道这个问题的原因吧?不,是 Oracle 公司都不知道这个问题的原因吧?面试官怕也不知道这个的答案吧?
咳咳,作为一个很正经的面试官,我觉得这个问题一点都不重要,重要的是你不知道答案啊。好的,下一位面试者请进,您先回去等通知吧。
为了避免这种尴尬的事情发生,今天我们来好好聊一下这个问题,毕竟技能再手,才能吊打面试官不是?
正文

这个问题相关的知识点,有以下几个:
H```
ashMap 的底层数据结构是什么?
什么是哈希碰撞?如何该解决这个问题?
什么是扩展因子?它有什么用?
还有对 HashMap 源码的理解,为什么 HashMap 会导致死循环?

视频版答案

视频内容如下:

图文答案

1.HashMap 的底层数据结构

先来说 HashMap 的底层数据结构,看过 HashMap 的源码我们就会发现,JDK 1.7 和 JDK 1.8 HashMap 的组成是不同的,JDK 1.7 HashMap 的组成是数组 + 链表的形式,而 JDK 1.8 新增了红黑树的数据结构,当 HashMap 中的链表长度大于 8 时,链表结构就会转换为红黑树,如下图所示:
![](https://s4.51cto.com/images/blog/202007/31/4e006f8b3e8d00bc4d156443365473de.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=)

2.哈希碰撞及解决方案

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

扩展因子也叫加载因子或负载因子是 HashMap 中的一个属性,如下图所示:假如数组的默认长度为 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) 的环形引用,就导致了死循环的产生,如下图所示:

![](https://s4.51cto.com/images/blog/202007/31/cce05aec85fda2d0a701473f3654477e.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=)

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

HashMap 是非线程安全的,以 JDK 1.7 为例,当多线程并发扩容时就会出现环形引用的问题,从而导致死循环的出现,一直死循环就会导致 CPU 运行 100%,所以在多线程使用时,我们需要使用 ConcurrentHashMap 来替代 HashMap,但只有懂得其中的因果关系才能吊打面试官,好了,本节内容到这里就结束了,我们下期再见。

上期中奖名单:皮卡皮卡、一步、好好学习、谈笑、包子有话要讲。
以上中奖的朋友,请加我的微信:GG_Stone 领取奖励。
【END】
近期热文

* 面试突击 005 | Redis 是如何实现高可用的?它的实现方式有哪些?
* 面试突击 004 | 如何排查 Redis 中的慢查询?视频实战篇
* 面试突击 003 | Redis 如何实现查询附近的人?
* 面试突击 002 | Redis 是如何处理已过期元素的?
* 面试突击 001 | Redis 如何从海量数据中查询出某一个 Key?
* Java面试详解(2020版):500+ 面试题和核心知识点详解
关注下方二维码,订阅更多精彩内容
![](https://s4.51cto.com/images/blog/202007/31/dba489b49a779bc90fe04f2d66b60f44.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=)
随机阅读

Copyright © 2017 英语文化交流 All Rights Reserved.