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

HashMap的数据结构浅析[通俗易懂]HashMap是非线程安全的。而HashMap的线程不安全主要体现在resize时的死循环HashMap工作原理HashMap数据结构常用的底层数据结构主要有数组和链表。数组存储区间连续,占用内存较多,寻址容易,插入和删除困难。链表存储区间离散,占用内存较少,寻址困难,插入和删除容易。HashMap要实现的是哈希表的效果,尽量实现O(1)级别的增删改查。它的具体实现则是同时使用…

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

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

HashMap工作原理

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

HashMap的寻址方式

  • 对于新插入的数据或者待读取的数据,HashMap将Key的哈希值对数组长度取模,结果作为该Entry在数组中的index。因此数组的长度必须时2的N次方,实际中,HashMap会自动通过Integer.highestOneBit算出比指定整数大的最小的N值。
        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时由链表的数据结构转换成红黑树的数据结构)
    Java8HashMap.png

JDK1.7中线程不安全的HashMap

  • 上文讲到占用空间超过加载因子的值时,就会自动扩容,这时HashMap中的元素或重新计算排序,这显然是不能保证线程安全的,而且在多线程并发调用时,可能出现死循环。
  • 首先:先给出resize的核心代码:
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,这里就有一种可能性,这两个线程在调用的时候线程访问.png
  • 当两个线程痛时执行的时候,可能有一个会被挂起,等待另一个结束后在继续执行,这时问题就产生了;
    HashMap线程不安全图解.png
  • 产生死循环的原因是: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浅析

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • bat 剪切文件_bat延时命令

    bat 剪切文件_bat延时命令扩展名是bat(在nt/2000/xp/2003下也可以是cmd)的文件就是批处理文件。首先批处理文件是一个文本文件,这个文件的每一行都是一条DOS命令(大部分时候就好象我们在DOS提示符下执行的命令行一样),你可以使用DOS下的Edit或者Windows的记事本(notepad)等任何文本文件编辑工具创建和修改批处理文件。其次,批处理文件是一种简单的程序,可以通过条件语句(if)和流程控制语句(…

  • 解释afterPropertiesSet

    在spring的bean的生命周期中,实例化->生成对象->属性填充后会进行afterPropertiesSet方法,这个方法可以用在一些特殊情况中,也就是某个对象的某个属性需要经过外界得到,比如说查询数据库等方式,这时候可以用到spring的该特性,只需要实现InitializingBean即可:@Component(“a”)publicclassAimplementsInitializingBean{privateBb;publicA(Bb){

  • idea2020.2.1激活码【2021免费激活】

    (idea2020.2.1激活码)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html3MRUAPM31O-eyJsaWNlbnNlSW…

  • 轮到你了 番外篇_碳酸危机52书库

    轮到你了 番外篇_碳酸危机52书库饰品模型篇乐高生活大爆炸对于乐高积木,其实我也是早有耳闻。但是高昂的价格摆在那里,我也只能望而却步。而送给程序员最好的礼物里面,也包含有可编程的乐高机器人,可见对于工科男来说,乐高真的是非常棒的礼物了。而我拥有的第一款乐高玩具,是我研二暑假的时候。那个时候正好也没什么事,看了好几天的乐高论坛以后,觉得科技系列的模型很棒,很符合我那藏在内心深处的,对于马达齿轮传动装置等机械品的向往。于

  • 共享锁、排他锁、互斥锁、悲观锁、乐观锁、行锁、表锁、页面锁、不可重复读、丢失修改、读脏数据

    点击上方“全栈程序员社区”,星标公众号 重磅干货,第一时间送达 作者:T-Birds blog.csdn.net/weixin_36634753/article/details/9…

  • make menuconfig执行报错

    make menuconfig执行报错1、flex:未找到命令解决办法:yuminstallflex2、bison:未找到命令解决办法:yuminstallbison缺什么安装什么,很简单最后再次执行makemenuconfig

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号