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

This article shows you how to implement HashMap in JDK7 and JDK8. The content is concise and easy to understand. It will definitely brighten your eyes. I hope you can get something through the detailed introduction of this article.

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 happens to have no element in the location to be stored, encapsulate it into a Node object and put it in this position.

If ((p = tab [I = (n-1) & hash]) = = null)

Tab [I] = newNode (hash, key, value, null)

/ / otherwise, it means there are elements on it.

Else {

Node e; K k

/ / if the key of this element is the same as the one you want to insert, 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 traverse 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 the operation is completed, one more thing is done, judged, and the treeifyBin method may be executed

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 the threshold and decide whether to expand the capacity

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)

}

The above is what the implementation of HashMap in JDK7 and JDK8 is like. Have you learned any knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.

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.