首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >HashMap的数据结构浅析[通俗易懂]

HashMap的数据结构浅析[通俗易懂]

作者头像
全栈程序员站长
发布于 2022-08-30 12:40:58
发布于 2022-08-30 12:40:58
49300
代码可运行
举报
运行总次数:0
代码可运行

大家好,又见面了,我是你们的朋友全栈君。

HashMap是非线程安全的。而HashMap的线程不安全主要体现在resize时的死循环

HashMap工作原理

  • HashMap数据结构 常用的底层数据结构主要有数组和链表。数组存储区间连续,占用内存较多,寻址容易,插入和删除困难。链表存储区间离散,占用内存较少,寻址困难,插入和删除容易。
  • HashMap要实现的是哈希表的效果,尽量实现O(1)级别的增删改查。它的具体实现则是同时使用了数组和链表,可以认为最外层是一个数组,数组的每个元素是一个链表的表头。

HashMap的寻址方式

  • 对于新插入的数据或者待读取的数据,HashMap将Key的哈希值对数组长度取模,结果作为该Entry在数组中的index。因此数组的长度必须时2的N次方,实际中,HashMap会自动通过Integer.highestOneBit算出比指定整数大的最小的N值。
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
        public static int highestOneBit(int i) {
          i |= (i >>  1);
          i |= (i >>  2);
          i |= (i >>  4);
          i |= (i >>  8);
          i |= (i >> 16);
          return i - (i >>> 1);
        }
  • 碰撞:由于数组的长度是有限的,所以不管Hash()方法和Equals()方法写得如何严谨,始终不能完全避免碰撞的发生(Hash值算出来的Index相同,需要放在数组的同一个位置),碰撞发生后,我们就只能添加一个链表子节点,但是这无疑会降低查找效率(找到Index还要遍历链表。。。)
  • 加载因子:默认是0.75,当数组的被占空间>=0.75的时候,HashMap就会进行扩容(变为两倍),扩容之后数组中的所有元素进行重排序(算出来的Index可能不同),从而减少数组下链表的长度,提高查找效率。

Java8 中的升级

  • Java8 中的HashMap采用了数组+链表+红黑树(类似于数据结构中的平衡二叉树)的模式(当链表长度<8时仍然采用链表的形式,>8时由链表的数据结构转换成红黑树的数据结构)

JDK1.7中线程不安全的HashMap

  • 上文讲到占用空间超过加载因子的值时,就会自动扩容,这时HashMap中的元素或重新计算排序,这显然是不能保证线程安全的,而且在多线程并发调用时,可能出现死循环。
  • 首先:先给出resize的核心代码:
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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;  
            } 
        }  
    }  
  • 在多线程调用中,可能会产生这种情况:两个线程同时认为HashMap需要rehash,这里就有一种可能性,这两个线程在调用的时候
  • 当两个线程痛时执行的时候,可能有一个会被挂起,等待另一个结束后在继续执行,这时问题就产生了;
  • 产生死循环的原因是:while(null != e)这句判断,在第一次执行的时候,B原本->null,于是重新计算到B的时候B->null,判断体就结束执行,于是就扩容成功
  • 当第二个线程执行扩容的时候,内存中是B->A ,是的,条件成立,而原本的条件(线程2以为的条件)是A->B 这里,两个条件同时成立,后果就是。。。一直循环下去A->B->A->B…
    • 具体过程是A->B,执行while,将A头插到数组,指针指向下一个,B->A,条件成立,将B头插如数组,指针指向下一个,A->B…
JDK1.8的优化
  • 在JDK1.8中采用了尾插法,可以有效避免上述这种死循环的情况。

以上就是我目前的理解,还有一种使用迭代器时的fast-fail,以后有机会更新。 关于ConcurrentHashMap可以看看我的另外一篇,欢迎指正:ConcurrentHashMap浅析

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/144696.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022年5月1,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
京东一面:为什么 HashMap 是线程不安全的?
这是《Java 程序员进阶之路》专栏的第 58 篇,我们来聊聊为什么 HashMap 是线程不安全的。
沉默王二
2021/12/23
3400
京东一面:为什么 HashMap 是线程不安全的?
HashMap数据结构及其一些方法
数组存储区间是连续的,占用内存严重,故空间复杂的很大。但数组的二分查找时间复杂度小,为O(1);数组的特点是:寻址容易,插入和删除困难;
全栈程序员站长
2022/08/31
2480
Java面试题:HashMap为什么线程不安全、ConcurrentHashMap原理、ConcurrentHashMap与HashMap区别、Map总结
还记得 HashMap的实现原理、jdk1.7与jdk1.8的HashMap有什么区别吗?如果忘记可以到这里重新温习:Java面试题:ArrayList底层实现原理、HashMap的实现原理、HashMap的jdk1.7和jdk1.8有什么区别
寻求出路的程序媛
2024/06/12
3750
Java面试题:HashMap为什么线程不安全、ConcurrentHashMap原理、ConcurrentHashMap与HashMap区别、Map总结
Hashmap源码阅读
HashMap是什么想必大家都是知道的,日常开发中经常使用,而且常驻于笔试题目及面试中,那么今天将从源码的角度来深入理解一下HashMap。
呼延十
2019/06/26
3530
Hashmap源码阅读
漫画:高并发下的HashMap
HashMap的容量是有限的。当经过多次元素插入,使得HashMap达到一定饱和度时,Key映射位置发生冲突的几率会逐渐提高。
小灰
2022/07/05
1860
漫画:高并发下的HashMap
去哪面试都会问的HashMap
HashMap可以说是面试的重中之重,去10家公司面试,8家都会问道,为什么大家都爱用HashMap打开话题?
Java识堂
2020/03/17
5070
去哪面试都会问的HashMap
关于HashMap在高并发下的问题
总所周知,HashMap不是线程安全的,在高并发情况下会出现问题。特别是,在java1.7中,多线程的HashMap会出现CPU 100%的严重问题。这个问题是怎样产生的,后续版本还会有这个问题吗(指java8及后续版本)?下面就来用通俗的语言讲解下。
用户3467126
2019/08/06
8480
Java数据结构-------Map
    1)无序; 2)访问速度快; 3)key不允许重复(只允许存在一个null Key);
在周末
2019/09/11
1.5K0
详解并发下的HashMap以及JDK8的优化
HashMap使用链表法避免哈希冲突(相同hash值),当链表长度大于TREEIFY_THRESHOLD(默认为8)时,将链表转换为红黑树。当小于等于UNTREEIFY_THRESHOLD(默认为6)时,又会退化回链表以达到性能均衡。 下图为HashMap的数据结构(数组+链表+红黑树 )
全菜工程师小辉
2019/08/16
1.1K0
高并发编程-HashMap深入解析
在JDK1.8以前版本中,HashMap的实现是数组+链表,它的缺点是即使哈希函数选择的再好,也很难达到元素百分百均匀分布,而且当HashMap中有大量元素都存到同一个桶中时,这个桶会有一个很长的链表,此时遍历的时间复杂度就是O(n),当然这是最糟糕的情况。
JavaQ
2018/12/17
5880
HashMap你了解多少
在日常开发工作中,HashMap是使用频率相当高的一个工具,同时「HashMap」的底层实现和原理,也成了面试题中的常客。最近又翻看了一下源码,做个记录。(本文都是基于jdk1.8的源码)
TodoCoder
2022/09/23
2730
HashMap你了解多少
HashMap为什么是线程不安全的?
Java的HashMap是非线程安全的。多线程下应该用ConcurrentHashMap。
Java技术精选
2021/09/02
1.4K0
HashMap为什么存在线程不安全呢?
本文主要探讨下HashMap 在多线程环境下容易出现哪些问题,深层次理解其中的HashMap。
田维常
2020/05/19
8390
HashMap 底层实现、加载因子、容量值及死循环
写在前面:2020年面试必备的Java后端进阶面试题总结了一份复习指南在Github上,内容详细,图文并茂,有需要学习的朋友可以Star一下! GitHub地址:https://github.com/abel-max/Java-Study-Note/tree/master
用户5546570
2020/05/27
8570
HashMap 底层实现、加载因子、容量值及死循环
HashMap的resezi方法中尾部遍历出现死循环问题 Tail Traversing (多线程)
在看HashMap源码是看到了resize()的源代码,当时发现在将old链表中引用数据复制到新的链表中时,发现复制过程中时,源码是进行了反序,此时是允许反序存储的,同时这样设计的效率要高,不用采用尾部插入,每次都要遍历到尾部。
小勇DW3
2018/08/30
1K0
HashMap的resezi方法中尾部遍历出现死循环问题 Tail Traversing (多线程)
11张图让你彻底明白jdk1.7 hashmap的死循环是如何产生的
jdk1.7 hashmap的循环依赖问题是面试经常被问到的问题,如何回答不好,可能会被扣分。今天我就带大家一下梳理一下,这个问题是如何产生的,以及如何解决这个问题。
苏三说技术
2020/10/15
1.2K0
11张图让你彻底明白jdk1.7 hashmap的死循环是如何产生的
数据结构?从HashMap的源码分析开始!
首先,先看下inflateTable方法,这个是初始化HashMap里面的线性表的空间:
大大大大大先生
2018/09/04
3830
数据结构?从HashMap的源码分析开始!
Hashmap源码解析
做什么都怕进入狗咬尾巴的怪圈,上次看hashmap源码还是2012年,这次出去面试时被问到了hashmap的问题,整体思路还是记得的,巴拉巴拉一堆。回来再看一下源码,温习一下
码农戏码
2021/03/23
3710
JDK1.7 HashMap 导致循环链表
在淘宝内网里看到同事发了贴说了一个CPU被100%的线上故障,并且这个事发生了很多次,原因是在Java语言在并发情况下使用HashMap造成Race Condition,从而导致死循环。这个事情我4、5年前也经历过,本来觉得没什么好写的,因为Java的HashMap是非线程安全的,所以在并发下必然出现问题。但是,我发现近几年,很多人都经历过这个事(在网上查“HashMap Infinite Loop”可以看到很多人都在说这个事)所以,觉得这个是个普遍问题,需要写篇疫苗文章说一下这个事,并且给大家看看一个完美的“Race Condition”是怎么形成的。
陈树义
2019/02/13
1.1K0
JDK1.7 HashMap 导致循环链表
面试官邪魅一笑:HashMap 为什么线程不安全?
cnblogs.com/developer_chan/p/10450908.html
Java技术江湖
2020/04/20
4920
面试官邪魅一笑:HashMap 为什么线程不安全?
相关推荐
京东一面:为什么 HashMap 是线程不安全的?
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档