The words written in the front

Don’t look at where you started, look at where you’re going.

Inheritance relationships

See the previous article for details

The underlying structure

1.8 data structure

Discard the concept of segment-based locking and use Node + CAS + Synchronized instead of Segment

The HashEntry structure is removed

When table [(n-1) & hash] == NULL, CAS operation is adopted. When hash conflicts occur, synchronized is usedCopy the code

The internal structure is the same as that of HashMap: array + linked list + red-black tree

Default sizeCtl = 16, which can be set during initialization

Basic attributes

/** * The maximum possible table size. The value must be exactly 1<<30 to keep the permissions of two table sizes in Java array allocation and index *, further required because the first two bits of the 32-bit hash field are used for control purposes. Private static final int MAXIMUM_CAPACITY = 1 << 30; Private static final int DEFAULT_CAPACITY = 16; private static final int DEFAULT_CAPACITY = 16; Static final int MAX_ARRAY_SIZE = integer. MAX_VALUE - 8; static final int MAX_ARRAY_SIZE = integer. MAX_VALUE - 8; /** * Default concurrency */ private static final int DEFAULT_CONCURRENCY_LEVEL = 16; /** * private static final float LOAD_FACTOR = 0.75f; /** * the bin count threshold for objects that use trees instead of lists. When an element is added to A, the bin is converted to a bin with at least that many nodes in the tree. This value must be larger * greater than 2 and should be at least 8 to comply with the assumption of removing tree shrinkage about converting back to normal bins. Static final int TREEIFY_THRESHOLD = 8; Static final int UNTREEIFY_THRESHOLD = 6; /** * Minimum table size the container can be treeified with. (Otherwise, if there are too many nodes in the container, the table size will be adjusted.) * The value to be avoided is at least 4 * TREEIFY_THRESHOLD Conflicts with the treeIFICATION threshold. Static final int MIN_TREEIFY_CAPACITY = 64; static final int MIN_TREEIFY_CAPACITY = 64; /** * The minimum number of restores per transfer step. The scope is subdivided to allow multiple sizing threads. * This value is used as a lower bound to avoid encountering excessive memory contention from resizers. The value should be at least DEFAULT_CAPACITY. */ private static final int MIN_TRANSFER_STRIDE = 16; /** * The number of bits used to generate the stamp, in sizeCtl. Must be at least 6 for 32-bit arrays. */ private static int RESIZE_STAMP_BITS = 16; /** * can help adjust the maximum number of threads to size. Must fit 32-resize_STAMP_bits. */ private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1; /** * Records the bit displacement of the size stamp, in sizeCtl. */ private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;Copy the code

It can be seen that compared with 1.7, related critical attributes of tree are added and related attributes of Segment are removed

A constructor

Parameterless constructor

The source code

public ConcurrentHashMap() {
    }
Copy the code

The default size is 16

Pass in a constructor that initializes the size

A negative value throws an exception

    public ConcurrentHashMap(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        this.sizeCtl = cap;
    }
Copy the code

Dynamically adjusted sizeCtl

Call the tableSizeFor method

Make sure sizeCtl is 2 to the n

Pass in a map constructor

SizeCtl is also initialized to 16, and all elements in the map are put into ConcurrentHashMap

public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
        this.sizeCtl = DEFAULT_CAPACITY;
        putAll(m);
    }
Copy the code

Pass in the initialization capacity and load factor

The default concurrency is 1

public ConcurrentHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, 1);
    }
Copy the code

Pass in the initial capacity, load factor, and concurrency

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) { if (! (loadFactor > 0.0 f) | | initialCapacity < 0 | | concurrencyLevel < = 0) throw new IllegalArgumentException (); if (initialCapacity < concurrencyLevel) // Use at least as many bins initialCapacity = concurrencyLevel; // as estimated Threads Long size = (long)(1.0 + (long)initialCapacity/loadFactor); // As estimated Threads Long size = (long)(1.0 + (long)initialCapacity/loadFactor); int cap = (size >= (long)MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int)size); this.sizeCtl = cap; }Copy the code

Enter the size of initialCapacity to determine a minimum that is greater than or equal to the initialCapacity size to the NTH power of 2,

If initialCapacity is 15, the sizeCtl value is 16. If initialCapacity is 16, the sizeCtl value is 16.

If initialCapacity exceeds the maximum allowed size, sizeCtl is the maximum.

Note that the concurrencyLevel parameter in the constructor has changed significantly in JDK1.8 and does not represent the number of concurrent requests allowed,

It is only used to determine the sizeCtl size. Concurrency control in JDK1.8 is specific to buckets, i.e. how many concurrent buckets can be allowed.

The Node is introduced

The source code

static class Node<K,V> implements Map.Entry<K,V> { final int hash; // Hash value of key final K key; //key volatile V val; //value volatile Node<K,V> next; // represents the next Node in the list Node(int hash, K key, V val, Node<K,V> next) {this.hash = hash; this.key = key; this.val = val; this.next = next; } public final K getKey() { return key; } public final V getValue() { return val; } public final int hashCode() { return key.hashCode() ^ val.hashCode(); }}Copy the code

This is the base class that makes up every element in 1.8

TreeNode

Construct the nodes of the tree

static final class TreeNode<K,V> extends Node<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next, TreeNode<K,V> parent) { super(hash, key, val, next); this.parent = parent; }}Copy the code

TreeBin introduction

Source:

static final class TreeBin<K,V> extends Node<K,V> { TreeNode<K,V> root; volatile TreeNode<K,V> first; volatile Thread waiter; volatile int lockState; // values for lockState static final int WRITER = 1; // set while holding write lock static final int WAITER = 2; Static final int READER = 4; // set when waiting for write lock // increment Value for setting read lockCopy the code

As the head node of the tree, only root and first nodes are stored, but the key and value of the node are not stored.

ForwardingNode

The node placed in the head during the transition is an empty node

static final class ForwardingNode<K,V> extends Node<K,V> { final Node<K,V>[] nextTable; ForwardingNode(Node<K,V>[] tab) { super(MOVED, null, null, null); this.nextTable = tab; }}Copy the code

Commonly used method

put

Call the putVal method with the third parameter of putVal set to false

When set to false, the value must be set

True is set only if the value of the key is null

public V put(K key, V value) {
        return putVal(key, value, false);
    }
Copy the code

PutVal method

final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); Int hash = spread(key.hashcode ()); int hash = spread(key.hashcode ()); int binCount = 0; for (Node<K,V>[] tab = table;;) {// infinite loop Node<K,V> f; int n, i, fh; If (TAB = = null | | (n = TAB. Length) = = 0) / / the length of the table is empty or table of 0 / / initialize the table TAB = initTable (); Else if ((f = tabAt(TAB, I = (n-1) & hash)) == null) {// Table is not empty and table length is greater than 0, If (casTabAt(TAB, I, null, new Node<K,V>(hash, key, value, null))) // Compare and swap values. // No lock when adding to empty bin} else if ((fh = f.hash) == MOVED) // The hash value of this node is MOVED helpTransfer(tab, f); else { V oldVal = null; Synchronized (f) {if (tabAt(TAB, If (fh >= 0) {// The hash value of this node in the table is greater than 0 // binCount is set to 1 binCount = 1; for (Node<K,V> e = f;; ++binCount) {// infinite loop K; if (e.hash == hash && ((ek = e.key) == key || (ek ! = null &&key. equals(ek)))) {oldVal = e.val; if (! OnlyIfAbsent) // Save the specified value to the node, that is, update the node value. break; } // save current Node Node<K,V> pred = e; If ((e = e.ext) == null) {// The next node of the current node is null, Next = new Node<K,V>(hash, key, value, null); // Exit loop break; }}} else if (f instanceof TreeBin) {if (f instanceof TreeBin) { // binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) ! = null) {// put hash, key, value into red black tree // save val oldVal = p.val; if (! OnlyIfAbsent) // Judge // assign node value value p.val = value; } } } } if (binCount ! If (binCount >= TREEIFY_THRESHOLD) // If binCount is greater than or equal to the threshold for converting to a red-black tree // Convert to treeifyBin(TAB, I); if (oldVal ! // Return oldVal; // return oldVal; break; }} // Increase the number of bincounts addCount(1L, binCount); return null; }Copy the code

Table initialization, tree conversion, and capacity expansion are involved in put 1.8. InitTable, tabAt, casTabAt, helpTransfer, putTreeVal, treeifyBin, and addCount are used. More on that later

1.8 Process summary of putVal Method

1. When adding a pair of key-value pairs, we first determine whether the array holding these key-value pairs is initialized. If not, we initialize the array

2. Calculate the hash value to determine the position in the array

3. If the position is empty, add it; if not, remove the node

4. If the hash value of the removed node is MOVED(-1), it means that the array is being expanded, copied to a new array, and the current thread will help with the replication

5. In the last case, if the node is not empty or expanded, synchronized is used to lock and add the node

6. Then determine whether the node is stored in a linked list or a tree

7. If it is a linked list, iterate through the list until the keys of the extracted nodes are compared with the keys to be placed. If the keys are equal and the hash value of the keys is equal,

If it is the same key, overwrite the value, or add it to the end of the list

8. In the case of a tree, call putTreeVal to add the element to the tree

Finally, after the addition is completed, it will judge how many nodes there are at the node (note the number before the addition). If the number reaches more than 8,

9. Call the treeifyBin method to try to convert the list to a tree or expand the array

JDK1.8 initTable ()

The array is initialized only when used

Concurrency issues are implemented through CAS manipulation of the sizeCtl variable.

InitTable source

private final Node<K,V>[] initTable() { Node<K,V>[] tab; int sc; While (= (TAB table) = = null | | TAB. The length = = 0) {/ / put the first time, the table has not been initialized, If ((sc = sizeCtl) < 0) thread.yield (); if (sc = sizeCtl) < 0) thread.yield (); // lost initialization race; Just spin else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {//SIZECTL: Represents the memory offset of the current object, sc represents the expected value, -1 represents the value to be replaced, Set to 1 to initialize the table with the try {if ((TAB = table) = = null | | TAB. The length = = 0) {int n = > 0 (sc)? Sc: DEFAULT_CAPACITY; + + + + + + + + + + @suppressWarnings ("unchecked") Node<K,V>[] nt = (Node<K,V>[])new Node<? ,? >[n]; table = tab = nt; sc = n - (n >>> 2); } } finally { sizeCtl = sc; // after initialization, sizeCtl size is 3/4 of array size} break; } } return tab; }Copy the code

InitTable process

1. If sizeCtl is smaller than 0, other arrays are being initialized

2. If sizeCtl is greater than 0, initialize an array with sizeCtl

3. Otherwise, initialize an array of the default size (16)

4. Set the sizeCtl value to 3/4 of the array length

TabAt function

@suppressWarnings ("unchecked") static final <K,V> Node<K,V> tabAt(Node<K,V>[] TAB, int I) {// Force to read data in main memory instead of the thread's own local working memory, Return (Node<K,V>) u.getobjectVolatile (TAB, ((long) I << ASHIFT) + ABASE); }Copy the code

This function returns a node with subscript I in the table array, which is reflected from the Unsafe object. The second parameter of getObjectVolatile is the offset address with subscript I.

CasTabAt function

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> V) {return U.compareAndSwapObject(TAB, (long) I << ASHIFT) + ABASE, c, V); }Copy the code

This function is used to compare whether the node with subscript I of the table array is C, and if it is C, v is swapped. Otherwise, the switch operation is not performed.

HelpTransfer function

	/**
     * Helps transfer if a resize is in progress.
     * 如果正在调整大小则帮忙转移
     */
	 //将旧的数组中的元素复制到新的数组中
    final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
        Node<K,V>[] nextTab; int sc;
        //旧数组不为空且nextTable也不空的情况下才能复制
        if (tab != null && (f instanceof ForwardingNode) &&
            (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
            int rs = resizeStamp(tab.length);
            while (nextTab == nextTable && table == tab &&
                   (sc = sizeCtl) < 0) {
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || transferIndex <= 0)
                    break;
                //cas操作保证线程安全
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                    transfer(tab, nextTab);//调用扩容方法
                    break;
                }
            }
            return nextTab;
        }
        return table;
    }
Copy the code

This table is used to move nodes in table to nextTable during expansion.

PutTreeVal function

final TreeNode<K,V> putTreeVal(int h, K k, V v) { Class<? > kc = null; // The Class object that defines k // identifies whether the tree has been searched once, not necessarily from the root node, but the searched path must have contained all nodes to be searched later. For (TreeNode<K,V> p = root;) { int dir, ph; K pk; If (p == null) {first = root = new TreeNode<K,V>(h, K,V, null, null); break; Else if ((ph = p.hash) > h) dir = -1; Else if (ph < h)// < dir = 1; / / on the right side else if ((pk = p.k ey) = = k | | (pk! = null &&k. quals(pk)))// Return p if the current node has the same key object as the specified key object; // The hash value of the current node is equal to the hash value of the specified key. But equals ranging else if (= = null && (kc, kc = comparableClassFor (k)) = = null) | | (dir = compareComparables (kc, k, Pk)) == 0) {// Specify that the comparable key is not implemented or is comparable to the current node's comparable key object (first loop only). TreeNode<K,V> q, ch; // Define the node to return, and the child node to search = true; /* * If ((ch = p.left)! /* * If ((ch = p.left)! = null && (q = ch.findTreeNode(h, k, kc)) ! = null) || ((ch = p.right) ! = null && (q = ch.findTreeNode(h, k, kc)) ! = null)) return q; } dir = tieBreakOrder(k, pk);} dir = tieBreakOrder(k, pk); TreeNode<K,V> xp = p; TreeNode<K,V> p; Pointing to the current node / * * / / define xp if dir is less than or equal to 0, then see if left node of the current node is empty, if is empty, you can add to the elements as left from the current node, if not empty, will continue the next round is * if dir is greater than or equal to 0, then see if right node of the current node is empty, If it is null, the element to be added can be used as the right node of the current node. If it is not empty, the next round of comparison is required. * If one of the above two children is not empty, the other thing this if does is to point p to the corresponding non-empty child node. Start the next comparison */ if ((p = (dir <= 0)? TreeNode<K,V> x, f = first; TreeNode<K,V> x, f = first; First = x = new TreeNode<K,V>(h, K,V, f, xp); // Create a new tree if (f! = null) f.prev = x; if (dir <= 0) xp.left = x; // The left child points to the new tree node else XP.right = x; // Right child points to the new tree node if (! xp.red) x.red = true; else { lockRoot(); // Insertion {root = balanceInsertion(root, x); } finally {unlockRoot(); }} break; } } assert checkInvariants(root); return null; }Copy the code

This function adds the hash, key, and value values to the red-black tree, or returns null if they have been added, otherwise returns the hash, key, and value.

TreeifyBin function

When the array length is less than 64, double the array size, otherwise turn the list into a tree

private final void treeifyBin(Node<K,V>[] tab, int index) { Node<K,V> b; int n, sc; if (tab ! Println ("treeifyBin \t==> treeifyBin: "+tab.length); if ((n = tab.length) < MIN_TREEIFY_CAPACITY) //MIN_TREEIFY_CAPACITY 64 tryPresize(n << 1); Else if ((b = tabAt(TAB, index))! = null &&b.hash >= 0) {synchronized (b) { If (tabAt(TAB, index) == b) {TreeNode<K,V> hd = null, tl = null; For (Node<K,V> e = b; e ! = null; e = e.next) { TreeNode<K,V> p = new TreeNode<K,V>(e.hash, e.key, e.val, null, null); If ((p.rev = tl) == null) // convert nodes to TreeNode lists, head nodes are still in the same position; // set head else tl.next = p; tl = p; } setTabAt(tab, index, new TreeBin<K,V>(hd)); // Put the list of Treenodes into the container TreeBin}}}}}Copy the code

This function is used to convert the data structure in the bucket to a red-black tree. It is worth noting that when the table length does not reach the threshold, a scaling operation is performed, which causes all elements in the bucket that triggered the treeifyBin operation to perform a scaling operation

To avoid having too many nodes in a bucket.

TryPresize method

Private final void tryPresize(int size) {/* * MAXIMUM_CAPACITY = 1 << 30 * */ int C = (size >= (MAXIMUM_CAPACITY >>> 1))? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>> 1) + 1); int sc; while ((sc = sizeCtl) >= 0) { Node<K,V>[] tab = table; int n; /* * If table is not already initialized, initialize an array with sizeCtrl and the larger array in c * and set sizeCtrl to -1. After initialization I set sizeCtrl to 3/4 of the size of the array * why do I initialize the array where it expands? * This is because putAll does not call initTable to initialize the table. Instead, tryPresize is called. So here need to do a judgment whether need to initialize the table * / if (TAB = = null | | (n = TAB. Length) = = 0) {n = > c (sc)? sc : c; If (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { SizeCtl = -1 try {if (table == TAB) {@suppressWarnings ("unchecked") Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; table = nt; sc = n - (n >>> 2); } } finally { sizeCtl = sc; }}} /* * Exit when c is smaller than or equal to sizeCtl or array size is greater than or equal to maximum size. But 2 n times * / else if (c < = sc | | n > = MAXIMUM_CAPACITY) {break; } else if (TAB == table) {int rs = resizeStamp(n); /* * Transfer the element from the first parameter to the second element of the Table. * * Transfer the element from the first parameter to the second element of the Table. * Transfer the element from the first parameter to the second element of the Table. In transfer, when the second parameter is null, * creates a table */ if (sc < 0) {Node<K,V>[] nt; if ((sc >>> RESIZE_STAMP_SHIFT) ! = rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0) break; /* * The number of threads to transfer is increased by one. */ if (U.compareAndSwapInt(this, SIZECTL, sc, SC + 1)) Transfer (TAB, nt); } /* * No initialization or expansion, */ else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) {Transfer (TAB, null); }}}}Copy the code

In the tryPresize method, there is no lock, multiple threads are allowed to enter, and if the array is expanding, the current thread helps expand as well.

AddCount method

rivate final void addCount(long x, int check) { CounterCell[] as; long b, s; if ((as = counterCells) ! = null || ! U.compareAndSwapLong(this, BASECOUNT, b = BASECOUNT, s = b + x)) {// counterCells are not empty or the comparison exchange fails. long v; int m; Boolean uncontended = true; if (as == null || (m = as.length - 1) < 0 || (a = as[ThreadLocalRandom.getProbe() & m]) == null || ! (uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { // cas fullAddCount(x, uncontended); return; } if (check <= 1) return; s = sumCount(); } if (check >= 0) {Node<K,V>[] TAB, nt; int n, sc; while (s >= (long)(sc = sizeCtl) && (tab = table) ! = null && (n = tab.length) < MAXIMUM_CAPACITY) { int rs = resizeStamp(n); if (sc < 0) { if ((sc >>> RESIZE_STAMP_SHIFT) ! = rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0) break; if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, null); s = sumCount(); }}}Copy the code

This function increments the value of binCount by one.

Expansion method

Jdk1.8 transfer method

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) { int n = tab.length, stride; if ((stride = (NCPU > 1) ? (n >>> 3)/NCPU: n) < MIN_TRANSFER_STRIDE) //MIN_TRANSFER_STRIDE // subdivide range //MIN_TRANSFER_STRIDE=16 /* * Initialize a table twice the length of nextTab * at this point, nextTable is set to a value (null initially) * because if one thread starts a table expansion, other threads can also help expand the table. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +  (Node<K,V>[])new Node<? ,? >[n << 1]; nextTab = nt; } catch (Throwable ex) { // try to cope with OOME sizeCtl = Integer.MAX_VALUE; return; } nextTable = nextTab; transferIndex = n; } int nextn = nextTab.length; /* * Create a FWD node, this is used to control concurrency, when a node is empty or has been transferred, / ForwardingNode<K,V> FWD = new ForwardingNode<K,V>(nextTab); boolean advance = true; // Whether to continue looking forward to the flag bit Boolean finishing = false; Case of this (int I = 0, bound = 0;;) // to ensure sweep(before doing nextTab (right), re-scan the array (right) and see what doesn't happen (right). { Node<K,V> f; int fh; while (advance) { int nextIndex, nextBound; if (--i >= bound || finishing) { advance = false; } else if ((nextIndex = transferIndex) <= 0) { i = -1; advance = false; } else if (U.compareAndSwapInt (this, TRANSFERINDEX, nextIndex, nextBound = (nextIndex > stride ? nextIndex - stride : 0))) { bound = nextBound; i = nextIndex - 1; advance = false; } } if (i < 0 || i >= n || i + n >= nextn) { int sc; If (finishing) {// Transfer nextTable = null; table = nextTab; sizeCtl = (n << 1) - (n >>> 1); // Set sizeCtl to 0.75 return after expansion; } if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { if ((sc - 2) ! = resizeStamp(n) << RESIZE_STAMP_SHIFT) { return; } finishing = advance = true; i = n; // recheck before commit } } else if ((f = tabAt(tab, ForwardingNode (Hash = MOVED[-1]) advance = casTabAt(TAB, I, null, FWD); else if ((fh = f.hash) == MOVED) advance = true; If (tabAt(TAB, I) == f) {Node<K,V> ln, hn; If (fh >= 0) {// If (fh >= 0) {// If (fh >= 0) {// If (fh >= 0) {// If (fh >= 0) {// If (fh >= 0) { The result of the & operation can only be 0 or n * according to this rule * 0--> placed in the same position of the new table * n--> placed in the (n+ old position) of the new table */ int runBit = fh & n; Node<K,V> lastRun = f; /* * lastRun represents the last node to be copied * every time the new node's hash&n -> b changes, set runBit to the result b * The value of runBit is the last invariant hash&n value * and the value of lastRun is the last node (let's say p node) that caused hash&n to change * why do that? Since the hash&n value of the node after the p node is the same as that of the P node, * so when copying to the new table, it must still be in the same position as the P node * After copying the P node, the next node of the P node still points to its original node, so there is no need to copy. */ for (Node<K,V> p = f.next; p ! = null; p = p.next) { int b = p.hash & n; //n is the length of the array before expansion. = runBit) { runBit = b; lastRun = p; } } if (runBit == 0) { ln = lastRun; hn = null; } else { hn = lastRun; ln = null; } /* for (Node<K,V> p = f; Node<K,V> p = f; Node<K,V> p = f; p ! = lastRun; p = p.next) { int ph = p.hash; K pk = p.key; V pv = p.val; If ((ph&n) == 0) /* * If runBit = 0, * sets the last hash node of the old sequence to the first hash node of the old table and the next hash node * and returns itself, */ ln = new Node<K,V>(ph, pk, pv, ln); Else /* * Assuming runBit is not 0, * sets the last hashed node of the old sequence to the first hashed node of the old table and the next node * and returns itself, */ hn = new Node<K,V>(ph, pk, pv, hn); } setTabAt(nextTab, i, ln); setTabAt(nextTab, i + n, hn); setTabAt(tab, i, fwd); advance = true; } else if (TreeBin<K,V> t = (TreeBin<K,V>)f; TreeNode<K,V> lo = null, loTail = null; TreeNode<K,V> hi = null, hiTail = null; int lc = 0, hc = 0; for (Node<K,V> e = t.first; e ! = null; e = e.next) { int h = e.hash; TreeNode<K,V> p = new TreeNode<K,V> (h, e.key, e.val, null, null); if ((h & n) == 0) { if ((p.prev = loTail) == null) lo = p; else loTail.next = p; loTail = p; ++lc; } else { if ((p.prev = hiTail) == null) hi = p; else hiTail.next = p; hiTail = p; ++hc; }} /* * If the number of nodes is less than or equal to 6, go back to a linked list */ ln = (lc <= UNTREEIFY_THRESHOLD)? untreeify(lo) : (hc ! = 0)? new TreeBin<K,V>(lo) : t; hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc ! = 0)? new TreeBin<K,V>(hi) : t; setTabAt(nextTab, i, ln); setTabAt(nextTab, i + n, hn); setTabAt(tab, i, fwd); advance = true; } } } } } }Copy the code

The characteristics of

1. Copy the nodes in the array to the same location in the new array, or move them to the same location in the expanded part

2. A step size is calculated to represent the length of the array handled by a thread, which is used to control CPU usage.

3. Each CPU processes at least 16 array elements, which means that if an array is 16 in length, only one thread will copy and move it

The FWD node will be set at the head of the linked list for each node, so that other threads will skip it.

5. The copied list in the new array is not absolute reverse order

The get method

The GET method is simple, supports concurrent operations, and does not lock

1. When the key is null, a NullPointerException is thrown

2. The get operation determines where the element is placed in the array by first calculating the hash value of the key

3. Then traverse all nodes at the location

4. Return a value if it exists, or null if it does not

public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; Int h = spread(key.hashcode ()); if ((tab = table) ! = null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) ! = null) {/ / table is not empty and table greater than zero and the key is the length of the barrel is not null if (eh = e.h (ash) = = h) {/ / table of the elements in the hash value and the key of the hash values are equal if (= e.k (ek ey) = = key | | (ek ! = null &&key.equals (ek))) // return e.val; } else if (eh < 0) return (p = e.type (h, key))! Return (p = e.type (h, key))! = null ? p.val : null; while ((e = e.next) ! = null) {/ / in the case of node hash value greater than 0 if (e.h ash = = h && (= e.k (ek ey) = = key | | (ek! = null && key.equals(ek)))) return e.val; } } return null; }Copy the code

The size method

The size of source code

public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 :
           (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n);
}
Copy the code

The maximum is the maximum value of the Integer type, but the Map size can exceed MAX_VALUE, so there is another method, mappingCount(), which the JDK recommends instead of size().

MappingCount () looks like this:

public long mappingCount() {
    long n = sumCount();
    return (n < 0L) ? 0L : n; // ignore transient negative values
}
Copy the code

Both size() and mappingCount() are computed by sumCount().

The code for sumCount() looks like this:

final long sumCount() { CounterCell[] as = counterCells; CounterCell a; long sum = baseCount; if (as ! = null) { for (int i = 0; i < as.length; ++i) { if ((a = as[i]) ! = null) sum += a.value; } } return sum; }Copy the code

Look at the sumCount() code. ConcurrentHashMap provides two helper variables, baseCount and counterCells, and a CounterCell helper inner class.

SumCount () is the process of iterating through counterCells to count sum.

Size () is definitely affected when put is performed, and addCount() is called at the end of put().

AddCount () has the following code:

If counterCells == NULL, the CAS increment operation is performed on baseCount.

if ((as = counterCells) ! = null || ! U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { CounterCell a; long v; int m; boolean uncontended = true;Copy the code

Use counterCells if concurrency causes baseCount CAS to fail.

if (as == null || (m = as.length - 1) < 0 || (a = as[ThreadLocalRandom.getProbe() & m]) == null || ! (uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { fullAddCount(x, uncontended); return; } if (check <= 1) return; s = sumCount();Copy the code

If counterCells CAS fails, in the fullAddCount method, an infinite loop continues until it succeeds.

private final void fullAddCount(long x, boolean wasUncontended) { int h; if ((h = ThreadLocalRandom.getProbe()) == 0) { ThreadLocalRandom.localInit(); // force initialization h = ThreadLocalRandom.getProbe(); wasUncontended = true; } boolean collide = false; // True if last slot nonempty for (;;) {// loop until successful CounterCell[] as; CounterCell a; int n; long v; if ((as = counterCells) ! = null && (n = as.length) > 0) { if ((a = as[(n - 1) & h]) == null) { if (cellsBusy == 0) { // Try to atta ...Copy the code

Then, what exactly is the CounterCell class? We’ll see that it uses the @sun.misc.Contended class tag and contains a volatile variable inside.

The @sun.misc.Contended annotation indicates that this class needs to prevent “pseudo-sharing”. So,

What is pseudo-sharing?

The cache system stores data in units of cache lines.

Cache lines are consecutive bytes of an integer power of 2, typically 32 to 256 bytes. The most common cache line size is 64 bytes.

When multiple threads modify variables that are independent of each other, they inadvertently affect each other’s performance if they share the same cache row, which is called pseudo-sharing. The CounterCell code is as follows:

@sun.misc.Contended static final class CounterCell { volatile long value; CounterCell(long x) { value = x; }}Copy the code

JDK1.8 size is obtained by CAS calculation of baseCount and counterCell, and finally by baseCount and counterCell traversal.

JDK 8 recommends using the mappingCount method because it returns a long value and does not limit the maximum value because size is an int.

The remove method

I call the remove method first

Call the replaceNode method within the method

public V remove(Object key) {
        return replaceNode(key, null, null);
    }
Copy the code

ReplaceNode method

Final V replaceNode(Object key, V value, Object CV) {// Calculate the hash value of the key int hash = spread(key.hashcode ()); for (Node<K,V>[] tab = table;;) {// infinite loop Node<K,V> f; int n, i, fh; if (tab == null || (n = tab.length) == 0 || (f = tabAt(tab, I = (n-1) &hash)) == null) // The table is empty or the table length is 0 or the bucket corresponding to the key is empty // Break loop; Else if ((fh = f.hash) == MOVED) // The hash value of the first node in the bucket is MOVED // Transfer TAB = helpTransfer(TAB, f); else { V oldVal = null; boolean validated = false; Synchronized (f) {if (tabAt(TAB, I) == f) {if (fH >= 0) {// The hash value of the node is greater than 0, validated = true; for (Node<K,V> e = f, pred = null;;) {// infinite loop; if (e.hash == hash && ((ek = e.key) == key || (ek ! = null &&key. equals(ek)))) {// the hash value of the node is equal to the specified hash value, and the key is equal to V ev = e.val; if (cv == null || cv == ev || (ev ! = null && CV. Equals (ev))) {// if CV is null or equal to the value of the node, or if CV is not null and equal to the value of the node. if (value ! // set e.val = value; // set e.val = value; else if (pred ! = null) // Pred is the successor of e. Next = e.next; Else set index in table to e.ext setTabAt(TAB, I, e.ext); } break; } pred = e; if ((e = e.next) == null) break; }} else if (f instanceof TreeBin) {age: 3 = true; TreeBin<K,V> t = (TreeBin<K,V>)f; TreeNode<K,V> r, p; if ((r = t.root) ! = null && (p = r.findTreeNode(hash, key, null)) ! = null) {// The root node is not empty and there is a node equal to the hash and key specified // save the value of p node pv = p.val; if (cv == null || cv == pv || (pv ! = null && CV. Equals (pv))) {// CV is null or equal to the value of the node. if (value ! = null) p.val = value; Else if (t.emovetreenode (p)) // Remove p node setTabAt(TAB, I, untreeify(t.first)); } } } } } if (validated) { if (oldVal ! = null) {if (value == null) // baseCount value minus addCount(-1l, -1); return oldVal; } break; } } } return null; }Copy the code

Clear method

public void clear() { long delta = 0L; // negative number of deletions int i = 0; Node<K,V>[] tab = table; // loop the table while (TAB! = null && i < tab.length) { int fh; Node<K,V> f = tabAt(tab, i); if (f == null) ++i; Else if ((fh = f.hash) == MOVED) {// if (fh = helpTransfer(TAB, f); i = 0; Else {synchronized (f) {if (tabAt(TAB, I) == f) {Node<K,V> p = (fh >= 0? f : (f instanceof TreeBin) ? ((TreeBin<K,V>)f).first : null); while (p ! = null) { --delta; p = p.next; } setTabAt(tab, i++, null); } } } } if (delta ! = 0L) addCount(delta, -1); }Copy the code

Thread safety reasons

jdk1.7

Segment locking causes reentrant locking

Jdk1.8

The implementation of ConcurrentHashMap uses the idea of lock separation, but locks a node, which is thread-safe on volatile and CAS without locking.

How to ensure thread safety under multithreading

Thread safety for initialization

The table variable uses volatile to ensure that each fetch is the most recently written value

transient volatile Node<K,V>[] table;
Copy the code

Multithreaded security for the PUT method

Multiple threads perform a put operation at the same time, and use the optimistic lock CAS operation to determine which thread is eligible to initialize the array. The other threads can only wait.

Concurrency techniques used:

1. Volatile variable (sizeCtl) : It is a flag bit that tells other threads whether the pit is populated or not. Visibility between threads is guaranteed by volatile.

2.CAS operation: CAS operation ensures the atomicity of the set sizeCtl flag bits and ensures that only one thread can be set successfully

In the tabAt(TAB, I) method, the volatile operator uses the Unsafe class volatile to look for values volatile, ensuring that the value is the latest each time it is retrieved:

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
  return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
Copy the code

Even though volatile is used for the table variable above, it only guarantees visibility to its reference, not to the latest object in its array. Therefore, the volatile class is required to retrieve the latest Node

Expanded thread safety

Concurrency techniques:

1. Reduce lock granularity: The head Node of the Node list is used as the lock. If the default size is 16, there will be 16 locks

Is a parallel operation. At the same time, the head node is locked directly to ensure thread safety

2.Unsafe’s getObjectVolatile method: This ensures that the values obtained are up-to-date

ConcurrentHashMap uses various CAS operations to maximize the concurrent performance of expansion operations. During expansion,

Even if a thread calls the get query method, it can safely query the data. If a thread performs the PUT operation, it will also help expand the capacity.

SizeCtl flag bits and volatile variables are used for CAS operations to achieve communication and assistance between multiple threads. Only one Node is locked in the migration process, which ensures thread safety and improves concurrency performance.

How is ConcurrentHashMap thread safe

How do multiple threads work synchronously?

In ConcurrentHashMap, synchronization is performed primarily through Synchronized and unsafe.

1. Seeking sizeCtl and nodes in an unsafe location, the unsafe method is always used to ensure concurrency safety

2. When a node needs to be set at a certain location, the node is locked using the Synchronized mechanism.

3. When expanding the array, set the hash value to MOVED based on the step size and FWD node to ensure concurrent security

4. When a node at a certain location is copied to the expanded table, the Synchronized synchronization mechanism is also used to ensure the security of the present program

The difference between fail-fast and fail-safe

Fail-fast vs. Fail-safe

Iterator’s security failure is based on making a copy of the underlying collection, so it is not affected by changes made on the source collection.

All collection classes under the java.util package fail quickly, while all classes under the java.util. Concurrent package fail safely.

Rapid failure of the iterator will throw ConcurrentModificationException, iterators and safety failure never throw this exception.

Since ConcurrentHashMap is also under java.util.concurrent, it is fail-safe.

How to solve

The Fail-fast mechanism is an error detection mechanism.

It can only be used to detect errors because the JDK does not guarantee that the Fail-fast mechanism will occur.

If the fail-fast mechanism is used in a multi-threaded environment, it is recommended to use classes under the java.util. Concurrent package instead of classes under the java.util package.

Fail – fast principle

Produce fail – fast events, it is triggered by throw ConcurrentModificationException.

For example, collections under java.util call next() and remove(),

CheckForComodification () is performed.

If “modCount is not equal to expectedModCount”, throw ConcurrentModificationException, produce fail – fast.

How did Fail-fast come about

When multiple threads operate on the same collection, when a thread accesses the collection,

The contents of this collection have been changed by other threads (i.e., other threads have changed modCount by adding, removing, clear, etc.);

At this moment, will throw ConcurrentModificationException, produce fail – fast.

Solve the principle of Fail-Fast

Like in the source code of CopyOnWriteArrayList

Implement iterators yourself when iterating

Public Iterator<E> Iterator () {return COWIterator<E>(getArray(), 0); }... private static class COWIterator<E> implements ListIterator<E> { private final Object[] snapshot; private int cursor; private COWIterator(Object[] elements, int initialCursor) { cursor = initialCursor; // When creating a COWIterator, the elements of the collection are saved into a new copy array. // This way, when the original set of data changes, the values in the copied data do not change. snapshot = elements; }Copy the code

Where, yes copies the elements of the collection into a new array,

When the data in the original collection changes, the values in the copied data do not change.

So there is no fail-fast problem.

The CopyOnWriteArrayList Iterator implementation class, there is no such thing as checkForComodification (), more won’t throw ConcurrentModificationException.

ConcurrentHashMap, HashMap, and HashTable comparison

The difference between HashMap and ConcurrentHashMap

1.ConcurrentHashMap Segment the entire bucket array and lock each Segment.

Synchronized locks are finer grained and have better concurrency performance than HashTable, whereas HashMap has no locking mechanism and is not thread-safe.

(after JDK1.8, ConcurrentHashMap is implemented in a new way, using the CAS algorithm.)

A HashMap allows NULL key-value pairs, but ConCurrentHashMap does not.

ConcurrentHashMap and Hashtable?

The main difference between ConcurrentHashMap and Hashtable is in the way thread-safe is implemented.

Hashtable is the entire lock.

1.7 of ConcurrentHashMap is segmentalized locking, 1.8 is CAS plus synchronized to achieve thread safety, and both are more granular.

ConcurrentHashMap performs better than Hashtable.

Hashtable is largely deprecated.

The words in the back

Sometimes it’s the best way to be a human being.

Drunk is a coward,

Wake up wine is rabbit bile,

Be careful with the wine,

Eat for nothing, drink for nothing,

Stay out of the way if you drink.

Fixation of trailer

What if YOU want the map to be ordered?

The answer is to use TreeMap. We’ll talk about TreeMap in the next video.