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

This article mainly introduces "the underlying implementation principle of HashMap". In daily operation, I believe many people have doubts about the underlying implementation principle of 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 about "the underlying implementation principle of HashMap"! Next, please follow the editor to study!

We all know that HashMap is composed of array + linked list, bucket array is the main body of HashMap, and linked list exists to solve hash conflicts, but many people do not know that HashMap actually contains tree structure, but there must be a note, when will the red-black tree structure appear? We have to look at the source code, which explains that when the default list length is greater than 8, it will be converted to a tree. Let's take a look at the structure of the source code / * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) * / * * Node is the basic node of hash and is an one-way linked list, which implements the Map.Entry interface * / static class Node implements Map.Entry {final int hash; final K key; V value; Node next; / / constructor Node (int hash, K key, V value, Node next) {this.hash = hash; this.key = key This.value = value; this.next = next;} public final K getKey () {return key;} public final V getValue () {return value;} public final String toString () {return key + "=" + value;} public final int hashCode () {return Objects.hashCode (key) ^ Objects.hashCode (value) } 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 If (Objects.equals (key, e.getKey ()) & & Objects.equals (value, e.getValue ()) return true;} return false;}} copy code is followed by the tree structure.

TreeNode is the data structure of a red-black tree.

/ * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn * extends Node) so can be used as extension of either regular or * linked node. * / static final class TreeNode extends LinkedHashMap.Entry {TreeNode parent; / / red-black tree links TreeNode left; TreeNode right; TreeNode prev; / / needed to unlink next upon deletion boolean red; TreeNode (int hash, K key, V val, Node next) {super (hash, key, val, next);} / * * Returns root of tree containing this node. * / final TreeNode root () {for (TreeNode r = this, p * *;) {if ((p = r.parent) = = null) return r; r = p;}} copy code We are looking at the class definition public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {copy code

Inherit the abstract map, implement the Map interface, and serialize it.

There are also basic variables in the class.

Variable / * The default initial capacity-MUST be a power of two. * default initial capacity 16-must be a power of 2 * / static final int DEFAULT_INITIAL_CAPACITY = 1 > 2; n | = n > 4; n | = n > 8; n | = n > 16; return (n

= MAXIMUM_CAPACITY)? MAXIMUM_CAPACITY: n + 1;} copy the code

In this source code, the loadFactor load factor is a very important parameter, because it can reflect the use of the HashMap bucket array, so that the time complexity of HashMap will change differently.

When this load factor belongs to a low load factor, the number of key-value pairs that HashMap can hold is too small. After expansion, the key-value pairs are re-stored in the bucket array, the collision between keys and keys will decrease, and the length of the linked list will become shorter.

However, if you increase the load factor when the load factor is greater than 1, the number of key-value pairs that HashMap can hold will increase, so the collision will increase, and the length of the linked list will also increase. In general, we will not modify the load factor. The default is 0.75. Add Q group: 479499375, you can get a Java advanced learning package, including (Java engineering, distributed architecture, high concurrency, high performance, profound and simple, micro service architecture, Spring, MyBatis, Netty, source code analysis, JVM principle analysis, etc.). These become essential content for architects) and the Java advanced learning roadmap.

Capacity expansion mechanism

The resize () method is a way to recalculate capacity. Let's look at the source code:

/ * Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @ return the table * / final Node [] resize () {/ / reference the Entry array Node [] oldTab = table; int oldCap = (oldTab = = null)? 0: oldTab.length; int oldThr = threshold; int newCap, newThr = 0 If (oldCap > 0) {/ / if the array size before expansion has reached the maximum (2 ^ 30) / / here to determine whether to reach the maximum size if (oldCap > = MAXIMUM_CAPACITY) {/ / modify the threshold to the maximum value of int (2 ^ 31-1), so that threshold = Integer.MAX_VALUE; return oldTab will not be expanded later. } / / if the expanded capacity is less than the maximum and the old array bucket is larger than the initial capacity 16, the threshold is moved left by 1 (2 times larger) else if ((newCap = oldCap = DEFAULT_INITIAL_CAPACITY) newThr = oldThr 0) / / initial capacity was placed in threshold / / the new capacity equals the old threshold newCap = oldThr Else {/ / zero initial threshold signifies using defaults / / if array bucket capacity

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.