JDK1.7和JDK1.8下HashMap源码分析
总结
存储对象时:我们将K/V传给put方法时,它调用hashCode计算hash从而得到bucket位置,进一步存储,HashMap会根据当前bucket的占用情况自动调整容量(超过LoadFacotr则resize为原来的2倍)。
获取对象时:我们将K传给get,它调用hashCode计算hash从而得到bucket位置,并进一步调用equals()方法确定键值对。
发生碰撞的时候:Hashmap通过链表将产生碰撞冲突的元素组织起来,在Java8中,如果一个bucket中碰撞冲突的元素超过某个限制(默认是8),则使用红黑树来替换链表,从而提高速度。
HashMap JDK1.7和1.8区别 一
对HashMap做下总结:
HashMap基于哈希散列表实现 ,可以实现对数据的读写。将键值对传递给put方法时,它调用键对象的hashCode()方法来计算hashCode,然后找到相应的bucket位置(即数组)来储存值对象。当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决hash冲突问题,当发生冲突了,对象将会储存在链表的头节点中。HashMap在每个链表节点中储存键值对对象,当两个不同的键对象的hashCode相同时,它们会储存在同一个bucket位置的链表中,如果链表大小超过阈值(TREEIFY_THRESHOLD,8),链表就会被改造为树形结构。
使用注意:
在重写equals的方法的时候,必须注意重写hashCode方法,同时还要保证通过equals判断相等的两个对象,调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象,其hashCode可以相同(只不过会发生哈希冲突,应尽量避免)。
一、初窥HashMap
HashMap是应用更广泛的哈希表实现,而且大部分情况下,都能在常数时间性能的情况下进行put和get操作。要掌握HashMap,主要从如下几点来把握:
jdk1.7中底层是由数组(也有叫做“位桶”的)+链表实现;jdk1.8中底层是由数组+链表/红黑树实现
可以存储null键和null值,线程不安全
初始size为16,扩容:newsize = oldsize*2,size一定为2的n次幂
扩容针对整个Map,每次扩容时,原来数组中的元素依次重新计算存放位置,并重新插入
插入元素后才判断该不该扩容,有可能无效扩容(插入后如果扩容,如果没有再次插入,就会产生无效扩容)
当Map中元素总数超过Entry数组的75%,触发扩容操作,为了减少链表长度,元素分配更均匀
二、jdk1.7中HashMap的实现
HashMap底层维护的是数组+链表
当两个key通过hashCode计算相同时,则发生了hash冲突(碰撞),HashMap解决hash冲突的方式是用链表。当发生hash冲突时,则将存放在数组中的Entry设置为新值的next(这里要注意的是,比如A和B都hash后都映射到下标i中,之前已经有A了,当map.put(B)时,将B放到下标i中,A则为B的next,所以新值存放在数组中,旧值在新值的链表上)。
图中,左边部分即代表哈希表,也称为哈希数组(默认数组大小是16,每对key-value键值对其实是存在map的内部类entry里的),数组的每个元素都是一个单链表的头节点,跟着的蓝色链表是用来解决冲突的,如果不同的key映射到了数组的同一位置处,就将其放入单链表中。
三、jdk1.8中HashMap的实现
在jdk1.8中HashMap的内部结构可以看作是数组(Node<K,V>[] table)和链表的复合结构,数组被分为一个个桶(bucket),通过哈希值决定了键值对在这个数组中的寻址(哈希值相同的键值对,则以链表形式存储。有一点需要注意,如果链表大小超过阈值(TREEIFY_THRESHOLD,8),图中的链表就会被改造为树形(红黑树)结构。
jdk1.7中HashMap采用的是位桶+链表的方式,即我们常说的散列链表的方式,而jdk1.8中采用的是位桶+链表/红黑树的方式,也是非线程安全的
HashMap JDK1.7和1.8区别 二
今天重温了下HashMap的源码,对比了下HashMap在jdk1.7和jdk1.8中的区别,搜到网上有一篇文章总结的挺好,于是摘抄了下来,另外也补充了一些自己总结的知识点和面试容易被问到的点(红色字体),有不正确的地方还请留言指正,谢谢。
学习jdk1.8中的HashMap之前,需要先了解下什么是红黑树(了解红黑树的同学直接从共同点开始看即可):
参考:https://www.cnblogs.com/ysocean/p/8032642.html
https://www.cnblogs.com/ysocean/p/8004211.html
二叉树:每个节点最多只能有两个子节点的树型结构。超过两个节点的成为多路树。
二叉搜索树:二叉搜索树是特殊的二叉树,需满足要求:若它的左子树不为空,则左子树上所有节点的值均小于它的根节点的值;若它的右子树不为空,则它的右子树上所有节点的值均大于它的根节点的值。它的左右子树也分别为二叉排序树。
如果是在平衡的二叉搜索树上,也就是说如果插入的数据是随机的,则其效率很高,其查找、插入和删除的时间复杂度都是O(logn),底数为2;如果插入的数据是有序的,比如从小到大的顺序,则数据的排布效果全部在根节点的右边,和链表没什么区别,这种情况下的时间复杂度为O(n),而不是O(logn),当然这是在最不平衡的条件下,实际情况下,二叉搜索树的效率应该在O(n)和O(logn)之间,这取决于树的不平衡度。
红-黑树:是一种用来保证树总是平衡的(或大部分是平衡的),也就是说,每个节点的左子树节点个数和右子树节点个数尽量相等。对于要插入的数据项(删除也是),插入例程要检查会不会破坏树的平衡,如果破坏了,程序就会通过改变节点的颜色、左旋、右旋的方式进行纠正,根据需要改变树的结构,从而保证树的平衡。
红黑树的特征:
有如下两个特征:
①、节点都有颜色;
②、在插入和删除的过程中,要遵循保持这些颜色的不同排列规则。
第一个很好理解,在红-黑树中,每个节点的颜色或者是黑色或者是红色的。当然也可以是任意别的两种颜色,这里的颜色用于标记,我们可以在节点类Node中增加一个boolean型变量isRed,以此来表示颜色的信息。
第二点,在插入或者删除一个节点时,必须要遵守的规则称为红-黑规则:
1.每个节点不是红色就是黑色的;
2.根节点总是黑色的;
3.如果节点是红色的,则它的子节点必须是黑色的(反之不一定),(也就是从每个叶子到根的所有路径上不能有两个连续的红色节点);
4.从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)。
从根节点到叶节点的路径上的黑色节点的数目称为黑色高度,规则 4 另一种表示就是从根到叶节点路径上的黑色高度必须相同。
注意:新插入的节点颜色总是红色的,这是因为插入一个红色节点比插入一个黑色节点违背红-黑规则的可能性更小,原因是插入黑色节点总会改变黑色高度(违背规则4),但是插入红色节点只有一半的机会会违背规则3(因为父节点是黑色的没事,父节点是红色的就违背规则3)。另外违背规则3比违背规则4要更容易修正。当插入一个新的节点时,可能会破坏这种平衡性,那么红-黑树是如何修正的呢?
引自:https://www.aliyun.com/jiaocheng/787890.html
参考文档:
https://blog.****.net/carson_ho/article/details/79373026
https://www.jianshu.com/p/8324a34577a0?utm_source=oschina-app
https://www.cnblogs.com/ysocean/p/8711071.html
-------------------------------华丽的分割线--------------------------------
共同点:
- 容量(capacity):HashMap中数组的长度
a. 容量范围:必须是2的幂 & <最大容量(2的30次方)
b. 初始容量 = 哈希表创建时的容量
默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
最大容量 = 2的30次方(若传入的容量过大,将被最大值替换)
static final int MAXIMUM_CAPACITY = 1 << 30;
- 加载因子(Load factor):HashMap在其容量自动增加前可达到多满的一种尺度
a. 加载因子越大、填满的元素越多 = 空间利用率高、但冲突的机会加大、查找效率变低(因为链表变长了)
b. 加载因子越小、填满的元素越少 = 空间利用率小、冲突的机会减小、查找效率高(链表不长)
默认加载因子 = 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f
扩容机制
扩容时resize(2 * table.length),扩容到原数组长度的2倍。
若key == null,则hash(key) = 0,则将该键-值 存放到数组table 中的第1个位置,即table [0]
异同点:
JDK1.7中使用一个Entry数组来存储数据,用key的hashcode取模来决定key会被放到数组里的位置,如果hashcode相同,或者hashcode取模后的结果相同(hashcollision),那么这些key会被定位到Entry数组的同一个格子里,这些key会形成一个链表。在hashcode特别差的情况下,比方说所有key的hashcode都相同,这个链表可能会很长,那么put/get操作都可能需要遍历这个链表也就是说时间复杂度在最差情况下会退化到O(n)
JDK1.7中
使用一个Entry数组来存储数据,用key的hashcode取模来决定key会被放到数组里的位置,如果hashcode相同,或者hashcode取模后的结果相同(hash collision),那么这些key会被定位到Entry数组的同一个格子里,这些key会形成一个链表。
在hashcode特别差的情况下,比方说所有key的hashcode都相同,这个链表可能会很长,那么put/get操作都可能需要遍历这个链表
也就是说时间复杂度在最差情况下会退化到O(n)。
发生hash冲突时,新元素插入到链表头中,即新元素总是添加到数组中,就元素移动到链表中。
在扩容resize()过程中,采用单链表的头插入方式,在将旧数组上的数据 转移到 新数组上时,转移操作 = 按旧链表的正序遍历链表、在新链表的头部依次插入,即在转移数据、扩容后,容易出现链表逆序的情况 。
HashMap线程不安全的一个重要原因就是:多线程下resize()容易出现死循环
此时若(多线程)并发执行 put()操作,一旦出现扩容情况,则 容易出现 环形链表,从而在获取数据、遍历链表时 形成死循环(Infinite Loop),即 死锁的状态 。
JDK1.8中
使用一个Node数组来存储数据,但这个Node可能是链表结构,也可能是红黑树结构
如果插入的key的hashcode相同,那么这些key也会被定位到Node数组的同一个格子里。
如果同一个格子里的key不超过8个,使用链表结构存储。
如果超过了8个,那么会调用treeifyBin函数,将链表转换为红黑树。
那么即使hashcode完全相同,由于红黑树的特点,查找某个特定元素,也只需要O(log n)的开销
也就是说put/get的操作的时间复杂度最差只有O(log n)
由于 JDK 1.8 转移数据操作 = 按旧链表的正序遍历链表、在新链表的尾部依次插入,所以不会出现链表 逆序、倒置的情况,故不容易出现环形链表的情况 ,但jdk1.8仍是线程不安全的,因为没有加同步锁保护。
发生hash冲突后,会优先判断该节点的数据结构式是红黑树还是链表,如果是红黑树,则在红黑树中插入数据,如果是链表,则将数据插入到链表的尾部并判断链表长度是否大于8,如果大于8要转成红黑树,另一还要判断数组长度是否超过阀值,超过阀值要进行扩容。听起来挺不错,但是真正想要利用JDK1.8的好处,有一个限制:
key的对象,必须正确的实现了Compare接口
如果没有实现Compare接口,或者实现得不正确(比方说所有Compare方法都返回0)
那JDK1.8的HashMap其实还是慢于JDK1.7的
简单的测试数据如下:
向HashMap中put/get 1w条hashcode相同的对象
JDK1.7: put 0.26s,get 0.55s
JDK1.8(未实现Compare接口):put 0.92s,get 2.1s
但是如果正确的实现了Compare接口,那么JDK1.8中的HashMap的性能有巨大提升,这次put/get 100W条hashcode相同的对象
JDK1.8(正确实现Compare接口,):put/get大概开销都在320ms左右
为什么要这么操作呢?
我认为应该是为了避免Hash Collision DoS攻击
Java中String的hashcode函数的强度很弱,有心人可以很容易的构造出大量hashcode相同的String对象。
如果向服务器一次提交数万个hashcode相同的字符串参数,那么可以很容易的卡死JDK1.7版本的服务器。
但是String正确的实现了Compare接口,因此在JDK1.8版本的服务器上,Hash Collision DoS不会造成不可承受的开销。
补充:为什么说HashMap是线程不安全的?
参考文档:https://www.cnblogs.com/qiumingcheng/p/5259892.html
参考文章:
不做标题党,只做纯干货】HashMap在jdk1.7和1.8中的实现
优质资源:
一个比较完善的HashMap源码分析的博客链接:https://www.cnblogs.com/chengxiao/p/6059914.html