[introduction to Java] day23 Java container class (VI) HashMap source code analysis (middle)

In the previous article, the basic contents of HashMap were introduced in detail, and the get and put methods were analyzed. Presumably, we also have a better understanding of HashMap. This article will analyze those functions in HashMap from the perspective of algorithm.

HashCode

Let's talk about the hashcode algorithm in HashMap. In the previous article, we saw that the put method in HashMap is as follows:

What is the hash function? Let's see what it really is:

It can be seen that the hashcode of the key is not simply used here, but an XOR operation is performed on its high 16 bits and low 16 bits. ("> > >" means to move right without sign, that is, when moving right, the left part is filled with 0). This is a disturbance function, and the specific effects will be described later. Next, let's look at the previous putval method:

Notice the code on line 8:

　　tab[i = (n - 1) & hash]

(n - 1) & hash is to get the corresponding array subscript through the hash value of the key, not the remainder of the size of the table.

So why? Firstly, the purpose of the perturbation function is to expand the influence of the high bit, so that the calculated value contains the characteristics of the high 16 bit and the 16th bit, making the hash value more unfathomable

N is the size of the table. By default, it is 16, the binary is 10000, and the binary corresponding to N - 1 is 1111. In this way, when performing an "and" operation with the hash value, it becomes a mask, except that the last four bits are all set to 0, and the range of the last four bits will certainly fall between (0 ~ n-1), which is exactly the size range of the array. That's the beauty of the hash function.

Then, let's continue the chestnuts in the previous article. Let's analyze the mapping process of hash values of Xiao Ming and Xiao Li step by step:

Xiaoming's hash value is 756692, which is converted to binary 10111000101111010100. The size of table is 32, n-1 = 31, and the corresponding binary is 11111. After the "and" operation, the result is 10100, that is, 20.

Xiao Li's hash value is 757012, which is converted to binary 101110001100010100. After the sum operation with 11111, the result is 10100, that is, 20. Therefore, there is a conflict with Xiao Ming, but it still needs to come first, so Xiao Li hangs behind Xiao Ming.

After reading the hash function, let's look at the expansion function.

Expansion function

In fact, we have seen the capacity expansion function before. In the putval method above, turn it over and you can see the resize function in the sixth line. This is the capacity expansion function. Let's take a look at its true face:

It can be seen here that if the original table has not been initialized, it will be expanded to the default size (16) after calling the function. As mentioned in the previous article, HashMap also uses lazy loading. Instead of initializing the table in the constructor, it is delayed until the first element is inserted.

When using put to insert elements, if it is found that the current bin occupancy has exceeded the proportion set by the load factor, resize will occur. In short, adjust the original capacity and threshold to twice the original, recalculate the index, and put the node into the new bin. Because the calculation of index value is related to the size of table array, the position of elements may be adjusted after capacity expansion:

As an example, if the fifth bit of the corresponding hash value is 0, the sequence number obtained will not change after the and operation, and its position will not change. On the contrary, if it is 1, its new sequence number will become the original sequence number + 16,.

It doesn't seem that there are many. Well, the algorithm part will be introduced here first. In the next article, we will talk about entryset, keyset and values in HashMap (by the way, the iterator if time is enough).

Well, this article ends happily. Finally, I wish you a happy Dragon Boat Festival! If you think the content is good, remember to use your hands and pay attention. Your support is my biggest motivation!