Detailed analysis of HashMap source code (JDK1.8)

3. Variable definition

The above defines some variables that will be used. It's good to be familiar with them.

3.1 transient

Here, careful partners will find that the bucket array table is declared transient. Transient means changeable. In Java, variables modified by this keyword will not be serialized by the default serialization mechanism.

Consider a question: the bucket array table is an important data structure at the bottom of HashMap. How can others restore it if it is not serialized?

Instead of using the default serialization mechanism, HashMap customizes the serialization content by implementing the readObject / writeobject methods. The content stored in the HashMap is a key value pair. As long as the key value pair is serialized, the HashMap can be reconstructed according to the key value pair data.

Some people may think that serializing a table can be done in one step, and then it can be restored directly? However, there are two problems with serializing tables:

Of the above two questions, the first one is easy to understand and the second one is easy to explain. The first step of HashMap's get / put / remove and other methods is to find the bucket position of the key according to the hash. However, if the key does not override the hashcode method, the hashcode method in the object will be called when calculating the hash. However, the hashcode method in object is native. Different JVMs may have different implementations, and the generated hash may also be different. In other words, the same key may generate different hashes on different platforms. At this time, if you continue to operate on the same table, there will be a problem.

3.2 LoadFactor

4. Constructor

6. Add element

6.1 putmapentries adding map objects

This method directly passes in a map object in the constructor. See the specific implementation code below:

It is mainly to judge whether some initialization work has been done, including capacity and table, and then add the data to the map after ensuring that they can be used. Traversal is used here, which is also briefly described here. It can be found that the table here is null and does not start assignment, but the threshold is calculated. Will be initialized in putval.

6.2 traversal

Like search, traversal is also an operation used frequently by everyone. For traversing HashMap, we generally use the following methods:

Either get the keyset to traverse, or get the entryset. Finally, you can also use the iterator. See the following figure for the specific traversal process:

The final result of traversing the above figure is 19 - > 3 - > 35 - > 7 - > 11 - > 43 - > 59. During initialization, hashiterator will first traverse the bucket array and find the bucket containing the reference of the linked list node. The corresponding figure is bucket 3. Then, the nextnode method traverses the linked list pointed to by the bucket. After traversing bucket 3, the nextnode method continues to find the next bucket that is not empty, corresponding to bucket 7 in the figure. After that, the process is similar to the above until the last bucket is traversed.

6.3 adding elements

Here's how to add a new element:

Through the above source code, we can see. When adding a new node, its location is determined by hash.

The search process is to first determine its index:

Here, the position of the bucket in the bucket array can be calculated through (n - 1) & hash. Some friends may not understand why they do this. Here is a brief explanation. The size length of bucket array in HashMap is always a power of 2. In this case, (n - 1) & hash is equivalent to taking the remainder of length. However, the computational efficiency of remainder is not as high as that of bit operation, so (n - 1) & hash is also a small optimization. For example, suppose hash = 185 and N = 16. The calculation process is shown as follows:

The above calculation is not complicated, so I won't say more here. The hash value here is key Hashcode(). However, in HashMap, the hash value is recalculated through bit operation. Why recalculate?

In Java, the length of the array is fixed, which means that the array can only store a fixed amount of data. But in the process of development, many times we can't know how large an array should be built. Small buildings are not enough, and large ones are not enough, resulting in waste. If only we could implement a variable length array and allocate space as needed. Fortunately, we do not need to implement variable length arrays ourselves. The Java collection framework has implemented variable length data structures. Such as ArrayList and HashMap. For this kind of variable length data structure based on array, capacity expansion is a very important operation.

First, resize (), let's see which functions call resize (), so we have a concept as a whole: