Shulou(Shulou.com)06/01 Report--

This article shows you why the length of HashMap is the power of 2. It is concise and easy to understand. It will definitely brighten your eyes. I hope you can get something through the detailed introduction of this article.

In order to make HashMap access efficient, there are as few collisions as possible, that is, data should be distributed evenly. As we have mentioned above, the range of Hash values is-2147483648 to 2147483647, adding up to about 4 billion of the mapping space. As long as the hash function is mapped uniformly and loosely, it is difficult to collide in general applications. But the problem is that there is no room for memory in an array of 4 billion lengths. So this hash value cannot be used directly. Before using it, we should also do the modular operation of the length of the array, and the remainder can be used for the location to be stored, that is, the corresponding array subscript. The array subscript is calculated as "(n-1) & hash". (n represents the array length). This explains why the length of HashMap is to the power of 2.

How should this algorithm be designed?

We may first think of using the% remainder operation to achieve this. However, the point is: "in the remainder (%) operation, if the divisor is the power of 2, it is equivalent to the and (&) operation with its divisor minus one (that is, hash%length==hash& (length-1) if length is to the n power of 2;)." And the use of binary operation & relative to% can improve the computational efficiency, which explains why the length of HashMap is the power of 2.

The above is why the length of HashMap is the power of 2. Have you learned any knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.