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

This article mainly explains "how to understand HashMap". The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "how to understand HashMap".

1. What is the process of adding a key-value pair to HashMap?

This is a flow chart found on the Internet. You can look at the flow chart with the steps to understand the process of adding key-value pairs.

1. Initialize table

Determine whether table is empty or null, otherwise execute the resize () method (the resize method is usually called when the capacity is expanded, or it can be called to initialize the table).

two。 Calculate hash value

The hash value is calculated based on the key value key. (because hashCode is an int type variable, which is 4 bytes and 32 bits, we will perform an XOR operation between the low 16 bits and the high 16 bits of hashCode to retain the high bit characteristics so that the resulting hash values are more evenly distributed.)

3. Insert or update nodes

The inserted array subscript I is calculated according to (n-1) & hash, and then judged.

Table [I] = = null

If there are no hash conflicting elements under the current array subscript, just create a new node and add it.

Table [I]. Hash = = hash & & (table [I] = = key | | (key! = null & & key.equals (table [I] .key)

Determine whether the first element of table [I] is the same as key, and if so, update value directly.

Table [i] instanceof TreeNode

Determine whether table [I] is treeNode, that is, whether table [I] is a red-black tree, and if it is a red-black tree, insert key-value pairs directly into the tree.

Other circumstances

The above judgment conditions are not satisfied, indicating that table [I] stores a linked list, then traverse the linked list to determine whether the key of the existing element is equal to the key of the inserted key-value pair, if so, update the value, if not, insert a new node at the end of the linked list. After insertion, determine whether the length of the linked list is greater than 8, and convert the linked list to a red-black tree if it is greater than 8.

4. Expand capacity

After the insertion is successful, determine whether the actual number of key-value pairs size exceeds the maximum capacity threshold (usually array length * load factor 0.75). If so, expand the capacity.

The source code is as follows:

two。 Why is HashMap not thread-safe?

In fact, by learning the method of adding key-value pairs in HashMap, we can see that locks are not used in the whole method, so once multiple lines are accessed concurrently, it may cause data inconsistency.

For example:

If two threads that add key-value pairs execute the statement if ((tab = table) = = null | | (n = tab.length) = = 0) and both initialize the array of table variables, the already initialized array table will be overwritten, and then the previously initialized thread will add the key-value pair to the previously initialized array, resulting in the loss of the key-value pair.

3. Why override the hashCode () and equal () methods together?

Once our object is used as a key in HashMap or an element in HashSet, we must override both the hashCode () and equal () methods

First take a look at the default implementation of the hashCode () and equal () methods

You can see that the source code in the Obejct class is as follows, and you can see that the default implementation of the equals () method is to determine whether two objects have the same memory address to determine the return result.

Many blogs on the Internet say that the default implementation of hashCode is to return the memory address, but it is not true. Take OpenJDK as an example, there are five default calculation methods for hashCode, some return random numbers and some return memory addresses, which calculation method depends on the specific implementation of the runtime library and JVM.

Interested friends can read this blog blog.csdn.net/xusiwei1236.

Then look at the application of hashCode () method and equal () method in HashMap

In order to store a set of key-value pairs uniformly in an array, HashMap calculates the hashCode of key to get a hash value, takes the module of the array length with hash to get the array subscript, and stores the key-value pair under the linked list corresponding to the array subscript (assuming that the length of the linked list is less than 8 and does not reach the threshold for conversion to a red-black tree).

Here is the putVal () method to add key-value pairs, which executes when the array subscript corresponds to a linked list

You can clearly see that the main way to judge whether the added key is equal to the key already in the linked list is e.hash = = hash & & (k = e.key) = = key | | (key! = null & & key.equals (k)), that is: 1. First determine whether the hash value is equal, not equal directly end the judgment, because the hash value is not equal, key is definitely not equal. two。 Determines whether the memory addresses of two key objects are equal (equality points to the same object in memory). 3.key is not null, call the equal () method of key to determine whether it is equal, because it is possible that the two key store different addresses in memory, but are equal. Just like

Background

Suppose we have a KeyObject class, and suppose we think that the attributes an of two KeyObject are equal, then KeyObject is equal. We take KeyObject as the key of HashMap, and take the equality of KeyObject as the de-duplication criterion. We cannot repeatedly add the values of KeyObject equality and value equality to HashMap.

Assume that both the hashCode () method and the equals () method are not overridden (result: HashMap cannot guarantee deduplication)

Execute the following code:

If both the hashCode () method and the equals () method of KeyObject are not overridden, then even if the attribute an of KeyObject is 1 and the hashCode of key2 is different, key1 and key2 are not equal in calling the equals () method, so that both key1 and key2 can exist in hashMap.

Print the results:

If you only override the hashCode () method (result: the equality judgment cannot be made correctly with the linked list elements, so the de-duplication is not guaranteed)

Execute the following code:

At this point, the implementation of the equal () method is the default, that is, when the memory addresses of the two objects are equal, the equal () method returns true. Although the a property of key1 and key2 is the same, they are different objects in memory, so the key1==key2 result will be that the equals () method of false,KeyObject determines the memory addresses of the two objects by default, so key1.equals (key2) will also be false. So these two key-value pairs can be added to the hashMap repeatedly.

Output result:

If you only override the equals () method (result: mapping to a different array subscript in HashMap, no guarantee of deduplication)

Assuming only the equals () method, the hashCode method will be implemented by default, and the specific calculation method depends on the JVM. (when testing, it is found that the hashCode is different for objects with different memory addresses, so the calculated array subscript is different, which will be stored in the linked list under different arrays in hashMap, and will also lead to duplicate elements in HashMap.

The output is as follows:

Thank you for your reading, the above is the content of "how to understand HashMap", after the study of this article, I believe you have a deeper understanding of how to understand HashMap, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.