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

全菜工程师小辉

发布于 2019-08-16 10:11:05

1K0

发布于 2019-08-16 10:11:05

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

HashMap在并发时出现的问题

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

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

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

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

单线程resize过程

首先我们把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;
}

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

Entry<K,V> next = e.next;// 因为是单链表，如果要转移头指针，一定要保存下一个结点，不然转移后链表就丢了
e.next = newTable[i];// e要插入到链表的头部，所以要先用e.next指向新的 Hash表第一个元素（为什么不加到新链表最后？因为复杂度是 O（N））
newTable[i] = e;// 现在新Hash表的头指针仍然指向e没转移前的第一个元素，所以需要将新Hash表的头指针指向e
e = next;// 转移e的下一个结点

并发时resize过程

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

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

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

线程一被调度回来执行。
1. 执行 newTalbe[i] = e。
2. 执行e = next，导致了e指向了key(7)。
3. 下一次循环的next = e.next导致了next指向了key(3)。

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

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

于是，当我们的线程一调用到，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计算和索引计算。

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就应该放在之前的位置再加上之前整个数组的长度的位置。这样子就减少了移动所有数据带来的消耗。（慢慢读两遍，想明白了，就觉得这个其实不看图更好理解）

常见FAQ

HashMap扩容条件

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

当前数据存储的数量（即size()）大小必须大于等于阈值
当前加入的数据是否发生了hash冲突

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

就是hashmap在存值的时候（默认大小为16，负载因子0.75，阈值12），可能达到最后存满16个值的时候，再存入第17个值才会发生扩容现象，因为前16个值，每个值在底层数组中分别占据一个位置，并没有发生hash碰撞。
当然也有可能存储更多值（超多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不会倒置，采用的尾插法。