HashMap在JDK7和JDK8中的区别

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

在[深入浅出集合Map]中,已讲述了HashMap在jdk7中实现,在此就不再细说了

JDK7中的HashMap

基于链表+数组实现,底层维护一个Entry数组

Entry<K,V>[] table;

根据计算的hashCode将对应的KV键值对存储到该table中,一旦发生hashCode冲突,那么就会将该KV键值对放到对应的已有元素的后面, 此时,形成了一个链表式的存储结构,如下图

HashMap在JDK7和JDK8中的区别

JDK8中的HashMap

基于位桶+链表/红黑树的方式实现,底层维护一个Node数组

Node<K,V>[] table;

在JDK7中HashMap,当成百上千个节点在hash时发生碰撞,存储一个链表中,那么如果要查找其中一个节点,那就不可避免的花费O(N)的查找时间,这将是多么大的性能损失,这个问题终于在JDK8中得到了解决。

JDK8中,HashMap采用的是位桶+链表/红黑树的方式,当链表的存储的数据个数大于等于8的时候,不再采用链表存储,而采用了红黑树存储结构。这是JDK7与JDK8中HashMap实现的最大区别。
如下图所示:

HashMap在JDK7和JDK8中的区别

这么做主要是再查询的时间复杂度上进行优化,链表为O(n),而红黑树一直是O(logn),冲突(即为相同的hash值存储的元素个数) 超过8个,可以大大的提高查找性能。

其他异同

共同点

1.容量(capacity):容量为底层数组的长度,JDK7中为Entry数组,JDK8中为Node数组
a. 容量一定为2的次幂

static int indexFor(int h, int length) {  
    return h & (length-1);  
}  

这段代码是用来计算出键值对存放在一个数组的索引,h是int hash = hash(key.hashCode())计算出来的,SUN大师们发现, “当容量一定是2^n时,h & (length - 1) == h % length” ,按位运算特别快 。
源码中大量使用运算,对于计算机,位运算计算效率特别快,毕竟二进制才是亲儿子呀

b. 默认初始容量16(容量为低层数组的长度,JDK7中为Entry数组,JDK8中为Node数组)

c.最大容量1<<30,即2的30次方

<< 30 = 1073741824
1 << 31 = -2147483648
1 << 32 = 1
1 << 33 = 2
1 << -1 = -2147483648

hashmap的“最大容量“其实是Integer.MAX_VALUE

2.加载因子(Load factor):HashMap在其容量自动增加前可达到多满的一种尺度
a.  默认加载因子 = 0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f 
  • 加载因子越大、填满的元素越多 = 空间利用率高、但冲突的机会加大、查找效率变低(因为链表变长了)

  • 加载因子越小、填满的元素越少 = 空间利用率小、冲突的机会减小、查找效率高(链表不长)
    0.75是一个"冲突的机会"与"空间利用率"之间寻找一种平衡与折衷的选择

3.扩容机制:扩容时resize(2 * table.length),扩容到原数组长度的2倍。

4.key为null:若key == null,则hash(key) = 0,则将该键-值 存放到数组table 中的第1个位置,即table [0]

   static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
不同点

1.发生hash冲突时
JDK7:发生hash冲突时,新元素插入到链表头中,即新元素总是添加到数组中,就元素移动到链表中。
JDK8:发生hash冲突后,会优先判断该节点的数据结构式是红黑树还是链表,如果是红黑树,则在红黑树中插入数据;如果是链表,则将数据插入到链表的尾部并判断链表长度是否大于8,如果大于8要转成红黑树。

2.扩容时
JDK7:在扩容resize()过程中,采用单链表的头插入方式,在将旧数组上的数据 转移到 新数组上时,转移操作 = 按旧链表的正序遍历链表、在新链表的头部依次插入,即在转移数据、扩容后,容易出现链表逆序的情况 。
多线程下resize()容易出现死循环。此时若(多线程)并发执行 put()操作,一旦出现扩容情况,则 容易出现 环形链表,从而在获取数据、遍历链表时 形成死循环(Infinite Loop),即 死锁的状态 。

JDK8:由于 JDK 1.8 转移数据操作 = 按旧链表的正序遍历链表、在新链表的尾部依次插入,所以不会出现链表 逆序、倒置的情况,故不容易出现环形链表的情况 ,但jdk1.8仍是线程不安全的,因为没有加同步锁保护。

建议:
1.使用时设置初始值,避免多次扩容的性能消耗
2.使用自定义对象作为key时,需要重写hashCode和equals方法
3.多线程下,使用CurrentHashMap代替HashMap

推荐阅读:

「深入浅出」集合Map

javaWeb传收参数方式总结

周末了,笑久一点~

如果觉得不错,请给个「好看」

分享给你的朋友!

HashMap在JDK7和JDK8中的区别

HashMap在JDK7和JDK8中的区别

HashMap在JDK7和JDK8中的区别

 THANDKS

- End -

一个立志成大腿而每天努力奋斗的年轻人

伴学习伴成长,成长之路你并不孤单!


HashMap在JDK7和JDK8中的区别
java从心
扫描二维码,关注公众号

原文始发于微信公众号(java从心):HashMap在JDK7和JDK8中的区别