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

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

The realization principle of HashMap

First of all, there is an array in which each element is a linked list (which may be inaccurate). When adding an element (key-value), the hash value of element key is first calculated to determine the position in the array, but elements with the same hash value may have been placed in the same position in the array, and then they are added to the elements with the same hash value, they are in the same position in the array, but form a linked list. The Hash values on the same linked list are the same, so the array stores the linked list. When the length of the linked list is too long, the linked list is converted to a red-black tree, which greatly improves the efficiency of lookup. When the capacity of the linked list array exceeds 0.75 of the initial capacity, the hash will double the size of the linked list array and move the original linked list array to the new array

That is, the schematic diagram of HashMap is:

Now let me analyze the implementation of HashMap in JDK7 and JDK8.

HashMap in JDK7

The underlying HashMap maintains an array, and each item in the array is an Entry

Transient Entry [] table

The objects we put into HashMap are actually stored in this array.

The key,value in Map is stored in the array as Entry.

Static class Entry implements Map.Entry {final K key; V value; Entry next; int hash

Where the Entry should be placed in the array (this position is often referred to as a bit bucket or hash bucket, that is, Entry with the same hash value will be placed in the same place, linked by a linked list), is calculated through the hashCode of key.

Final int hash (Object k) {int h = 0; h ^ = k.hashCode (); h ^ = (h > 20) ^ (h > 12); return h ^ (h > 7) ^ (h > 4);}

The value calculated by hash will use the indexFor method to find the table subscript where it should be located:

Static int indexFor (int h, int length) {return h & (length-1);}

This method is actually equivalent to modeling table.length.

Hash conflicts (collisions) occur when two key computes the same through hashCode, and HashMap resolves hash conflicts by using linked lists.

When a hash conflict occurs, the Entry stored in the array is set to the next of the new value. (note here that both An and B are mapped to the subscript I after hash. There is already A before. When map.put (B), put B in the subscript I, and An is the next of B, so the new value is stored in the array, and the old value is on the linked list of the new value.)

Schematic diagram:

So when there are a lot of hash conflicts, HashMap degenerates into a linked list.

Summarize the process after map.put:

When you put a pair of keys to a HashMap, it calculates a location based on the hashCode value of the key, which is where the object is going to be stored in the array.

If no object exists at that location, put the object directly into the array If an object already exists at this location, start searching along the chain of the existing object (in order to determine whether the value is the same, map does not allow duplicate key-value pairs). If there are objects in this chain, use the equals method to compare them. If the equals method comparison of each object on this chain is false, put the object in the array. Then link the object that previously existed at that position in the array to the back of the object.

It is worth noting that when key is null, it is put into table [0]

Private V putForNullKey (V value) {for (Entry e = table [0]; e! = null; e = e.next) {if (e.key = = null) {V oldValue = e.value; e.value = value; e.recordAccess (this); return oldValue;}} modCount++ AddEntry (0, null, value, 0); return null;}

When size is greater than threshold, capacity expansion occurs. Threshold equals capacity*load factor

Void addEntry (int hash, K key, V value, int bucketIndex) {if ((size > = threshold) & & (null! = table [bucketIndex])) {resize (2 * table.length); hash = (null! = key)? Hash (key): 0; bucketIndex = indexFor (hash, table.length);} createEntry (hash, key, value, bucketIndex);}

Resize in jdk7, resize occurs only when size > = threshold and Entry already exists in that slot in table. That is, although size > = threshold, the capacity will not be expanded until there is at least one Entry in each slot. And notice that resize doubles its capacity each time.

HashMap in JDK8

Until JDK7, the structure of HashMap is so simple, based on the implementation of an array and multiple linked lists, when hash values conflict, the corresponding nodes are stored in the form of linked lists.

There are some doubts about the performance of HashMap like this. If hundreds of nodes collide during hash and are stored in a linked list, then if you want to find one of the nodes, it will inevitably take O (N) search time, which will be a great performance loss. This problem has finally been solved in JDK8. In the worst case, the time complexity of linked list lookup is O (n), while the red-black tree is always O (logn), which will improve the efficiency of HashMap.

HashMap in JDK7 uses bit bucket + linked list, which we often call hash linked list, while JDK8 uses bit bucket + linked list / red-black tree (see red-black tree for red-black tree), which is also non-thread-safe. When the length of the linked list of a bit bucket reaches a certain threshold, the linked list will be converted into a red-black tree.

In JDK8, when the number of nodes of the same hash value is not less than 8, it will no longer be stored as a single linked list and will be adjusted to a red-black tree (the null node is not drawn in the image above). This is the biggest difference between the HashMap implementation in JDK7 and JDK8.

Next, let's take a look at the source implementation of HashMap in JDK8.

The name Entry in JDK becomes Node because it is associated with the red-black tree implementation TreeNode.

Transient Node [] table

When the number of collision nodes is not less than 8-1, it is converted to a red-black tree.

Static final int TREEIFY_THRESHOLD = 8

The put method has changed a lot in JDK8.

Public V put (K key, V value) {return putVal (hash (key), key, value, false, true);} final V putVal (int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node [] tab; Node p; int n, I; / if there is no data in the current map, execute the resize method. And return n if ((tab = table) = = null | | (n = tab.length) = = 0) n = (tab = resize ()) .length / / if the key-value pair to be inserted does not happen to have an element in the location to be stored, encapsulate it into a Node object and put it in this location. If ((p = tab [I = (n-1) & hash]) = = null) tab [I] = newNode (hash, key, value, null) / / otherwise, it means that there is an element else {Node e; K k; / / if the key of this element is the same as the one you want to insert, then replace it and it's done. If (p.hash = = hash & & (k = p.key) = = key | | (key! = null & & key.equals (k) e = p; / / 1. If the current node is data of type TreeNode, execute the putTreeVal method else if (p instanceof TreeNode) e = ((TreeNode) p) .putTreeVal (this, tab, hash, key, value); else {/ / still traverses the data on this chain, no different from jdk7 for (int binCount = 0; + + binCount) {if ((e = p.next) = = null) {p.next = newNode (hash, key, value, null); / / 2. After completing the operation, one more thing is done, judged, and may execute the treeifyBin method if (binCount > = TREEIFY_THRESHOLD-1) / /-1 for 1st treeifyBin (tab, hash); break } if (e.hash = = hash & & (k = e.key) = = key | | (key! = null & & key.equals (k) break; p = e }} if (e! = null) {/ / existing mapping for key V oldValue = e.value; if (! onlyIfAbsent | | oldValue = = null) / / true | |-- e.value = value; / / 3. AfterNodeAccess (e); return oldValue }} + + modCount; / / judge threshold to decide whether to expand if (+ + size > threshold) resize (); / / 4. AfterNodeInsertion (evict); return null;}

TreeifyBin () converts the linked list into a red-black tree.

The previous indefFor () method disappears, directly using (tab.length-1) & hash, so seeing this represents the lower corner of the array.

Static final int hash (Object key) {int h; return (key = = null)? 0: (h = key.hashCode ()) ^ (h > 16);} at this point, the study on "implementation process parsing of HashMap in JDK7 and JDK8" is over, hoping to solve everyone's doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.