首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    深入理解JDK8 HashMap

    上一篇文章提到,HashMap在JDK7或者JDK8中采用的基本存储结构都是数组+链表形式,可能有人会提出疑问,HashMap在JDK8中不是数组+链表+红黑树吗?本文的回答是。至于为什么JDK8在一定条件下将链表转换为红黑树,我相信很多人都会回答:为了提高查询效率。基本答案可以说是这样的,JDK7中的HashMap对着Entry节点增多,哈希碰撞的概率在慢慢变大,这就直接导致哈希表中的单链表越来越长,这就大大降低了HashMap的查询能力,且时间复杂度可能会退化到O(n)。针对这种情况,JDK8做出了优化,就是在一定的条件下,链表会被转换为红黑树,提升查询效率。 HashMap在JDK8中基本结构示意图如下所示:

    01

    JDK8之后-JVM运行时数据区域

    首先弄清几个概念: 1.方法区(method area)只是JVM规范中定义的一个概念,用于存储类信息、常量池、静态变量、JIT编译后的代码等数据,具体放在哪里,不同的实现可以放在不同的地方。永久代是HotSpot虚拟机特有的概念,是对方法区的实现,别的JVM没有永久代的概念。(虽然去除了永久代,但是方法区作为概念上的区域仍然存在) 2.在JDK8中,JDK8的HotSpot VM已经是以前的HotSpot VM与JRockit VM的合并版,也就是传说中的“HotRockit”,只是产品里名字还是叫HotSpot VM。所以对于说JDK8去除永久代换成元空间的说法,就是默指的合并后的HotSpot虚拟机。 3.为什么要将永久代去除呢? 一方面是节省空间,避免了常见的永久内存错误:java.lang.OutOfMemoryError: PermGen问题。另一方面是为了整合JRockit,因为JRockit没有永代区这样类似的空间。 其实,从jdk7开始,就开始了永久代的转移工作,将譬如符号引用(Symbols)转移到了native heap;字面量(interned strings)转移到了java heap;等。但是指导JDK8永久代才被元空间替代。 4.元空间又是什么呢?以前存储在永久代里面的数据现在存在了哪里? 元空间是一块与堆不相连的本地内存。原本存在永久代的数据,一部分移到了java堆里面,一部分移到了本地内存里面(即元空间)(文档中原句:Move part of the contents of the permanent generation in Hotspot to the Java heap and the remainder to native memory.) 。永久代中原来存储的字符串常量(池)、符号引用(这两个在jdk7普遍就已经将其放在堆上了)和类的静态变量现在存储在java堆中,其余的数据作为元数据存储在元空间中。 5.什么是元数据呢? 元数据是数据的数据或者叫做用来描述数据的数据或者叫做信息的信息。(比如原本方法区存储的类信息、即时编译器编译后的代码等),也可以把元数据简单的理解成,最小的数据单位。元数据可以为数据说明其元素或属性(名称、大小、数据类型、等),或其结构(长度、字段、数据列),或其相关数据(位于何处、如何联系、拥有者)。 6.元空间详细:http://blog.csdn.net/lk7688535/article/details/51767460

    04

    HashMap 与 ConcurrentHashMap 底层实现

    我们存放的 hashMap 都会封装成一个节点对象 Entry(key,value),然后将此节点对象存放到一个数组中,存放前首先需要确定存放的数组下标:① 通过 hash(key) 算法得到 key 的 hashcode,并通过 hashcode的高16位和低16位进行异或操作(如果两个相应bit位相同,则结果为0,否则为1)得到32位的 int值,首先将高16位无符号右移16位与低十六位做异或运算。如果不这样做,而是直接做&运算(相同位的两个数字都为1,则为1;若有一个不为1,则为0)那么高十六位所代表的部分特征就可能被丢失 将高十六位无符号右移之后与低十六位做异或运算使得高十六位的特征与低十六位的特征进行了混合得到的新的数值,这样高位与低位的信息都被保留了 。② int值再与(数组长度-1:底位全为1,高位全为0)进行位运算,获取要存放的下标;③ 如果②中得到相同的值时,判断 key值是否相同,如果相同则新value替换旧value。如果key不相同,将value以链表的形式存放在同一个数组下标下,为了提高存放的速度,新的数据,将存放在原链表的头部。即新数据的 next 指向链表的头元素即可。需要注意的是,每次给链表的头部插入一个新的元素之后,需要将链表的头元素赋值给 table 的下标值。代码展示为 :

    02
    领券