Introduction to the
This paper is based on JDK1.8, mainly discusses the data structure and implementation principle of HashMap.
Main Introduction:
- Member attribute
- Initialization principle
- Expansion principle
- Linked list plus red black tree
Member attributes of a HashMap
1. Static inner classes
- Node implements the Map.Entry interface, the main storage class of HashMap
final int hash; // Hash value of each Node final K key; // key key V value; // value Node<K,V> next; // Point to the next NodeCopy the code- TreeNode, used in red-black trees, inherits the Node class
TreeNode<K,V> parent; TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev;Copy the code2. Main member attributes
transient Node<K,V>[] table; // hash bucket array TRANSIENT int size; // Map key-value transient int modCount; // Number of changes, same as in ArrayList, used for fast-fail int threshold; // capacity * loadFactor, when size > threshold will be expanded final float loadFactor; // Load factor, which defaults to 0.75Copy the codeConstructors
1. No-parameter construction
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
Copy the code2. Constructor for the initialCapacity parameter only
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
Copy the codeInitialCapacity and loadFactor constructors
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
Copy the codeTableSizeFor (initialCapacity). The tableSizeFor(initialCapacity) method matches a value greater than and closest to the cap value. For example, cap=11. Cap =25 and return 32
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
Copy the code3. Principle of capacity expansion
Expand capacity by calling resize()
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY < < 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; // Zero initial threshold using defaults (05.6 so far) newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab ! = null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) ! = null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) ! = null); if (loTail ! = null) { loTail.next = null; newTab[j] = loHead; } if (hiTail ! = null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }Copy the codeThe implementation steps are as follows:
1. Check whether the capacity is greater than the threshold of the original capacity. If yes, expand the capacity twice.
(1) If there are no elements after the node, hash & (newcap-1) to complete the placement of elements. (2) If the node is a tree structure, disassemble the tree to determine whether there are more than six elements. If there are no more than six elements, remove the tree structure. (3) When there is an element behind the node, hash & oldCap is used to determine whether the element needs to be shifted
Here are a few design ideas worth pondering:
1. Double the original capacity each time:
Reason: The capacity is set to the power of 2, and the capacity expansion only needs to be shifted, which can ensure that most elements do not need to move after expansion
2. Hash & (newCap-1) instead of hash % newCap because the and operation is faster
3. Use Hash & oldCap to determine whether the capacity needs to be moved
4. Generation of linked lists and red-black trees
Analyze putVal() to understand the process of adding elements
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; If ((TAB = table) = = null | | (n = TAB. Length) = = 0) / / if undefined size, for the first time put generates a default size of n = 16 (TAB = the resize ()). The length; If ((p = TAB [I = (n-1) & hash]) == null) // add a newNode TAB [I] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key ! = null && key.equals(k)))) // If the keys are the same, the value e = p will be overwritten; Else if (p instanceof TreeNode) // Modify the tree structure e = ((TreeNode<K,V>)p).puttreeval (this, TAB, hash, key, value); Else {// For (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); 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) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; If (++size > threshold) // If the capacity exceeds the threshold, expand resize(); afterNodeInsertion(evict); return null; }Copy the code1, if there is no element in the table or the length is 0, call resize
2. If there is no element in TAB [(n-1) & hash], the node information is added
3. If the key is the same, the original value will be overwritten
4. If the node is a tree node, the red-black tree operation (balanced tree operation) will be performed.
5. If the node is a linked list structure, the list is traversed. If the key is the same, a node in the list will be overwritten; otherwise, a new node will be added to the list
6, when the element is added to determine whether to expand, this will also exist thread insecurity.
** Lists are converted to tree structures **
final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) ! = null) { TreeNode<K,V> hd = null, tl = null; do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) ! = null); if ((tab[index] = hd) ! = null) // Generated tree hd.treeify(TAB); }}Copy the code1. If the length of the table is less than 64, capacity expansion is triggered to adjust the capacity. The red-black tree structure is generated only when the length is greater than or equal to 64
2. Transform all elements in the linked list into red-black tree nodes, and generate red-black tree structure, where the head node of the linked list is the root node of the tree
final void treeify(Node<K,V>[] tab) { TreeNode<K,V> root = null; for (TreeNode<K,V> x = this, next; x ! = null; x = next) { next = (TreeNode<K,V>)x.next; x.left = x.right = null; if (root == null) { x.parent = null; x.red = false; root = x; } else { K k = x.key; int h = x.hash; Class<? > kc = null; for (TreeNode<K,V> p = root;;) { int dir, ph; K pk = p.key; if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) dir = tieBreakOrder(k, pk); TreeNode<K,V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; root = balanceInsertion(root, x); break; } } } } moveRootToFront(tab, root); }Copy the codeAnalysis of linked lists and red-black trees when an element is removed
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; if ((tab = table) ! = null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) ! = null) { Node<K,V> node = null, e; K k; V v; if (p.hash == hash && ((k = p.key) == key || (key ! = null && key.equals(k)))) node = p; else if ((e = p.next) ! = null) { if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { do { if (e.hash == hash && ((k = e.key) == key || (key ! = null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) ! = null); } } if (node ! = null && (! matchValue || (v = node.value) == value || (value ! = null && value.equals(v)))) { if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p) tab[index] = node.next; else p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; }Copy the codeImplementation principle:
1. Check whether the key of the node in the table is the same as that of the deleted element. If so, set the position in the element to NULL
2. If the node is a tree node, it traverses the tree structure to find the element and removes an element in the tree node. If the number of nodes in the tree is less than 6, it returns to the list structure
3. If the node is a linked list, traverse the list to find the node with the same key and remove it
The node in the red-black tree was deleted
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) { int n; if (tab == null || (n = tab.length) == 0) return; int index = (n - 1) & hash; TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl; TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev; if (pred == null) tab[index] = first = succ; else pred.next = succ; if (succ ! = null) succ.prev = pred; if (first == null) return; if (root.parent ! = null) root = root.root(); if (root == null || root.right == null || (rl = root.left) == null || rl.left == null) { tab[index] = first.untreeify(map); // too small return; } TreeNode<K,V> p = this, pl = left, pr = right, replacement; if (pl ! = null && pr ! = null) { TreeNode<K,V> s = pr, sl; while ((sl = s.left) ! = null) // find successor s = sl; boolean c = s.red; s.red = p.red; p.red = c; // swap colors TreeNode<K,V> sr = s.right; TreeNode<K,V> pp = p.parent; if (s == pr) { // p was s's direct parent p.parent = s; s.right = p; } else { TreeNode<K,V> sp = s.parent; if ((p.parent = sp) ! = null) { if (s == sp.left) sp.left = p; else sp.right = p; } if ((s.right = pr) ! = null) pr.parent = s; } p.left = null; if ((p.right = sr) ! = null) sr.parent = p; if ((s.left = pl) ! = null) pl.parent = s; if ((s.parent = pp) == null) root = s; else if (p == pp.left) pp.left = s; else pp.right = s; if (sr ! = null) replacement = sr; else replacement = p; } else if (pl ! = null) replacement = pl; else if (pr ! = null) replacement = pr; else replacement = p; if (replacement ! = p) { TreeNode<K,V> pp = replacement.parent = p.parent; if (pp == null) root = replacement; else if (p == pp.left) pp.left = replacement; else pp.right = replacement; p.left = p.right = p.parent = null; } TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement); if (replacement == p) { // detach TreeNode<K,V> pp = p.parent; p.parent = null; if (pp ! = null) { if (p == pp.left) pp.left = null; else if (p == pp.right) pp.right = null; } } if (movable) moveRootToFront(tab, r); }Copy the code