假设我们自己实现一个HashMap遇到扩容问题，即原有数组已经满了或者快满了(专业点，就是填充数据的比例已经超过loadFactory)；扩充存储数据的数组后怎么迁移原来的数据？
直接的思路就是遍历所有已经填充的数据；计算key的hashcode跟新的数组size取余；确定新位置一个一个放进去；
这基本就是JDK1.7 中HasmMap的扩容实现思路；
在 JDK1.7 中，HashMap 整个扩容过程就是分别取出数组元素，一般该元素是最后一个放入链表中的元素，然后遍历以该元素为头的单向链表元素，依据每个被遍历元素的 hash 值计算其在新数组中的下标，然后进行交换。这样的扩容方式会将原来哈希冲突的单向链表尾部变成扩容后单向链表的头部。
JDK1.8中，HashMap对扩容操作做了优化。
我们从源码可以看到，循环Node数组时，如果某个节点有值且并没有Hash冲突的时候，直接重新hash；如果是红黑树(TreeNode)的时候，调用了TreeNode的split方法（此处暂且按下不表）；
如果都不是（那就是链表了），将当前j位置的链表分割成loHead和hiHead两个链表，然后将loHead放在新数组的j位置，将hiHead放在新数组的 j + oldCap 位置，此处oldCap为原数组的大小。
...
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
...
我们看到，判断数据放到loHead 还是 hiHead的依据是 if ((e.hash & oldCap) == 0) 即key的hash值和 原有数组容量的 & 操作结果。
此处怎么理解？
-
为什么原数组j位置的链表可以拆分为loHead和hiHead两个链表，并且是放到新数组j 和 j + oldCap位置？
首先，JDK8中存储数据的数组长度总是2的N次方，因此扩容前后数组的长度是 2 倍关系；
其次，key的hash值映射到存储数组的下标是通过取余操作完成，举例来说，如果一个key的最终hash值为123，当前存储数组大小为16，那么该key存储在 123% 16 = 11 这个下标；
这样我们来设想下存储数组大小从16扩容到32，原有数组下标11里面的所有key，可能会被移动到新数组的哪个位置？
很容易可以证明，它只可能在新数组的 11 或者 11 + 16 的位置上( hashCode = 11 + N * 16，N为偶数，仍然在11，N为奇数则在 11+16位置上 )；
这就是为什么原来的链表需要且只需要拆分为loHead和hiHead两个链表，并且放到新数组j 和 j + oldCap位置的原因 -
为什么可以根据条件
if ((e.hash & oldCap) == 0)来判断数据放到loHead 还是 hiHead？
loHead会放到新数组的j位置，hiHead会放到新数组的j + oldCap位置；所以问题其实是一个hash值，在对oldCap求余得到j，如何快速判断该hash值对 newCap求余数会得到 j还是 j + oldCap？
我们从二进制的表示形式直观看该问题；以hash值 123为例，原数组大小(oldCap)为16，新数组大小(newCap)为32；
image.png
从上式看出，
首先 > newCap 的高位对取余没有任何影响，因为它都会被newCap和oldCap整除掉
其次 < oldCap的低位就是对oldCap取余的结果，而hash值对newCap和oldCap取余结果是否一致完全取决于该值在oldCap位上是0还是1；
如果是0，则hash值对newCap和oldCap取余结果一致
如果是1，则hash值对newCap和oldCap取余结果为原值 + oldCap
这就是条件 if ((e.hash & oldCap) == 0) 的原因
使用该方法判断的好处就是计算快速，只需要一次&操作。
网友评论