e. Hash & oldcap = = 0 detailed interpretation

e.hash & oldCap == 0 Detailed interpretation

Press (e.hash & oldCap) Is it equal to 0 There are two situations ( In the process of derivation, always pay attention to ： The array length before and after the expansion is 2 Of n The next power , This is HashMap Specified by the underlying source code )：

situation 1：【 Derivation process 1】 When e.hash&oldCap be equal to 0 when ,e The index position in the old and new arrays remains the same ：(2oldCap-1)& e.hash = (oldCap -1) & e.hash

situation 2：【 Derivation process 2】 When e.hash&oldCap It's not equal to 0 The elements of ,e The index position in the new array is its index position in the old array plus the length offset of the old array : (2oldCap-1)& e.hash = (oldCap -1) &e.hash+oldCap

oldCap yes table The capacity of , Follow the strategy of the source code , It must be 2^n Power , It means that 2 There must be only one base 1, The rest are 0; If you want to guarantee e.hash&oldCap ==0, You just need to e.hash In the corresponding oldCap The binary bits are in 1 The one who is 0, You can guarantee the final biting and operation (&) The result is 0; If e.hash&oldCap !=0 , You just need to e.hash In the corresponding oldCap The binary bits are in 1 The one who is 1, You can guarantee the final bitwise and operation （&） It's not equal to 0

hypothesis oldCap = 16 = 2^4 = 10000（ Binary system ）

Derivation process 1：

Want to satisfy e.hash&oldCap ==0, hypothesis e.hash = 01111 ( Be careful , there e.hash After the initial hash(key) Calculated ), Pay attention to this 01111 in 0 The position of is corresponding to oldCap The only one in the binary system 1 The location of )

10000 & 01111

be oldCap & e.hash = 10000 & 01111 = 00000( Binary system ) = 0（ Decimal system ）

When adding elements , This calculation method is used to find the corresponding subscript in the array for the element to be added

Now we have doubled the capacity of the array , The formula must be modified

（2oldCap-1）& e.hash = （2^5 - 1）& 0 1111 = 01 1111 & 0 1111 = 00 0000（ Binary system ）= 0（ Decimal system ）

（oldCap -1）& e.hash = （2^4 - 1）& 0 1111 = 0 1111 & 0 1111 = 0 0000（ Binary system ） = 0 （ Decimal system ）

thus it can be seen , If meet e.hash&oldCap ==0 , The subscript position of the element in the old array is the same as that of the element in the new array

(e.hash & oldCap) == 0
if (loTail != null) {
    
    loTail.next = null;
    //  The subscript position of the element in the old array is the same as that of the element in the new array 
    newTab[j] = loHead;
}

Derivation process 2：

Want to satisfy e.hash&oldCap !=0, hypothesis e.hash = 11111( Be careful , there e.hash After the initial hash(key) Calculated ), Pay attention to this 11111 First of all 1 The position of is corresponding to oldCap The only one in the binary system 1 The location of )

10000 & 11111

be oldCap & e.hash = 1 0000 & 1 1111 = 1 0000 （ Binary system ） = 16（ Decimal system ）

When adding elements , Through this i = (n - 1) & hash Calculation method to find the corresponding subscript in the array for the element to be added

（2oldCap-1）& e.hash = （2^5 - 1）& 1 1111 = 01 1111 & 1 1111 = 0001 1111（ Binary system ）= 31（ Decimal system ）

（oldCap -1）& e.hash = （2^4 - 1）& 1 1111 = 0 1111 & 1 1111 = 0000 1111（ Binary system ） = 15 （ Decimal system ）

You can find （oldCap -1）& e.hash + oldCap = 15 + 16 = 31 = （2oldCap-1）& e.hash

thus it can be seen , If meet e.hash&oldCap != 0 , The subscript position of the element in the old array + Old array capacity = The position of the subscript of the element in the new array

e.hash & oldCap) == 0
if (hiTail != null) {
    
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

The above is only for personal interpretation , If there is any misunderstanding , Please comment in the comments section , thank you