时间:2021-05-20
示例:有一定基础的小伙伴们可以选择性的跳过该步骤
HashMap是Java程序员使用频率最高的用于映射键值对(key和value)处理的数据类型。随着JDK版本的跟新,JDK1.8对HashMap底层的实现进行了优化,列入引入红黑树的数据结构和扩容的优化等。本文结合JDK1.7和JDK1.8的区别,深入探讨HashMap的数据结构实现和功能原理。
Java为数据结构中的映射定义了一个接口java.uti.Map,此接口主要有四个常用的实现类,分别是HashMap,LinkedHashMap,Hashtable,TreeMap,IdentityHashMap。本篇文章主要讲解HashMap以及底层实现原理。
既然讲HashMap,那就不得不说一下JDK7与JDK8(及jdk8以后)的HashMap有什么区别:
面试的时候,面试官经常会问道一个问题:为什么HashMap的默认负载因子是0.75,而不是0.5或者是整数1呢?
答案有两种:
写数据之后会可能触发扩容,HashMap结构内,我记得有一个记录当前数据量的字段,这个数据量字段到达扩容阈值的话,它就会触发扩容的操作
阈值(threshold) = 负载因子(loadFactor) x 容量(capacity)
当HashMap中table数组(也称为桶)长度 >= 阈值(threshold) 就会自动进行扩容。
扩容的规则是这样的,因为table数组长度必须是2的次方数,扩容其实每次都是按照上一次tableSize位运算得到的就是做一次左移1位运算,
假设当前tableSize是16的话 16转为二进制再向左移一位就得到了32 即 16 << 1 == 32 即扩容后的容量,也就是说扩容后的容量是当前
容量的两倍,但记住HashMap的扩容是采用当前容量向左位移一位(newtableSize = tableSize << 1),得到的扩容后容量,而不是当前容量x2
问题又来了,为什么计算扩容后容量要采用位移运算呢,怎么不直接乘以2呢?
这个问题就比较简单了,因为cpu毕竟它不支持乘法运算,所有的乘法运算它最终都是再指令层面转化为了加法实现的,这样效率很低,如果用位运算的话对cpu来说就非常的简洁高效。
老问题又来了,为啥HashMap中初始化大小为什么是16呢?
首先我们看hashMap的源码可知当新put一个数据时会进行计算位于table数组(也称为桶)中的下标:
int index =key.hashCode()&(length-1);
hahmap每次扩容都是以 2的整数次幂进行扩容
因为是将二进制进行按位于,(16-1) 是 1111,末位是1,这样也能保证计算后的index既可以是奇数也可以是偶数,并且只要传进来的key足够分散,均匀那么按位于的时候获得的index就会减少重复,这样也就减少了hash的碰撞以及hashMap的查询效率。
那么到了这里你也许会问? 那么就然16可以,是不是只要是2的整数次幂就可以呢?
答案是肯定的。那为什么不是8,4呢? 因为是8或者4的话很容易导致map扩容影响性能,如果分配的太大的话又会浪费资源,所以就使用16作为初始大小。
JDK7与JDK8及以后的HashMap结构与存储原理有所不同:
Jdk1.7:数组 + 链表 ( 当数组下标相同,则会在该下标下使用链表)
Jdk1.8:数组 + 链表 + 红黑树 (预值为8 如果链表长度 >=8则会把链表变成红黑树 )
Jdk1.7中链表新元素添加到链表的头结点,先加到链表的头节点,再移到数组下标位置
Jdk1.8中链表新元素添加到链表的尾结点
(数组通过下标索引查询,所以查询效率非常高,链表只能挨个遍历,效率非常低。jdk1.8及以
上版本引入了红黑树,当链表的长度大于或等于8的时候则会把链表变成红黑树,以提高查询效率)
前面寻址算法都是一样的,根据key的hashcode经过高低位异或之后的值,再按位与 &(table.lingth - 1),得到一个数组下标,然后根据这个数组下标内的状况,状况不同,然后情况也不同,大概分为了4种状态:
( 1.)第一种就是数组下标下内容为空:
这种情况没什么好说的,为空据直接占有这个slot槽位就好了,然后把当前.put方法传进来的key和value包装成一个node对象,放到这个slot中就好了。
( 2.)第二种情况就是数组下标下内容不为空,但它引用的node还没有链化:
这种情况下先要对比一下这个node对象的key与当前put对象的key是否完全.相等,如果完全相等的情况下,就行进行replace操作,把之前的槽位中node.下的value替换成新的value就可以了,否则的话这个put操作就是一个正儿.八经的hash冲突,这种情况在slot槽位后面追加一个node就可以了,用尾插法 ( 前面讲过,jdk7是把新增元素添加到头部节点,而jdk8则添加到尾部节点)。
( 3.)第三种就是该数组下标下内容已经被链化了:
这种情况和第二种情况处理很相似,首先也是迭代查找node,看看链表上中元素的key,与当前传过来的key是否完全一致,如果完全一致的话还是repleace操作,用put过来的新value替换掉之前node中的value,否则的话就是一致迭代到链表尾节点也没有匹配到完全一致的node,就和之前的一样,把put进来数据包装成node追加到链表的尾部,再检查一下当前链表的长度,有没有达到树化阈值,如果达到了阈值就调用一个树化方法,树化操作都是在这个方法里完成的。
( 4.)第四种情况就是冲突很严重的情况下,这个链表已经转化成红黑树了:
红黑树就比较复杂 要将清楚这个红黑树还得从TreeNode说起 TreeNode继承了Node结构,在Node基础上加了几个字段,分别是指向父节点parent字段,指向左子节点left字段,指向右子节点right字段,还有一个表示颜色的red字段,这就是TreeNode的基本结构,然后红黑树的插入操作,首先找到一个合适的插入点,就是找到插入节点的父节点,然后红黑树它又满足二叉树的所有特性,所以找这个父节点的操作和二叉树排序是完全一致的,然后说一下这个二叉树排序,其实就是二分查找算法映射出来的结构,就是一个倒立的二叉树,然后每个节点都可以有自己的子节点,本且左节点小于但前节点,右节点大于当前节点,然后每次向下查找一层就能那个排除掉一半的数据,查找效率非常的高效,当查找的过程中也是分情况的。
首先第一种情况就是一直向下探测,直到查询到左子树或者右子树位null,说明整个树中,并没有发现node链表中的key与当前put key一致的TreeNode,那此时探测节点就是插入父节点的所在了,然后就是判断插入节点的hash值和父节点的hash值大小决定插入到父节点的左子树还是右子树。当然插入会打破平衡,还需要一个红黑树的平衡算法保持平衡。
其次第二种情况就是根节点在向下探测过程中发现TreeNode中key与当前put的key完全一致,然后就也是一次repleace操作,替换value。
其实主要就是为了解决jdk1.8以前hash冲突所导致的链化严重的问题,因为链表结构的查询效率是非常低的,他不像数组,能通过索引快速找到想要的值,链表只能挨个遍历,当hash冲突非常严重的时候,链表过长的情况下,就会严重影响查询性能,本身散列列表最理想的查询效率为O(1),当时链化后链化特别严重,他就会导致查询退化为O(n)为了解决这个问题所以jdk8中的HashMap添加了红黑树来解决这个问题,当链表长度>=8的时候链表就会变成红黑树,红黑树其实就是一颗特殊的二叉排序树嘛,这个时间复杂…反正就是要比列表强很多
迁移其实就是挨个桶位推进迁移,就是一个桶位一个桶位的处理,主要还是看当前处理桶位的数据状态把,这里也是分了大概四种状态:
这四种的迁移规则都不太一样
(1.)第一种就是数组下标下内容为空:
这种情况下就没什么可说的,不用做什么处理。
( 2.)第二种情况就是数组下标下内容不为空,但它引用的node还没有链化:
当slot它不为空,但它引用的node还没有链化的时候,说明这个槽位它没有发生过hash冲突,直接迁移就好了,根据新表的tableSize计算出他在新表的位置,然后存放进去就好了。
( 3.)第三种就是slot内储存了一个链化的node:
当node中next字段它不为空,说明槽位发生过hash冲突,这个时候需要把当前槽位中保存的这个链表拆分成两个链表,分别是高位链和低位链
(4.)第四种就是该槽位储存了一个红黑树的根节点TreeNode对象:
这个就很复杂了,本文章暂时不做过多的介绍(博主还没整明白 =_=! )
到此这篇关于HashMap底层实现原理详解的文章就介绍到这了,更多相关HashMap底层实现原理内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持!
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
hashtable底层实现原理如下: 1、HashTable类中,保存实际数据的,依然是Entry对象。其数据结构与HashMap是相同的。 2、HashT
对于HashSet而言,它是基于HashMap实现的,HashSet底层采用HashMap来保存所有元素,因此HashSet的实现比较简单,查看HashSet的
hashtable底层原理如下: 1、HashTable类中,保存实际数据的,依然是Entry对象。其数据结构与HashMap是相同的。 2、HashTab
简介本篇将简单讲解Java集合框架中的HashSet与HashMap。散列集(HashSet)快速入门底层原理:动态数组加单向链表或红黑树。JDK1.8之后,当
一、ListSet区别List有序,可重复;Set无序,不重复;二、ListSet实现类间区别及原理Arraylist底层实现使用Object[],数组查询效率