Why is the premise of hash% length = = hash & (length-1) that length is the nth power of 2

Hash The range of values is -2147483648 To 2147483647, It's about 40 Billion mapping space , But we can't create one 40 Billion size array ,HashMap The default array size is 16.

So I'm getting Hash After the value, you need to remainder the length of the array , The remainder is at the index of the array .

So why do you say hash%length == hash&(length-1) The premise is length yes 2 Of n Power ？

From a binary point of view , Shift a number right 1 Bits are divided by 2, What its remaining binary numbers represent is to divide by 2 The result , Then the removed number is the remainder .
in other words , Shift a number right n position , Is to divide this number by 2 Of n Power , Removed n A digit is the remainder we want .

When the length of an array is 2 Of n In the second place , We let hash To make a surplus on it is to want hash On the far right n digit .
here , The length of the array is expressed in binary numbers 1 Follow behind n individual 0, If it is -1, That is to say length-1, At this time, the binary digital representation is that the front is 0, Follow behind n individual 1.
Then let's hash Follow length-1 Carry out bit and operation , And you get hash After n Bits are the remainder you want .

The reason why hash&(length-1) To get the rest , Instead of doing it directly hash%length The reason is ： Computing speed is faster , More efficient .

Reference resources ：
Java Gather common knowledge points & Interview question summary ( Next ) | JavaGuide
Binary bitwise AND & And remainder | Perkins4j2 Technology blog