Hashmap非线程安全关于hash值冲突处理
作者:zziawan 发布时间:2023-11-11 09:22:10
前言
总是觉得对HashMap很熟悉,但最近连续被问到几个关于它的问题,才发现它其实并不简单。这里对关于它的一些问题做个总结,也希望能够大家一个参考。
hash值冲突该怎么处理
都知道它是基于hash值,可以进行常量时间消化的存储结构。广泛用于各种情况下的高效key-value存储。这里有几个问题。首先,如果出现hash值冲突该怎么处理?相信很多人都不用思考就能说出,通过链表来解决冲突。就是将hash值相同值存储到一个挂载在该位置的链表里面去。但是这就又引出了新的问题,给一个key,它的hash值有冲突的情况下,它是如何在链表上取到你所期望的value的?这个就要去看hashmap的存储结构了。每一个key-value会被封装到一个entity中,map中存储的其实是这个entity。这样既存储了value,又存储了key。所有在链表上取值只需要比较key是否equal。这里又出现了一个问题,为什么建议重写key的equal和hash方法。重写hash方法能够保证不同对象用于不同的hash值,从而减少冲突,重写equal则可以在出现冲突的情况下,保证不出现错误覆盖的情况。
hashmap的put方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)//没有初始化,则要初始化,初始化调用的也是resize()方法
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);//这个位置没有值,直接插入,重写hash方法的作用体现在这里
else {//出现了冲突
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))//找到了如该key equal的value
e = p;
else if (p instanceof TreeNode)//事树节点,插入到树里。jdk8冲突节点数目达到一定值后,使用树结构存储
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {//一直找到链表的结尾,将k-v插入
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);//是否需要改成树存储
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
上面的代码充分表明了key重写equal的作用。HashMap以key的value来获取值,所以一定要确保同一个key的hashcode在任何时候都不能改变。这也是为什么建议key是不可变对象,如string对象。如果key是对象,运行过程中key的hashcode因为内部值的改变而发生了改变,那么map中的value将永远丢失。
非线程安全体现
以上是关于kv的讨论,接下来是关于HashMap的另外的一个常见话题——线程安全问题。多数人都知道它是非线程安全的。但是如果问你它非线程安全体现在哪里,恐怕会难住一批人。
首先容易想到的是多线程插入时出现了冲突的情况,多个线程同时插入,但是这其中有些值又出现了冲突。插入时大家都看到这个位置没有值,于是都进行插入,这样肯定会出现值覆盖,对外的表现就是值丢失。如果开始插入时,这个位置已经有了值,那么在插入链表过程中还是会出现值覆盖。
另外就是同时扩容问题。因为HashMap会在空间不足时自动扩容,大小变成之前的两倍。同时复制之前的值到新的数组中。冲突链也会进行复制。如果多个线程插入后同时看到容量需要调整,就都会调用resize方法。那么底层到达会出现什么问题就难以预测了。
所以这也是HashMap非线程安全的第二点体现。当然同时读写一个值也可能会存在数据跟期望不一致的情况。这也是非线程安全的表现。
来源:https://www.cnblogs.com/zziawanblog/p/7231784.html
猜你喜欢
- Java 判断字符串中是否包含中文的实例详解 Java判断一个字符串是否有中文是利用Unicode编码来判断,因为中
- 本文实例为大家分享了java实现鲜花销售系统的具体代码,供大家参考,具体内容如下一、练习目标1.体会数组的作用2.找到分层开发的感觉3.收获
- java 读取本地文件实例详解用javax.xml、w3c解析实例代码:package cn.com.xinli.monitor.utils
- java遍历json字符串,取得相应KV值时,各种麻烦,比如将json中的list取出来转为JSONArray,再将list中的object
- 简介AccessibilityService的设计初衷是为了辅助有身体缺陷的群体使用Android应用,它的设计贯穿着Android的控件树
- 这篇文章需要对git具有一定的了解,并且知道如何安装git工具(其实就是上git官网下载个文件,安装)git这种版本控制工具有什么好处第一个
- 如图所示的效果相信大家都不陌生,我们可以使用很多种方法去实现此效果,这里自己采用CountDownTimer定时器简单封装下此效果,方便我们
- 在基于UI元素的自动化测试中, 无论是桌面的UI自动化测试,还是Web的UI自动化测试. 首先我们需要查找和识别UI
- 效果展示人脸支付效果视频密码框输入支付效果视频因为密码支付时会调起系统安全键盘,开启自动保护功能,防止泄露,会导致输入密码时录屏黑屏,故使用
- Java中List.of()和Arrays.asList()的区别及原因动手写一下,让自己更有印象1.Arrays.asList()可以插入
- 1.前言在Mybatis中需要创建的配置文件有sqlMapconfig.xml,映射文件xxxMapper.xml,而这些文件在idea中并
- 本文实例为大家分享了Android实现双曲线折线图的具体代码,供大家参考,具体内容如下先看一下效果图1.先下载jar包 mpandroidc
- 1、通过查找API文档:2、Map.Entry是一个接口,所以不能直接实例化。3、Map.entrySet( )返回的是一个collecti
- 在上一篇文章《驱动开发:内核字符串转换方法》中简单介绍了内核是如何使用字符串以及字符串之间的转换方法,本章将继续探索字符串的拷贝与比较,与应
- 在学会了java中io流的使用后,我们对于数组的排序,又多了一种使用方法。大家知道流处理数据的效率是比较理想的,那么在具体操作数组排序上,很
- 我们都知道mybatis在进行参数判断的时候,直接可以用<if test=""></if> 就可
- 本文向您展示了在 Flutter 中实现完美的验证码输入框几种不同方法。重点是什么?真实世界的 完美的验证码输入框或 PIN 输入 UI 通
- 注意是maven的webapp:选择maven下一步下一步。maven下载过慢在setting中加入镜像。 我也有疑问这是什么鬼格式,但是证
- 对某个类型中的方法进行拦截,然后加入固定的业务逻辑,这是AOP面向切面编程可以做的事,在springboot里实现aop的方法也有很多, s
- 引言备忘录模式经常可以遇到,譬如下面这些场景:浏览器回退:浏览器一般有浏览记录,当我们在一个网页上点击几次链接之后,可在左上角点击左箭头回退