Shulou(Shulou.com)06/02 Report--

This article mainly introduces "how to understand and master HashMap". In daily operation, I believe many people have doubts about how to understand and master HashMap. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts of "how to understand and master HashMap"! Next, please follow the editor to study!

Data structure

In JDK1.8, HashMap is made up of array + linked list + red-black tree (1.7 version is array + linked list)

When a value is to be stored in HashMap, its hash is calculated based on the value of Key, and the location in the array is confirmed by the hash value. If a hash conflict occurs, it is stored as a linked list. If the linked list is too long, HashMap will convert the linked list into a red-black tree for storage, as shown in the figure:

Before we look at the source code, we need to look at some basic attributes.

/ / the default initial capacity is 16 static final int DEFAULT_INITIAL_CAPACITY = 1 return o! = null? O.hashCode (): 0;} public final V setValue (V newValue) {V oldValue = value; value = newValue; return oldValue;} public final boolean equals (Object o) {if (o = = this) return true; if (o instanceof Map.Entry) {Map.Entry e = (Map.Entry) o / / Objects.equals (1a.equals b)-> return (a = = b) | | (a! = null & & a.equals (b)); if (Objects.equals (key, e.getKey ()) & & Objects.equals (value, e.getValue ()) return true;} return false;}}

Summary

Default initial capacity is 16, default load factor is 0.75

Threshold = array length * loadFactor. When the number of elements exceeds threshold (capacity threshold), HashMap will expand the capacity.

The table array holds references to linked lists

One thing to note here is that the table array is not initialized in the constructor, it is initialized in the resize (expansion) method.

The length of the table array is always the power of 2.

It is well known that the length of the HashMap array is always the power of 2 (referring to the size of the table array). Have you ever wondered why?

First, we need to know that HashMap ensures that the length of the HashMap array is always to the power of 2 through a method called tableSizeFor. The source code is as follows:

/ * find a power greater than or equal to the minimum 2 of cap and use it as the capacity threshold * / static final int tableSizeFor (int cap) {int n = cap-1; n | = n > 1; n | = n > 2; n | = n > 4; n | = n > 8; n | = n > 16; return (n)

= MAXIMUM_CAPACITY)? MAXIMUM_CAPACITY: n + 1;}

The function of tableSizeFor (regardless of cases greater than the maximum capacity) is to return a number greater than or equal to the input parameter and the nearest integer power of 2. For example, 10 returns 16.

The algorithm changes all the bits after the highest bit 1 to 1. Finally, let the result n = 1, that is, you get the value of the integer power of 2.

The purpose of having cap-1 assign to n is to find another target value that is greater than or equal to the original value. For example, binary 1000, the decimal value is 8. If you operate directly without subtracting 1 from it, you will get the answer 10000, or 16. It's obviously not the result. Minus 1, the binary is 111, and then you get the original value of 1000, that is, 8. The efficiency is greatly improved through a series of bit operations.

So where can I use the tableSizeFor method?

The answer is to call this method in the constructor to set the threshold, which is the capacity threshold.

Here you may have another question: why set it to threshold?

This is because the length of the table array will be set when the threshold is initialized for the first time in the expansion method, which will be described later when we talk about the expansion method.

/ * input initial capacity and load factor * / public HashMap (int initialCapacity, float loadFactor) {if (initialCapacity)

MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.