HashMap的死循环(HashMapinfiniteloop)

作者：白云下6_136 | 来源：互联网 | 2023-05-17 12:36

仅为学习交流，如果有错，请指正，谢谢HashMap是一个线程不安全的key-value的存储集合，也意味着它在多线程的环境中也存在很大的风险。HashM

仅为学习交流，如果有错，请指正，谢谢
HashMap是一个线程不安全的key-value的存储集合，也意味着它在多线程的环境中也存在很大的风险。
HashMap的存储结构：

通常来讲，HashMap是由一个数组和一个链表组成，在初始化的时候，HashMap会初始化一个数组table[],在不指定容量的情况下默认为16，负载系数为0.75，HashMap在put的时候会通过key的hash值来计算这个数组的下标，然后就把这个存储集合存储在该下标的数组中，在查找时的复杂度为O(1),然而在Hash算法中，很有可能存在不同的key算出相同的值，HashMap就会把相同的值用链表来表示，这个时候就要遍历链表了，查找复杂度为O(n). 正是由于链表的存在，在多线程的环境下，共享链表，这就会变得不安全了。什么时候链表会变得不安全呢？HashMap的容量是动态的，随着容量的增加而增量，在每次put的时候都会检查当前的容量是否满足，假设上述图片的容量为4，如果当前的容量大于4*0.75(负载因子)，就会创建一个4*2的容量的新数组，将老的数组Copy到新的数组，然后所有的值就会重新hash，也就是rehash。现在我们模拟两个线程下的rehash情况，我们有两个线程：Thread1，Thread2，我们先看看HashMap中的rehash方法transfer(). 1:  // tranfer()片段
2:  // 这是在resize()中调用的方法,resize()就是HashMap扩容的方法
3:
4:  for (int j = 0; j
5:    Entry e = src[j];
6:    if (e != null) {
7:      src[j] = null;
8:      do {
9:      Entry next = e.next;  //假设线程1停留在这里就挂起了,线程2登场
10:     int i = indexFor(e.hash, newCapacity);
11:     e.next = newTable[i];
12:     newTable[i] = e;
13:     e = next;
14:   } while (e != null);
15:   }
16: }

此时运行完Thread1：

此时Entry e是e1，Entry next = e.next中的next是next1,红色是还没有完成，指针指向步骤还没有开始。现在Thread2登场了，Thread2运行完结构如下：

发现与Thread1的情况刚好反过来了，此时Entry e是e2，Entry next = e.next中的next是next2，是的，Thread2已经完成了指针指向操作了 Entry next = e.next;
10:     int i = indexFor(e.hash, newCapacity);
11:     e.next = newTable[i];
12:     newTable[i] = e;
13:     e = next;//假设Thread2已经走了这里
这个时候Thread1要登场了，从Entry next = e.next;开始继续运行下去,此时在Thread2的影响下Thread1运行的结构已经变了

此时由于Thread2的影响，(key:2 ,value:b)已经指向了(key:1,value:a),而红线是Thread1接下来的操作,完成指针指向操作，当Thread1完成时结构如下

这个时候你就会发现圆圈内形成了一个闭环，infinite loop就形成了！！！！
参考： http://pettyandydog.com

推荐阅读

php
Android中高级面试必知必会，积累总结

本文介绍了Android中高级面试的必知必会内容，并总结了相关经验。文章指出，如今的Android市场对开发人员的要求更高，需要更专业的人才。同时，文章还给出了针对Android岗位的职责和要求，并提供了简历突出的建议。 ... [详细]

蜡笔小新 2023-12-14 14:53:02
list
JDK源码学习之HashTable(附带面试题)的学习笔记

本文介绍了JDK源码学习之HashTable(附带面试题)的学习笔记，包括HashTable的定义、数据类型、与HashMap的关系和区别。文章提供了干货，并附带了其他相关主题的学习笔记。 ... [详细]

蜡笔小新 2023-12-12 13:05:17
list
GreenDAO快速入门

前言之前在自己做项目的时候，用到了GreenDAO数据库，其实对于数据库辅助工具库从OrmLite，到litePal再到GreenDAO，总是在不停的切换，但是没有真正去了解他们的 ... [详细]

蜡笔小新 2023-12-11 12:31:00
rsa
【机器学习】生成式对抗网络模型综述

生成式对抗网络模型综述摘要生成式对抗网络模型(GAN)是基于深度学习的一种强大的生成模型，可以应用于计算机视觉、自然语言处理、半监督学习等重要领域。生成式对抗网络 ... [详细]

蜡笔小新 2023-12-14 17:51:18
list
CSS3选择器的使用方法详解，提高Web开发效率和精准度

本文详细介绍了CSS3新增的选择器方法，包括属性选择器的使用。通过CSS3选择器，可以提高Web开发的效率和精准度，使得查找元素更加方便和快捷。同时，本文还对属性选择器的各种用法进行了详细解释，并给出了相应的代码示例。通过学习本文，读者可以更好地掌握CSS3选择器的使用方法，提升自己的Web开发能力。 ... [详细]

蜡笔小新 2023-12-14 14:37:52
blob
sklearn数据集库中的常用数据集类型介绍

本文介绍了sklearn数据集库中常用的数据集类型，包括玩具数据集和样本生成器。其中详细介绍了波士顿房价数据集，包含了波士顿506处房屋的13种不同特征以及房屋价格，适用于回归任务。 ... [详细]

蜡笔小新 2023-12-13 17:45:15
main
[大整数乘法] java代码实现

本文介绍了使用java代码实现大整数乘法的过程，同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率，并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]

蜡笔小新 2023-12-13 11:21:32
main
引擎之旅 Chapter.2 线程库

预备知识可参考我整理的博客Windows编程之线程:https:www.cnblogs.comZhuSenlinp16662075.htmlWindows编程之线程同步:https ... [详细]

蜡笔小新 2023-12-12 14:06:39
main
to_a和to_ary有什么区别？ - What's the difference between to_a and to_ary?

Whatsthedifferencebetweento_aandto_ary?to_a和to_ary有什么区别？ ... [详细]

蜡笔小新 2023-12-11 19:30:04
main
Java高并发程序设计学习-线程安全的概念与synchronized

本文介绍了Java高并发程序设计中线程安全的概念与synchronized关键字的使用。通过一个计数器的例子，演示了多线程同时对变量进行累加操作时可能出现的问题。最终值会小于预期的原因是因为两个线程同时对变量进行写入时，其中一个线程的结果会覆盖另一个线程的结果。为了解决这个问题，可以使用synchronized关键字来保证线程安全。 ... [详细]

蜡笔小新 2023-12-13 15:43:03
php
南邮ctf-web的writeup

本文介绍了南邮ctf-web的writeup，包括签到题和md5 collision。在CTF比赛和渗透测试中，可以通过查看源代码、代码注释、页面隐藏元素、超链接和HTTP响应头部来寻找flag或提示信息。利用PHP弱类型，可以发现md5('QNKCDZO')='0e830400451993494058024219903391'和md5('240610708')='0e462097431906509019562988736854'。 ... [详细]

蜡笔小新 2023-12-13 10:58:55
main
Java学习笔记之面向对象编程（OOP）

本文介绍了Java学习笔记中的面向对象编程（OOP）内容，包括OOP的三大特性（封装、继承、多态）和五大原则（单一职责原则、开放封闭原则、里式替换原则、依赖倒置原则）。通过学习OOP，可以提高代码复用性、拓展性和安全性。 ... [详细]

蜡笔小新 2023-12-13 08:44:30
list
基于Socket的多个客户端之间的聊天功能实现方法

本文介绍了基于Socket的多个客户端之间实现聊天功能的方法，包括服务器端的实现和客户端的实现。服务器端通过每个用户的输出流向特定用户发送消息，而客户端通过输入流接收消息。同时，还介绍了相关的实体类和Socket的基本概念。 ... [详细]

蜡笔小新 2023-12-11 15:55:40
main
操作系统的定义和功能

本文介绍了操作系统的定义和功能，包括操作系统的本质、用户界面以及系统调用的分类。同时还介绍了进程和线程的区别，包括进程和线程的定义和作用。 ... [详细]

蜡笔小新 2023-12-11 14:17:13
php
javascript和java的关系,JavaScript和java的关系

Java和JavaScript是什么关系？java跟javaScript都是编程语言，只是java跟javaScript没有什么太大关系，一个是脚本语言（前端语言），一个是面向对象 ... [详细]

蜡笔小新 2023-12-11 04:03:31

白云下6_136

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章