热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

HashMap并发情况下,导致闭环链

主要是由于hashmap的resize方法引起,resize是扩容map大小。里面个transfer方法,用于将原表中的结点重新hash,并放入到新表相应的index中。

  主要是由于hashmap的resize方法引起,resize是扩容map大小。

   里面个transfer方法,用于将原表中的结点重新hash,并放入到新表相应的index中。

   transfer方法如下:


void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry e : table) { //依次从旧数组元素下标0开始循环这个旧表
            while(null != e) {  //循环处理对应数据元素,重新hash,并放入到旧表
                Entry 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;
            }
        }
    }


   这个方法就是将旧表的元素重新hash,然后放入到新表的相应位置中。

  而这里高并发会导致元素的互相指向,形成闭环,如:3<->7。

  下面具体分析这种情况:假设当前容器大小为2,threshold为1(实际情况中不会这么设,会导致查找慢)。hash采用最简单的mod,因此3和7这两个key映射在table的下标为1的位置。

 而为了解决冲突,采用链式来解决,即数组table第二个元素(下标为1)存储了3->7。(即3结点中的next指向了7)

  这时假设需要插入key 8,由于达到扩容条件(即当前元素>=threshold*容器大小=2),这时扩容后大小为4(原先table大小*2)

  因此进行扩容:

  线程一,执行上述transfer代码:

  线程一:

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry e : table) {
            while(null != e) { 
                Entry 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;
            }
        }
    }

这时,线程1线程栈中,e为3,next值为7


然后,线程2执行上述代码,最终将结点3,结点7放入新表中,即: 7和3在table下标为3中,7->3

在这个过程中,线程2修改了引用结点7,使其中的next字段指向了3(这就是引起闭环的主要原因)


接着线程一继续执行,当前e为3,next为7

第一步,将当前处理的结点3放入新表newTable(下标为3),然后将结点3的next指向null(因此newTable是处于线程栈中,是线程私有的,并不受线程2影响)

  这部处理完后,newTable下标为3的内容为:3(其next指向null)


第二步,处理结点7,这时当前结点e为7,而next由于线程2修改了其引用,所以next为3。

            这步处理完后,其newTable下标为3的内容为:7(指向3),3(指向null)


第三步,这步是引起闭环的最终原因,当前处理结点为3,next值为null

        这时使3指向newTable中的7,然后将3存入newTable

      这步处理完后,newTable下标为3的内容为:

    3(指向7),7(指向3)。


查找时,查找key为11的值,这时查找table下标为3的内容,先找3,不匹配,然后找7.也不对,这时查7指向的3.。。。。

 死循环





 

  

 



推荐阅读
  • HashTable与ConcurrentHashMap均可实现HashMap的功能,对外提供了键值对存储的数据结构。但是在内部结构及实现上有何区别,性能上的差异到底在哪里又是如何导致的 ... [详细]
  • HashMap的相关问题及其底层数据结构和操作流程
    本文介绍了关于HashMap的相关问题,包括其底层数据结构、JDK1.7和JDK1.8的差异、红黑树的使用、扩容和树化的条件、退化为链表的情况、索引的计算方法、hashcode和hash()方法的作用、数组容量的选择、Put方法的流程以及并发问题下的操作。文章还提到了扩容死链和数据错乱的问题,并探讨了key的设计要求。对于对Java面试中的HashMap问题感兴趣的读者,本文将为您提供一些有用的技术和经验。 ... [详细]
  • Java之HashMap在多线程情况下导致死循环的问题
    PS:不得不说Java编程思想这本书是真心强大..学习内容:1.HashMap<K,V>在多线程的情况下出现的死循环现象当初学Java的时候只是知道HashMap< ... [详细]
  • 转载自:http:www.blogjava.netCarpenterLeearchive20160427430268.html总体介绍之所以把HashSet和HashMa ... [详细]
  • 缓存这个东西就是为了提高运行速度的,由于缓存是在寸土寸金的内存里面,不是在硬盘里面,所以容量是很有限的。LRU这个算法就是把最近一次使用时间离现在时间最远的数据删除掉。先说说List:每 ... [详细]
  • 手写HashMap,快手面试官直呼内行
    手写HashMap,快手面试官直呼内行-手写HashMap?这么狠,面试都卷到这种程度了?第一次见到这个面试题,是在某个不方便透露姓名的Offer收割机大佬的文章:这……我当 ... [详细]
  • Java面试 HashMap、HashSet源码解析
    本章所有源代码基于JDK1.8版本HashMap和HashSet是JavaCollectionFramework的两个重要成员,其中HashMap是Map接口的常用实现类,Hash ... [详细]
  • JDK源码学习之HashTable(附带面试题)的学习笔记
    本文介绍了JDK源码学习之HashTable(附带面试题)的学习笔记,包括HashTable的定义、数据类型、与HashMap的关系和区别。文章提供了干货,并附带了其他相关主题的学习笔记。 ... [详细]
  • HashMap的扩容知识详解
    本文详细介绍了HashMap的扩容知识,包括扩容的概述、扩容条件以及1.7版本中的扩容方法。通过学习本文,读者可以全面了解HashMap的扩容机制,提升对HashMap的理解和应用能力。 ... [详细]
  • 本篇文章给大家分享的是有关Java中怎么对HashMap按键值排序,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话 ... [详细]
  • 01Map集合概述A:Map集合概述:我们通过查看Map接口描述,发现Map接口下的集合与Collection接口下的集合,它们存储数据的形式不同a:Collection中的集合 ... [详细]
  • 邮件解析引擎FastMail库大功告成!
    1概述邮件解析库API完全使用面向对象技术设计,使用C++语言开发的用于邮件解析和组装的库。它提供了一些类用来解析和组装Internet邮件,如MimeMessa ... [详细]
  • 将学生对象和学生的归属地通过键与值存储到map集合中。importjava.util.HashMap;importjava.util.Iterator;importjava.uti ... [详细]
  • 在Java中有多种遍历HashMap的方法,注意Java中所有的Map类型都实现了共有的Map接口,所以接下来方法适用于所有Map(如:HaspMap,TreeMap,Linked ... [详细]
  • 写这篇文章起源于一道面试题,如何将自定义的类对象作为key存储到HashMap中,即考虑怎么判断key的唯一性。首先,我们看以下HashMap中put(…)方法的源码:public ... [详细]
author-avatar
手机用户2502907463
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有