This article has participated in the activity of “New person creation Ceremony”, and started the road of digging gold creation together.

✨ I am YuShiwen who likes to share knowledge and blog. Learn and grow together with you! 📢 smell have successively, learned is own, everybody refuels! 📢 guide: the article is not long, after reading, I believe you will gain, this article and the general interview article is not the same, this article knowledge is more detailed, deeper, directly to the hardware layer, further broaden the reader's understanding of the computer, and also strive to know why!Copy the code

1. Why is expansion in HashMap 2 to the NTH power

A:

  1. When expanding, move the array length of the current hash table to the left by 2.
  2. When we calculate the index of an array, we use 2 to the NTH power.





2. How to use 2 to the NTH power?

A: When calculating the array subscript, subtract 1 from the array length in the Hash table, and then perform a bitwise ampersand (&) operation on the Hash value of the key.

I = (n – 1) & hash; Where I is the subscript of the TAB array, n is the length of the array in the Hash table, and Hash is the value of the key computed by the hashCode method.





3. What happens if it’s not 2 to the NTH power?

A: Let’s use the inverse method to prove what happens if it’s not 2 to the NTH power. Here’s what happens:

I = (n – 1) & hash; Where I is the subscript of the TAB array, n is the length of the array in the Hash table, and Hash is the value of the key computed by the hashCode method.

For example, the initial length is 16 when it is 2 to the NTH power. For example, if it is not 2 to the NTH power, the initial length is 13. Then the above code will appear: (Note :int has 32 bits. To save space, I only write the lower 8 bits. The remaining 24 bits are all zeros.)

  1. First, the binary bit of 13 is 0000 1101;
  2. Execute n-1, the binary result is 0000 1100;
  3. The result 0000 1100 and any hash operation, the first and second bits of the value are always 0, that is, the resulting value can only be: 0000 0000 0100 0000 1000 0000 1100

Initialize the hash table array with bit 13 in length, where only the indexes 0, 4, 8, and 12 can store values, and the indexes 1, 2, 3, 5, 6, 7, 9, 10, and 11 are not used, as shown in the following figure:This will greatly increase the probability that the nodes will become extremely long linked lists, resulting in long queries later.

If it is 2 to the NTH power, again we do the three steps above:

  1. First, the binary bit of 16 0001 0000;
  2. Execute n-1, the binary result is 0000 1111;
  3. The result, 0000 1111, is an & with any hash, resulting in values ranging from 0 to 15, covering the entire array.

The graph becomes the following:





4. In 2 you mentioned the ampersand operation. Why not replace the ampersand operation with the mod or mod operation in the HashMap source code?

A: Because the result of the mod or mod calculation is negative, the most important thing is that the mod or mod operation is not as fast as the &(and) operation.





5. Why is the result of mod or mod negative? Why is the mod or mod operation not faster than the &(and) operation?

Inner activity: the questioner has been asking this question, and all ask so low level, here can not simply answer a sentence, want to test my low level of skills, then listen to me slowly.

5.1 The reasons for negative results of mod or mod calculation are as follows:

There is a difference between floorMod and floorMod. FloorMod is defined in Java as follows:

Because the mod operation is the operator %, Java can not see the source code, the author refers to the definition of the mod in mathematics, the general content is as follows:

public static int fixMod(int x, int y){
	int r = x - fixDiv(x,y)*y;
	return r;
}
Copy the code

FloorMod calls the floorDiv method, and fixMod calls the fixDiv method. Both the floorDiv method and fixDiv are quotient operations. FloorDiv is rounded towards negative infinity and fixDiv is rounded towards 0:

  • When the number is positive, such as 3/5, the floorDiv and fixDiv values are the same, 0.
  • When it is negative, such as -3/5, floorDiv rounding negative infinity is -1 and fixDiv rounding zero is 0.

The summary is:

  1. Mod, following the principle of keeping quotient, the fixDiv method, as close to zero as possible;
  2. Modules are taken in accordance with the principle of making the quotient, i.e. floorDiv method, as close to negative infinity as possible

That’s one of the differences between mod and mod operations. Now let’s look at another difference, and this one is important. Let’s look at an example:The above example code is as follows, you can copy and paste to run the kangkang:

println "The modulo operation of 5 and 3 is:"+Math.floorMod(5.3);
println "Mod 5,3 is:"+5%3;
println "";
println "-5,-3 modulus operation is:"+Math.floorMod(- 5.- 3);
println The mod of -5 and -3 is:+ (- 5%- 3);
println "";
println "5,-3 modulus calculation is:"+Math.floorMod(5.- 3);
println "Mod 5,-3 is:"+ (5%- 3);
println "";
println "-5,3 modulus operation is:"+Math.floorMod(- 5.3);
println "-5, mod 3 is:"+ (- 5%3);

Copy the code

The running results are as follows:There are the following situations:

  • When the divisor and dividend sign are the same, the result is the same.
  • When the divisor and dividend sign are different, the following two situations occur:
    1. The symbol and divisor of the operation result are the same.
    2. For the mod operation, the result has the same sign as the dividend.

As can be seen from the above, when the divisor or dividend is negative, the result may also be negative.

5.2 The reasons why the operation of mod or mod is not as fast as &(and) are as follows:

Ordinary calculators add, subtract, multiply and divide by hardware logic:

Mathematically, the ALU in the CPU does only three things arithmetically, addition, shift, and inversion; In the actual physical circuit, there are only and, or, non, xOR gate circuit; With these two points in mind, let’s analyze addition, subtraction, multiplication and division:

  1. Addition: logical xor operation, that is, 0 and 0 and 1 and 1 are 0, 0 and 1 and 1 are 1, get the value of the standard sum, according to the operation requirements, determine whether to carry;
  2. Subtraction: there is no subtraction for the computer, subtraction is to take a number as a negative number, and then in the computer with the complement code stored (that is, the original code take negative plus 1), and then the implementation of addition operation; (Addition is also calculated using the complement.)
  3. Multiplication: shift, logical judgment, accumulation;
  4. Division: shift, logical judgment, reduction.

The 2-bit adder gate circuit is roughly as follows :(here is a two-bit adder for example, in reality, more of these gates can be composed of more bit adder) The circuit diagram of the multiplier gate is as follows. The multiplier consists of an adder and an and gate (again, only 2-bit * 2-bit multiplication is cited here. The higher gate circuit is more complex, but the basic way of implementation remains unchanged).

From the hardware implementation, it can be seen that the realization of these four basic operations only need adder, shifter and basic logic gate hardware components. Early CPUS were simple, with only these components and no special multipliers or dividers. Later cpus integrated specialized parallel processing circuits into the CPU’s built-in coprocessors (such as floating-point arithmetic units), which were implemented in hardware to make computation faster. Of course, the logic of the calculation remains the same.

As mentioned in section 3.1 above, mod fetching operations are as follows (mod fetching operations are similar) :

r=x-floorDiv(x,y)*y
Copy the code

In this relation, fixMod is quotient operation, quotient operation involves the division operation, the resulting quotient is multiplied by y, above we said: multiplication can be broken down into: shift, logical judgment, sum; Division can be divided into: shift, logical judgment, and reduction. As you can see, the underlying implementation of multiplication and division is the shift operation and the accumulation operation, plus some logical judgment, which is much less efficient than the ampersand (and) operation, and only requires an and gate logic circuit to compute.





Appendix: Look at the source code with the author

Test code (JDK1.8) : Create a HashMap, this time empty, first we insert into the HashMap key= “name”, value= “YuShiwen” key value pairs.In the follow up code, the putVal() method in HashMap is calledFollow up putVal method:

  1. The Hash table is empty at the beginning, that is, the TAB is null. Enter the if statement and call resize() to initialize the Hash table. (ps: the resize() method will be called during initialization or expansion, and the expansion method will be moved one bit to the left, that is, the original size multiplied by 2)
  2. Second screenshot: The first time, the resize() method returns the default size of 16.

After putVal returns the default value of 16, we continue. We all know that the underlying implementation of HashMap is array + linked list, which is the structure shown in the first image;) Then we get an if statement, which evaluates the array subscript. That is, we subtract 1 from the array in the Hash table, and then perform a bitwise and (&) operation on the Hash value of the key.

I am YuShiwen who likes to share knowledge and blog. Learn and grow together with you! See you in our next post.