As many of you know, in JDK8, HashMap capacity is always 2 to the NTH power, so what is the purpose of this design? Can I change the default initial capacity from 16 to 20, and when I expand, can I change the capacity from twice to 3x or 1.5x?

So, with those questions in mind, let’s take a look.

Preliminary knowledge preparation

What is the ^

In Java, ^ is a bit operation called an or operation. It is a binary operation, the specific operation rules are: the same for 0, different for 1.

So let’s do an example

You compute 2^3.

First we convert 2 and 3 to binary representation as follows:

2 ——> 0010

3 ——> 0011

The result, according to the rules described above, is 0001, which in decimal form is 1.

How about that? Doesn’t that make sense.

What is a &

In Java, ampersand is also a bit operation called the and operation. It is a binary operation, the specific operation rule is: as long as one of the 0, 0.

So let’s do an example

Compute the result of 2 and 3.

First we convert 2 and 3 to binary representation as follows:

2 ——> 0010

3 ——> 0011

So according to the rules described above, the result is 0010, which in decimal form is 2.

What is > > >

In Java, >>> is called unsigned right shift. It is a kind of operation for binary, the specific operation rule is: ignore the sign bit, move n bits to the right, the vacancy is filled with 0.

So let’s do an example

Calculate the result of 16>>>2.

First we convert 16 to binary representation as follows:

16 – > 0001, 0000

So according to the rules described above, we need to move the binary number two places to the right, so that the space is filled with 0, so let me use a picture to illustrate;

As shown in the above, the red box is that we need the result, the first act, the original value of the secondary system, 16 representative of the second coming of the two moves to the right, find the last two 0 removed from the red box, they lack of two high, we according to the rules, filling them with 0, get the third row, then the third line represents the value of the data is 16 > > > the result of 2, We convert it to decimal, and the result is 4.

So 16>>>2 is 4.

So in Java, there are many similar bit operations, such as ^,&,<<,>>,<<<,>>, etc., interested students can baidu to learn.

The hash algorithm

So let’s move on to today’s topic, hash algorithms. Let’s first look at how the hash algorithm is implemented in a HashMap.

So, let’s break down the key parts of the code above. First, let’s take a look

h = key.hashCode()
Copy the code

There’s nothing special about this code, except to hash the key.

Now let’s look at the second piece of code,

h >>> 16
Copy the code

This code moves the hash value of the key 16 bits to the right, as we mentioned in the preparation above.

So on the whole,

(h = key.hashCode()) ^ (h >>> 16)
Copy the code

In this code, xOR operations are performed on the high and low 16 bits of the hash value of the key. In this way, the high and low 16 bits of the hash value can be used to ensure that the characteristics of each bit of the hash value are better preserved and hash conflicts are better reduced.

So why take ^ operations, rather than “& or | operation, so not is also can keep the characteristics of the high and low 16? You can think about it. If you have an idea, you can leave a comment below.

Now that we know the details of the hash algorithm in HashMap, do you have any ideas for the question at the beginning of this article? We will answer it in the next article.

Note: This article is based on JDK8.