如果 HashMap 的 table 长度为 M，全部存储的键值对数量为 N，如果哈希函数满足均匀性的要求，那么每条链表的长度大约为 N/M，因此平均查找次数的复杂度为 O(N/M)。
为了让提高查找效率，需要降低每条链表的长度，也就是说 table 要尽可能大。HashMap 采用动态扩容来根据当前的 N 值来调整 M 值，使得空间效率和时间效率都能得到保证。
关于JAVA7中的扩容机制不了解的 大家可以先参考这篇文章# 博客园java容器03--HashMap源码分析
JAVA7扩容后的rehash过程使用了单链表的头插法方式，同一位置上新元素总会被放在链表的头部位置；这样如果发生了hash冲突的话先放在一个索引上的元素终会被放到Entry链的尾部，这一点和JAVA8有区别。
JAVA8在rehash算法利用了下面的一个特性：
HashMap的扩容使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。什么意思呢？ 我们举个例子说明。
假设原数组长度 capacity 为 16，扩容之后 new capacity 为 32：
old capacity : 00010000
new capacity : 00100000
根据HashMap如何计算Entry在桶中的下标？一文中，
下标的计算方法，对于一个 Key，如原Hash值 key1 = 0001 1001 key2 = 0000 1001
扩容前 hash & (length - 1) :
key1 : 0001 1001 & 0000 1111 -> 0000 1001
key2 : 0000 1001 & 0000 1111 -> 0000 1001
扩容后 hash & (length - 1) :
key1 : 0001 1001 & 0001 1111 -> 0001 1001
key2 : 0000 1001 & 0001 1111 -> 0000 1001
因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，
**只需要看原来的hash值在扩容后新增的那一位是1还是0，如果是0的话索引没变，是1的话索引变成“原索引+oldCap” 。
在JAVA8代码中，抽象为一行if判断代码 ：
if ((e.hash & oldCap) == 0）
即如果位与原来的capacity结果为0 则代表hash值新增的高位为0。
jdk1.8 hashMap扩容例图.png
这种算法既省去了重新计算hash值的时间，而且新增的1位是0还是1机会是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。
这就是JAVA8新增的优化点：
在JAVA7中rehash旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，而在JAVA8中不会倒置。
参考：
http://www.importnew.com/20386.html
https://www.cnblogs.com/csslcww/p/9611568.html
网友评论