static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0)?1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
Copy the code
/ / analysis
Int n = cap-1; The following algorithm is easier to understand after not analyzing it
1.n |= n >>> 1;  // Unsigned right shift n binary by 1 bit
// Set n = 9
0000 0000 0000 0000 0000 0000 0000 1001  = 9
// Unsigned move 1 bit to the right
0000 0000 0000 0000 0000 0000 0000 0100
// If one is one and none is zero
-----------------------------------------------
0000 0000 0000 0000 0000 0000 0000 1101= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =// Unsigned shift 2 bits to the right
0000 0000 0000 0000 0000 0000 0000 0011
// If one is one and none is zero
-----------------------------------------------
0000 0000 0000 0000 0000 0000 0000 1111= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =// Unsigned shift 4 bits to the right
0000 0000 0000 0000 0000 0000 0000 0000
// If one is one and none is zero
-----------------------------------------------
0000 0000 0000 0000 0000 0000 0000 1111= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =// Unsigned shift 8 bits to the right
0000 0000 0000 0000 0000 0000 0000 0000
// If one is one and none is zero
-----------------------------------------------
0000 0000 0000 0000 0000 0000 0000 1111= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =// Unsigned move 16 bits to the right
0000 0000 0000 0000 0000 0000 0000 0000
// If I have 1, I have 0
-----------------------------------------------
0000 0000 0000 0000 0000 0000 0000 1111
Copy the code

See any patterns? 1. The ultimate goal of unsigned right shift is to convert all 32 bits of binary n to 0:

0000 0000 0000 0000 0000 0000 0000 0000
Copy the code

The maximum value of Java int 0x7fffffff is unsigned to the right as shown above

0x7fffffff = 0111 1111 1111 1111 1111 1111 1111 1111
0111 1111 1111 1111 1111 1111 1111 1111
0011 1111 1111 1111 1111 1111 1111 1111 >>> 1
0000 1111 1111 1111 1111 1111 1111 1111 >>> 2
0000 0000 1111 1111 1111 1111 1111 1111 >>> 4
0000 0000 0000 0000 1111 1111 1111 1111 >>> 8
0000 0000 0000 0000 0000 0000 0000 0000 >>> 16
Copy the code

See, when we move to 16, all of them become zeros. We can also explain why it is 16 instead of 8 or 32. This is because Java ints are stored in 4 bytes 32 bits. Beyond that, there’s no point. 2. The ultimate purpose of xOR is to change the first 1 in the highest bit of the binary system into 1 after 0. Similarly, take the maximum value of int 0x7fffffff as an experiment

0111 1111 1111 1111 1111 1111 1111 1111
0011 1111 1111 1111 1111 1111 1111 1111 >>> 1
------------------------------------------------
0111 1111 1111 1111 1111 1111 1111 1111 | 
0000 1111 1111 1111 1111 1111 1111 1111 >>> 2
------------------------------------------------
0111 1111 1111 1111 1111 1111 1111 1111 | 
0000 0000 1111 1111 1111 1111 1111 1111 >>> 4
------------------------------------------------
0111 1111 1111 1111 1111 1111 1111 1111 | 
0000 0000 0000 0000 1111 1111 1111 1111 >>> 8
------------------------------------------------
0111 1111 1111 1111 1111 1111 1111 1111 | 
0000 0000 0000 0000 0000 0000 0000 0000 >>> 16
------------------------------------------------
0111 1111 1111 1111 1111 1111 1111 1111 | 
Copy the code

What you see or what you see is what it is all the time. So with all this talk, what will happen after this shift to the right + or? Take a look at

Incoming 1 = 1 incoming 2 = 2 incoming 3 = 4 incoming 4 = 4 incoming 5 = 8... Incoming 8 = 8 incoming 9 = 16... Incoming 16 = 16 incoming 17 = 32... We pass 32 = 32Copy the code

What that means is that whatever you pass in at the top will compute the first power of two greater than the value you pass in minus 1, 0, 1, 3, 7, 15, 31, 63, 127, 255… (Note: this is the operation above, not involving the +1 in the first line and the (n+1) in the following line) and then did it again

(n < 0)?1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
Copy the code

If n is less than 0, return 1. If n is greater than or equal to the maximum value of int, 0x7fffffff returns the maximum value of int. If n is greater than or equal to the maximum value of int, return n+1. This means that whatever initial value you pass in will eventually be replaced by the value calculated by the HashMap (2 to the NTH power). Let’s go back and see why we have int n = cap-1 in the first line; Through a series of instructions above we can find the result of calculation is calculated is greater than your incoming values of the first 2 to the power cut (note: the above two power minus 1 and the no 1 to distinguish, here is the final calculations), it was if your incoming number 2 NTH power such as 8 so if not minus 1 so calculated result is in the end

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1100 | 0000 0000 0000 0000 0000 0000 0000 0011 > > > 2 0000 0000 0000 0000 0000 0000 0000 1111 | 0000 0000 0000 0000 0000 0000 0000 0000 > > > 4 0000 0000 0000 0000 0000 0000 0000 1111 0000 0000 0000 0000 0000 0000 0000 0000 | > > > 8, 0000, 0000 0000 0000 0000 0000 0000 1111 0000 0000 0000 0000 0000 0000 0000 0000 | > > > 16 | 0000 0000 0000 0000 0000 0000 0000 1111Copy the code

The final result is 15 plus 1, which is 16, so if you want to create a HashMap of 8 and you get a HashMap of 16, you’re going to waste the rest, so you have to subtract 1 and 8 minus 1 is 7, and then you get n=7 plus 1 is 8. What if it’s 9? 9 minus 1 is 8 and then n is equal to 15 plus 1 is equal to 16 so it’s going to create 16 containers for you so that’s it, isn’t that amazing? With {} this method is only 9 lines of code but it takes a lot of text to analyze and describe and I don’t have to make it clear. So why do we use an exponential power of two as the initial value of the container? We’ll look at that next time when the container makes a good copy of the data, because that’s where it makes the best use of the algorithm. It’s only clear when it’s used.