本文主要是介绍HashMap扩容时的rehash方法中(e.hash oldCap) == 0算法推导，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
PS:由于文档是我在本地编写好之后再复制过来的，有些文本格式没能完整的体现，故提供下述图片，供大家阅览，以便有更好的阅读体验：
HashMap在扩容时，需要先创建一个新数组,然后再将旧数组中的数据转移到新数组上来
此时，旧数组上的数据就会根据(e.hash & oldCap) 是否等于0这个算法,被很巧妙地分为2类:
① 等于0时，则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置,记为低位区链表lo开头-low;
② 不等于0时,则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置再加上旧数组长度，记为高位区链表hi开头high.
具体,详见下述的算法推导解析:
算法：
(e.hash & oldCap)=0
前提：
e.hash代表的是旧数组中节点或元素或数据e的hash值，该hash值是根据key确定过的：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16) ；
oldCap为旧数组的数组长度，是2的n次幂的整数。即e.hash&2^n=0
推导过程1(e.hash & oldCap)=0：
- 因为oldCap是2的n次幂的整数,其二进制表达为1个1后面跟n个0：1000…0，若想要e.hash&oldCap的结果为0，则e.hash的二进制形式中与对应oldCap的二进制的1的位置一定为0，其他位置的可以随意，这样即可保证结果为0；
- 假设：
oldCap= 2 ^ 3 =8 = 1000
则e.hash可以是 0101
e.hash&oldCap 0000=0
3. (2oldCap -1)=2 ^ 4-1=01111，其二进制位数比oldCap多一位，但多的这一位是0,其余都是1(其低三位肯定也是1);(oldCap-1)=2 ^ 3-1=0111，其二进制位数与oldCap相同,且其低3位的值都是1。故(2oldCap-1)和(oldCap -1)两者与只有4位且首位为0的e.hash=0101计算时，其实只有低3位真正能影响计算结果，而两者的低3位相同，都是111；
4. 故在前提条件下，(2oldCap-1)和(oldCap -1)两者与e.hash进行&运算之后的结果一样：
(2oldCap -1)=2 ^ 4-1= 01111 (oldCap-1)=2 ^ 3-1= 0111
e.hash 0101 e.hash 0101
e.hash&oldCap 00101=5 e.hash&oldCap 0101=5
5. 而(oldCap -1) &e.hash恰巧代表的就是e元素在旧数组中的索引位置；
而(2oldCap -1) &e.hash则代表的就是e元素在旧数组长度扩容2倍后的新数组里的索引位置
6. 综上，可得出满足e.hash&oldCap=0的元素，其在新旧数组中的索引位置不变；
推导过程2(e.hash & oldCap)不等于0：
- 因为oldCap是2的n次幂的整数,其二进制表达为1个1后面跟n个0：1000…0，若想要e.hash&oldCap的结果不为0，则e.hash的二进制形式中与对应oldCap的二进制的1的位置一定不为0，其他位置的可以随意，这样即可保证结果不为0；
- 假设：
oldCap= 2 ^ 3 =8 = 1000
则e.hash可以是 1101
e.hash&oldCap 1000=13
3. (2oldCap -1)=2 ^ 4-1=01111,其二进制位数比oldCap多一位,但多的这一位是0,其余都是1(其低三位肯定也是1,其从左到右数的第4位为1);(oldCap-1)=2 ^ 3-1=0111,其二进制位数与oldCap相同,且其低3位的值都是1, 其从左到右数的第4位为0,。故(2oldCap-1)和(oldCap -1)两者与只有4位且首位为1的e.hash=1101计算时,其实也只有从左到右数的第4位(0)真正能影响计算结果,因为低3位完全一样都是1;
4. 故在前提条件下，(2oldCap-1)和(oldCap -1)两者与e.hash进行&运算后结果相差了oldCap：
(2oldCap -1)=2^4-1= 01111 ( oldCap - 1 ) =2 ^ 3-1= 0111
e.hash 1101 e.hash 1101
(2oldCap -1)& e.hash 01101=8+5 (2oldCap -1)&e.hash 0101=5
5. 而(oldCap -1) &e.hash恰巧代表的就是e元素在旧数组中的索引位置；
而(2oldCap -1) &e.hash则代表的就是e元素在旧数组长度扩容2倍后的新数组里的索引位置
6. 综上，可得出满足e.hash&oldCap不等于0的元素，其在新数组中的索引位置是其在旧数组中索引位置的基础上再加上旧数组长度个偏移量。
这篇关于HashMap扩容时的rehash方法中(e.hash oldCap) == 0算法推导的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
