Analysis of HashMap usage from the perspective of Java source code

―HashMap―

Advantages: super fast query speed and time complexity can reach o (1). The data structure is HashMap. Dynamic variable length storage data (relative to array).

Disadvantages: the hash value needs to be calculated once. If it is not handled properly, it will occupy additional space.

- how to use HashMap -

We usually use HashMap as follows

The above code creates a new HashMap and inserts two data. The basic data types are not accepted for K and V

If you write this, there will be a problem:

Why should we use it like this? See the source code:

This is the definition of the HashMap implementation class.

- HashMap is a dynamic variable length data structure -

When using HashMap, in order to improve the execution efficiency, we often set the HashMap initialization capacity:

Or use guava's tool class maps to easily create a collection with an appropriate size initialization value.

So why use it like this? Let's look at their source constructor.

Constructor without parameters:

public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); }

Explanation of terms:

So we know that if we call the parameterless constructor, we will get a 16 capacity array.

So the question arises: what if the initial capacity is not enough?

The array is of fixed length. How to use a fixed length data to represent an indefinite length data? The answer is to find a longer one, but it will reduce the efficiency when resizing. Therefore, we suggest that a reliable capacity should be given during the initialization of HashMap.

- put method of HashMap -

If the inserted data exceeds the existing capacity, it will be executed

It is shown here that if the current size + + > threshold, it will expand twice the current size and execute resize (2 * table. Length). How do they expand?

How is the transfer array transferred?

- additional execution times of HashMap expansion -

So if we want to add a HashMap with 1000 elements, how many additional calculations do we need if we use the default value

When it is greater than 16 * 0.75 = 12, it needs to be calculated 12 times again

When it is greater than 16 * 2 * 0.75 = 24, 24 additional calculations are required

……

When it is greater than 16 * n * 0.75 = 768, 768 additional calculations are required

Therefore, we calculate 12 + 24 + 48 +... + 768 times in the expansion process

Therefore, it is strongly recommended that if we know the range in the project, we should manually specify the initial size, such as:

Conclusion: This is the reason why the execution efficiency of HashMap decreases seriously when it exceeds the initial capacity.

The above is all about analyzing the usage of HashMap from the perspective of Java source code. I hope it will be helpful to you. Interested friends can continue to refer to other related topics on this site. If there are deficiencies, please leave a message to point out. Thank you for your support!