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

Step-by-step analysis of the source code of the HashMap put method of the implementation process (jdk 1.8) example analysis, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain in detail for you, people with this need can come to learn, hope you can get something.

Preliminary knowledge

Note: we will not talk about what a red-black tree is and how to implement it. We just need to know what it looks like and understand its benefits.

Why use the data structure of array + linked list / red-black tree to store data in jdk1.8?

When the Hash conflict is serious, the linked list on the array will become longer and longer, which will reduce the efficiency of the query; the time complexity is O (N). After the introduction of red-black tree, the query efficiency is directly improved to O (logn).

What does the internal data structure of HashMap look like after the introduction of the red-black tree?

When will the linked list be used and when will the red-black tree be used?

When the size of the linked list is greater than the preset threshold (8), it is converted to a red-black tree.

Put method source code (annotated) final V putVal (int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node [] tab; / / local variable, pointing to the container Node p; / / local variable int n, I; / / 1. If HashMap is not initialized, initialize if ((tab = table) = = null | | (n = tab.length) = = 0) n = (tab = resize ()) .length; / / 2. According to the position of the calculated element in the array, and determine whether the target location is empty / / 2.1 if it is empty. New A new Node is placed at the target location if ((p = tab [I = (n-1) & hash]) = = null) tab [I] = newNode (hash, key, value, null); / / 2.2 if it is not empty, discuss else {Node e; K k by case / / 2.2.1 if the target location has a value (it may be the root node of the red-black tree or the header of the linked list), compare whether the key is the same (equivalent to judging in advance) if (p.hash = = hash & & (k = p.key) = = key | | (key! = null & & key.equals (k) e = p / / 2.2.2 if the target location is a red-black tree, write the data else if (p instanceof TreeNode) e = ((TreeNode) p) .putTreeVal (this, tab, hash, key, value); / / 2.2.3 if the target location is a linked list, traverse the entire linked list. Else {for (int binCount = 0;; + binCount) {/ / if the next node of the current node is empty, new a new node, and then the current node points to the new node if ((e = p.next) = = null) {p.next = newNode (hash, key, value, null) / / judge the length of the linked list with one additional node. If the length is greater than the threshold, convert the linked list to a red-black tree if (binCount > = TREEIFY_THRESHOLD-1) / /-1 for 1st treeifyBin (tab, hash); break } / / if the next node of the current node is not empty, determine whether the key is the same, and if so, jump out of the loop. If (e.hash = = hash & & (k = e.key) = = key | | (key! = null & & key.equals (k) break; p = e;}} / / a pair of 2.2.1 and 2.2.2 and 2.2.3. Judge the element that indicates that you want to overwrite the original position. If (e! = null) {V oldValue = e.value; if (! onlyIfAbsent | | oldValue = = null) e.value = value; afterNodeAccess (e); return oldValue;}} / / below is the expansion code, ignoring + + modCount; if (+ + size > threshold) resize (); afterNodeInsertion (evict); return null } flow chart of the put method

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

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.