详解并发下的HashMap以及JDK8的优化

PhilipAnn 发布于5月前
0 条问题

HashMap使用链表法避免哈希冲突(相同hash值),当链表长度大于TREEIFY_THRESHOLD(默认为8)时,将链表转换为红黑树。 当小于等于UNTREEIFY_THRESHOLD(默认为6)时,又会退化回链表以达到性能均衡。 下图为HashMap的数据结构(数组+链表+红黑树 )

详解并发下的HashMap以及JDK8的优化

HashMap在并发时出现的问题

1.多线程put的时候可能导致元素丢失

主要问题出在addEntry方法的new Entry (hash, key, value, e),如果两个线程都同时取得了e,则他们下一个元素都是e,然后赋值给table元素的时候有一个成功有一个丢失。

2.多线程put后可能导致get死循环

造成死循环的原因是多线程进行put操作时,触发了HashMap的扩容(resize函数),出现链表的两个结点形成闭环,导致死循环。 下图为JDK8中的put操作流程,详情请自行查看源码。

详解并发下的HashMap以及JDK8的优化

单线程resize过程

详解并发下的HashMap以及JDK8的优化

首先我们把resize函数中的transfer()的关键代码贴出来:


 

while(null != e) {

Entry<K,V> 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;

}

我们可以再简化一下,因为中间的i就是判断新表的位置,我们可以跳过。 简化后代码:


 

while(null != e) {

Entry<K,V> next = e.next;

e.next = newTable[i]; //假设线程一执行完这里就被调度挂起了

newTable[i] = e;

e = next;

}

去掉了一些与本过程冗余的代码,意思就非常清晰了:

  1. Entry<K,V> next = e.next;// 因为是单链表,如果要转移头指针,一定要保存下一个结点,不然转移后链表就丢了

  2. e.next = newTable[i];// e要插入到链表的头部,所以要先用e.next指向新的 Hash表第一个元素(为什么不加到新链表最后? 因为复杂度是 O(N))

  3. newTable[i] = e;// 现在新Hash表的头指针仍然指向e没转移前的第一个元素,所以需要将新Hash表的头指针指向e

  4. e = next;// 转移e的下一个结点

并发时resize过程

e.next = newTable[i];

详解并发下的HashMap以及JDK8的优化

而我们的线程二执行完成了。 于是我们有下面的这个样子。

因为Thread1的 e 指向了key(3),而next指向了key(7),其在线程二rehash后,指向了线程二重组后的链表。我们可以看到链表的顺序被反转后。

  1. 线程一被调度回来执行。

    1. 执行 newTalbe[i] = e。

    2. 执行e = next,导致了e指向了key(7)。

    3. 下一次循环的next = e.next导致了next指向了key(3)。

详解并发下的HashMap以及JDK8的优化

  1. 一切安好。线程一接着工作。把key(7)摘下来,放到newTable[i]的第一个,然后把e和next往下移。

详解并发下的HashMap以及JDK8的优化

  1. 环形链接出现。 e.next = newTable[i] 导致 key(3).next 指向了 key(7)。 注意: 此时的key(7).next 已经指向了key(3), 环形链表就这样出现了。

详解并发下的HashMap以及JDK8的优化

于是,当我们的线程一调用到,HashTable.get(11)时,悲剧就出现了——Infinite Loop。

JDK8中HashMap的优化

1.长链表的优化

在JDK8中,如果链表的长度大于等于8 ,那么链表将转化为红黑树; 当长度小于等于6时,又会变成一个链表

红黑树的平均查找长度是log(n),长度为8的时候,平均查找长度为3,如果继续使用链表,平均查找长度为8/2=4,这才有转换为树的必要。 链表长度如果是小于等于6,6/2=3,虽然速度也很快的,但是转化为树结构和生成树的时间并不会太短。 还有选择6和8,中间有个差值7可以有效防止链表和树频繁转换。 假设一下,如果设计成链表个数超过8则链表转换成树结构,链表个数小于8则树结构转换成链表,如果一个HashMap不停的插入、删除元素,链表个数在8左右徘徊,就会频繁的发生树转链表、链表转树,效率会很低。

注意,当数组长度小于64(常量定义)的时候,扩张数组长度一倍,否则的话把链表转为树。 并不是每次都直接树化的。

此外,在JDK7中,hash计算的时候会对操作数进行右移操作,计算复杂,目的是将高位也参与运算,减少hash碰撞; 在JDK8中,链表可以转变成红黑树,所以hash计算也变得简单。 下面的图为JDK8中的hash计算和索引计算。

详解并发下的HashMap以及JDK8的优化

2.hash碰撞的插入方式的优化

发生hash碰撞时,JDK7会在链表头部插入,而JDK8会在链表尾部插入。 头插法是操作速度最快的,找到数组位置就直接找到插入位置了,但JDK8之前hashmap这种插入方法在并发场景下会出现死循环。 JDK8开始hashmap链表在节点长度达到8之后会变成红黑树,这样一来在数组后节点长度不断增加时,遍历一次的次数就会少很多(否则每次要遍历所有),而且也可以避免之前的循环列表问题。 同时如果变成红黑树,也不可能做头插法了。

3.扩容机制的优化

在JDK7中,对所有链表进行rehash计算; 在JDK8中,实际上也是通过取余找到元素所在的数组的位置,取余的方式在putVal里面: i = (n - 1) & hash。 我们假设,在扩容之前,key取余之后留下了n位。 扩容之后,容量变为2倍,所以key取余得到的就有n+1位。 在这n+1位里面,如果第1位是0,那么扩容前后这个key的位置还是在相同的位置(因为hash相同,并且余数的第1位是0,和之前n位的时候一样,所以余数还是一样,位置就一样了); 如果这n+1位的第一位是1,那么就和之前的不同,那么这个key就应该放在之前的位置再加上之前整个数组的长度的位置。 这样子就减少了移动所有数据带来的消耗。 (慢慢读两遍,想明白了,就觉得这个其实不看图更好理解)

详解并发下的HashMap以及JDK8的优化

常见FAQ

HashMap扩容条件

查看JDK7源码的put函数,然后跳转到addEntry函数。 然后你会发现JDK7中hashmap扩容是要同时满足两个条件:

  1. 当前数据存储的数量(即size())大小必须大于等于阈值

  2. 当前加入的数据是否发生了hash冲突

因为上面这两个条件,所以存在下面两种情况:

  1. 就是hashmap在存值的时候(默认大小为16,负载因子0.75,阈值12),可能达到最后存满16个值的时候,再存入第17个值才会发生扩容现象,因为前16个值,每个值在底层数组中分别占据一个位置,并没有发生hash碰撞。

  2. 当然也有可能存储更多值(超多16个值,最多可以存26个值)都还没有扩容。 原理: 前11个值全部hash碰撞,存到数组的同一个位置(这时元素个数小于阈值12,不会扩容),后面所有存入的15个值全部分散到数组剩下的15个位置(这时元素个数大于等于阈值,但是每次存入的元素并没有发生hash碰撞,所以不会扩容),前面11+15=26,所以在存入第27个值的时候才同时满足上面两个条件,这时候才会发生扩容现象。

而在JDK8中,扩容的条件只有一个,就是当前容量大于阈值(阈值等于当前hashmap最大容量乘以负载因子)

HashMap在JDK7中扩容计算新索引的方法

通过transfer方法将旧数组中的元素复制到新数组,在这个方法中进行了包括释放旧的Entry中的对象引用,该过程中如果需要重新计算hash值就重新计算,然后根据indexfor()方法计算索引值。 而索引值的计算方法为: h & (length-1) ,即hashcode计算出的hash值和数组长度进行与运算。

一般认为,Java的%、/操作比&慢10倍左右,因此采用&运算而不是h % length会提高性能。

HashMap在JDK8中计算索引的方法

这个设计确实非常的巧妙,既省去了重新计算hash值的时间,也就是说1.8不用重新计算hash值而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。 这一块就是JDK1.8新增的优化点。 有一点注意区别,JDK1.7中rehash的时候,旧链表迁移新链表的时候,如果在新表的数组索引位置相同,则链表元素会倒置,因为他采用的是头插法,先拿出旧链表头元素。 但是从下图可以看出,JDK1.8不会倒置,采用的尾插法。

详解并发下的HashMap以及JDK8的优化

为什么 HashMap中 String、Integer 这样的包装类适合作为 key键?

详解并发下的HashMap以及JDK8的优化

HashMap中的key如果是Object类型,则需实现哪些方法?

详解并发下的HashMap以及JDK8的优化

查看原文: 详解并发下的HashMap以及JDK8的优化

  • bigbird
  • yellowlion
  • smallpanda
  • greenlion
  • smallcat
  • whitelion
  • bigsnake
  • bluekoala
  • ANDY 君朋
需要 登录 后回复方可回复, 如果你还没有账号你可以 注册 一个帐号。