People should only forget themselves and love others, so that people can be quiet, happy and noble. — Anna Karenina by Leo Tolstoy

0 foreword

Thread-safe map-ConcurrenthashMap, let’s explore how it differs from HashMap and why it is thread-safe.

1 Inheritance System

2 attribute

• Bin array. Lazy initialization only at first insertion. The magnitude is always a power of two. Directly accessed by iterators.
  

  

• The next table to use; Non-null only during capacity expansion
  

  

• The base counter value, used primarily when there is no contention, is also used as feedback during table initialization contention. Update via CAS
  

  

• If the control over table initialization and expansion is negative, the table will be initialized or expanded: -1 is used to initialize the table. -n Number of active expansion threads Otherwise, when the table is null, the initial table size used when the table is created is retained, or the default is 0. After initialization, retain the element count of the next table to be expanded.
  

  

• Index of the next table to be split during expansion (+ 1)
  

  

• Spinlocks for capacity expansion and/or CounterCell creation (locked by CAS)
  

  

• Table of counter cells. If not null, the size is a power of 2.
  

  

• Node: Data structure that holds keys, values, and hash values for keys. Value and next are volatile to ensure visibility
  

  

• For a particular Node, the hash value of the transfer nodes is MOVED,-1. Where references to nextTable are stored. Insert the bin head node during transfer. ForwardingNode takes effect only when the table is expanded. It is placed in the table as a placeholder to indicate that the current node is null or has been moved.
  

  

3. Construction Method

3.1 no arguments

• Create a new empty map using the default initial table size (16)
  

  

3.2 do.

• Creates a new empty map with an initial table size that can hold a specified number of elements without dynamic resizing.
  

  

  – Creates a new map that has the same mapping as the given map

  

Note that sizeCtl maintains the capacity of a value to the power of two for now.

When instantiating ConcurrentHashMap with parameters, the size of the table will be adjusted based on the parameters. Assume that the parameter is 100, and eventually it will be adjusted to 256, ensuring that the table size is always a power of 2

tableSizeFor

• Returns the table size of a power of 2 for a given required capacity
  

  

Delayed initialization of the table

ConcurrentHashMap initializes only the sizeCtl value in the constructor. The table is not initialized directly, but deferred until the first put operation. However, put can be executed concurrently. How to ensure that the table is initialized only once?

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    // Enter spin
    while ((tab = table) == null || tab.length == 0) {
        // If a thread finds sizeCtl<0, it means that another thread is initializing, and the current thread cedes CPU time slices
        if ((sc = sizeCtl) < 0) 
            Thread.yield(); // Lost the chance to initialize the race; Direct spin
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                // Table is not empty, so double check
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0)? sc : DEFAULT_CAPACITY;@SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n]; table = tab = nt; sc = n - (n >>>2); }}finally {
                sizeCtl = sc;
            }
            break; }}return tab;
}
Copy the code

The Thread that performs the first PUT changes sizeCtl to -1 by executing the Unsafe.compareAndSwapInt method. Only one Thread can successfully change sizeCtl. The other threads can only use Thread.yield() to give up CPU time chips until table initialization is complete.

4 put

The table is initialized, and the PUT operation adopts CAS+synchronized to implement concurrent insertion or update.

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    / / calculate the hash
    int hash = spread(key.hashCode());
    int binCount = 0;
    // Spin is guaranteed to add success
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        // step1. table is initialized if null or empty
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        // step 2. If the current array index has no value, create it directly
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // CAS creates a new node at index I. If index I is null, the creation succeeds. Otherwise, the loop continues spinning
            if (casTabAt(tab, i, null.new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        // step3. If the current bucket is a transfer node, the capacity of the bucket is being expanded. Wait until the capacity expansion is complete
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        // step4. The current index position has a value
        else {
            V oldVal = null;
            // Lock the current slot to ensure that only one thread can modify the slot
            synchronized (f) {
                // Check whether the I position data has been modified
                // binCount is assigned to indicate that the table is being modified
                if (tabAt(tab, i) == f) {
                    / / list
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            // If there is a value, return it directly
                            if(e.hash == hash && ((ek = e.key) == key || (ek ! =null && key.equals(ek)))) {
                                oldVal = e.val;
                                if(! onlyIfAbsent) e.val = value;break;
                            }
                            Node<K,V> pred = e;
                            // Assign the new element to the end of the list and exit the spin
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break; }}}// Red black tree, TreeNode is not used, TreeBin is used, TreeNode is just a node of red black tree
                    // TreeBin holds references to red-black trees and locks them to ensure thread-safe operations
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        // If this is true, give oldVal the old value
                        // In putTreeVal, while recoloring a red-black tree
                        // Locks the root of the red-black tree
                        if((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) ! =null) {
                            oldVal = p.val;
                            if(! onlyIfAbsent) p.val = value; }}}}// If binCount is not empty and oldVal has a value, the value is successfully added
            if(binCount ! =0) {
                // Whether the linked list needs to be converted to a red-black tree
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if(oldVal ! =null)
                    return oldVal;
                // Slots are already locked, only if a new red-black tree or list fails to be added
                // Both additions are spins and almost never fail
                break; }}}// step5. check whether the container needs to be expanded. If it needs to be expanded, call the Transfer method
    // If the capacity is already being expanded, check whether the capacity is completed
    addCount(1L, binCount);
    return null;
}
Copy the code

4.2 Execution Process

1. If the array is empty, initialize it, and when done, go to 2
2. Calculates whether the current bucket bit has a value
   • If no, the CAS is created. After the CAS fails, the CAS spins until the CAS succeeds
   • Yes, 3
3. Check whether the bucket is a transfer node (Expansion ing)
   • If yes, keep spinning until the capacity expansion is complete and then add data
   • No, 4
4. If the bucket level has a value, add the synchronize lock to the current bucket level
   • Add nodes to the end of the linked list
   • Red black tree, red black tree version method added
5. After the addition is complete, check whether the capacity needs to be expanded

The implementation of the spin + CAS + Synchronize lock is ingenious and provides best practice for designing concurrent code.

5 Transfer-Expansion

Check whether expansion is required at the end of the PUT method and enter the Transfer method from the addCount method of the PUT method.

Basically create a new empty array and move and copy each element into the new array.

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    // Length of the old array
    int n = tab.length, stride;
    if ((stride = (NCPU > 1)? (n >>>3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; // subdivide range
    // If the new array is empty, initialize it with twice the size of the original array, n << 1
    if (nextTab == null) {            // initiating
        try {
            @SuppressWarnings("unchecked")
            Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n <<1];
            nextTab = nt;
        } catch (Throwable ex) {      // try to cope with OOME
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        nextTable = nextTab;
        transferIndex = n;
    }
    // The new array length
    int nextn = nextTab.length;
    // If the original array is a transfer node, the node is being expanded
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    boolean advance = true;
    boolean finishing = false; // to ensure sweep before committing nextTab
    // The I value decreases from the maximum value of the original array to 0
    for (int i = 0, bound = 0;;) {
        Node<K,V> f; int fh;
        while (advance) {
            int nextIndex, nextBound;
            // A flag to end the loop
            if (--i >= bound || finishing)
                advance = false;
            // The copy is complete
            else if ((nextIndex = transferIndex) <= 0) {
                i = -1;
                advance = false;
            }
            // Decrease the value of I each time
            else if (U.compareAndSwapInt
                     (this, TRANSFERINDEX, nextIndex,
                      nextBound = (nextIndex > stride ?
                                   nextIndex - stride : 0))) {
                bound = nextBound;
                i = nextIndex - 1;
                advance = false; }}// if any of the conditions are met, the copy is complete
        if (i < 0 || i >= n || i + n >= nextn) {
            int sc;
            // When a node is copied, the transfer node is added to the array, so the data of the copied node will not change again
            // The original array is found to be a transfer node, so it will not operate until the transfer node disappears
            // This means that once an array node is marked as a transition node, nothing will change, so there will be no thread-safety issues
            // So the assignment is straightforward, no problem.
            if (finishing) {
                nextTable = null;
                table = nextTab;
                sizeCtl = (n << 1) - (n >>> 1);
                return;
            }
            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, i)) == null)
            advance = casTabAt(tab, i, null, fwd);
        else if ((fh = f.hash) == MOVED)
            advance = true; // already processed
        else {
            synchronized (f) {
                // Copy the node
                if (tabAt(tab, i) == f) {
                    Node<K,V> ln, hn;
                    if (fh >= 0) {
                        int runBit = fh & n;
                        Node<K,V> lastRun = f;
                        for(Node<K,V> p = f.next; p ! =null; p = p.next) {
                            int b = p.hash & n;
                            if (b != runBit) {
                                runBit = b;
                                lastRun = p;
                            }
                        }
                        if (runBit == 0) {
                            ln = lastRun;
                            hn = null;
                        }
                        else {
                            hn = lastRun;
                            ln = null;
                        }
                        If the node has only one data, copy it directly. If the node is a linked list, loop several times to form a linked list copy
                        for(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)
                                ln = new Node<K,V>(ph, pk, pv, ln);
                            else
                                hn = new Node<K,V>(ph, pk, pv, hn);
                        }
                        // Place the copied value in the new array location
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        // Place the ForwardingNode node at the old array location
                        // Put: ForwardingNode: ForwardingNode: ForwardingNode
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                    // Copy of the red-black tree
                    else if (f instanceof TreeBin) {
                        // Copy red-black tree, same as HashMap, code ignored.// Place the ForwardingNode node at the old array location
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                }
            }
        }
    }
}
Copy the code

Execute the process

1. First, copy all the values of the original array to the new array, starting from the end of the array
2. When copying the slot points of the array, lock the slot points of the original array first. When successfully copying the slot points of the original array to the new array, assign the slot points of the original array to the transfer node
3. In this case, if new data needs to be put to the slot and the slot is found to be a transfer node, the slot is kept waiting. Therefore, data of the slot will not change before capacity expansion is complete
4. Copy from the end of the array to the head, each copy is successful, set the node in the original array as the transfer node until all the array data is copied to the new array, directly assign the new array to the array container, copy is complete.

6 summarizes

ConcurrentHashMap ConcurrentHashMap ConcurrentHashMap ConcurrentHashMap ConcurrentHashMap ConcurrentHashMap ConcurrentHashMap ConcurrentHashMap ConcurrentHashMap ConcurrentHashMap ConcurrentHashMap ConcurrentHashMap