Map

01 / HashMap

In JDK8, the bottom layer of HashMap is realized by "array + linked list + red black tree". When learning the principle of HashMap, we should focus on its data structure, put process and capacity expansion mechanism.

Source code interpretation:

Data structure:

At the beginning, it must be array + linked list, and when it reaches a certain scale, it will be transformed into a tree.

The tree node inherits the linked list node and retains the characteristics of the linked list when the data structure is a tree. It is very easy to change from a tree to a linked list.

transient Node<K,V>[] table;//Array of Node type (each Node in the array can be a one-way linked list)
//Node, single linked list
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    . . . 
}
//Tree structure (TreeNode indirectly inherits Node)
static final class TreeNode<K,V> extends LinkedHashMap.Entry<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) {
            super(hash, key, val, next);
        }
}

1.1 process of put()

1. If the array is empty, it will be expanded for the first time.

2. If the head node at the ith position of the array is empty (the linked list does not exist), a new linked list node will be created.

3. If the head node at the ith position of the array is not empty (a linked list or tree already exists), insert the element into the slot.

• If the element is equal to the header node (key), it is directly overwritten;
• If the element is a tree node, it is added to the tree;
• If the element is a linked list node and the length of the linked list is less than 8, it will be added to the linked list
• If the element is a linked list node and the length of the linked list reaches 8, expand the capacity or turn it into a tree, and then add the element;

4. If the number of elements exceeds the threshold, the capacity will be expanded again.

Source code interpretation:

public V put(K key, V value) {
    //First calculate the hash value of the key and take the module of the array as the subscript
        return putVal(hash(key), key, value, false, true);
    }
//DP Hash 
static final int hash(Object key) {
        int h;
    //Take the hashCode() of the key first, and then move the result of hashCode on XOR to the right by 16 bits
    //Do XOR operation between high and low to reduce the probability of collision
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
     //1. Array is empty
        if ((tab = table) == null || (n = tab.length) == 0)
            //Initial expansion
            n = (tab = resize()).length;
     //Calculate the position of the element (hash function and array length and operation), and obtain when the header node is empty
        if ((p = tab[i = (n - 1) & hash]) == null)
            //Create linked list node
            tab[i] = newNode(hash, key, value, null);
        else {//When neither array nor header node is empty
            Node<K,V> e; K k;
            //If the passed in key and the header node are equal
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //cover
                e = p;
            else if (p instanceof TreeNode)//If the head node is a tree
                //Add elements to the tree
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {//It is neither a head node nor a tree, that is, a linked list
                for (int binCount = 0; ; ++binCount) {
                    //If the subsequent node bit of the head node is null
                    if ((e = p.next) == null) {
                        //Create a new node and insert it behind the linked list
                        p.next = newNode(hash, key, value, null);
                        //After inserting the data, check whether the length is greater than or equal to 8-1
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //Convert to tree (judge whether to expand or convert to tree)
                            treeifyBin(tab, hash);
                        break;
                    }
                    //During traversal, it is found that an element is equal to the current element (i.e. a node already exists)
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //The value of the processing node. The above is the location of the processing node
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                //Allow updating existing values
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;//Update the value of the node
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;//Increase modification quantity
        if (++size > threshold)//Is the array size greater than the threshold
            resize();//Capacity expansion
        afterNodeInsertion(evict);
        return null;
    }

When the length of the linked list reaches 8, first judge whether the length of the array is greater than 64. If it is greater than 64, it will be transformed into a tree. If it is less than 64, expand the capacity first

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //Determine array length and 64 size
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();//Capacity expansion
    //Convert linked list to tree
    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)
            hd.treeify(tab);
    }
}

hashCode(): used to determine where to put it

static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;

1.2 capacity expansion mechanism

The default capacity is 16. Double the capacity every time you expand the capacity. The capacity must be to the nth power of 2
16 = 00010000, 32 = 00100000
hash & (16-1) = hash & 00001111
hash & (32-1) = hash & 00011111
After doubling and capacity expansion, the calculated index value is one more bit,
If this bit is 0, the position remains unchanged, otherwise the position is + 16.

What about moving the data location? Recalculate? no The node is either in the original slot or in the position of the original slot + 16 (the first 16 low-level slots and the last 16 high-level slots)

Source code interpretation:

 int threshold;  //Artificially specified capacity
final float loadFactor; //The default value of load factor is 0.75

//constructor 
public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

//The default value of load factor is 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//Constructor with specified capacity
 public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
//
 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; //Initialize load factor
        this.threshold = tableSizeFor(initialCapacity);//Initialize capacity for processing
    }

//Convert the artificially specified capacity calculation to the nth power of close to 2
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;
    }

Expansion source code:

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) {
        //Determine whether the old capacity exceeds the maximum
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //When the maximum capacity is not reached, the new capacity is twice the old capacity
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    //Old threshold
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        //Give a default capacity of 16
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {//When capacity bit 0 is specified
        //critical value
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    //Reinitialize the new array. The above is the double expansion mechanism, and the following is the migration mechanism
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;//Assign a new array
    //The previous array is not empty. Traverse the old bucket
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;//Empty old tub
                if (e.next == null)//When the head node of the current slot has no successor
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)//If the head node is a tree
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);//Add to tree
                else { // preserve order is not a tree, it is a linked list
                    //Head and tail nodes of low-level slot
                    Node<K,V> loHead = null, loTail = null;
                    //Head and tail nodes of high-level slot
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    //The position of the distribution slot, in the low-level slot or in the high-level slot
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {//Low level slot
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {//High level slot
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    //Locate the position in front and start moving the data below
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;//Put the low position in the original position
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;//Place the high position at the original + doubled capacity position
                    }
                }
            }
        }
    }
    return newTab;
}

Tree migration in migration mechanism

It is also to allocate node locations first, and then link nodes to the tree

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
            TreeNode<K,V> b = this;
            // Relink into lo and hi lists, preserving order
    //Low high slot node
            TreeNode<K,V> loHead = null, loTail = null;
            TreeNode<K,V> hiHead = null, hiTail = null;
            int lc = 0, hc = 0;
    //Ergodic iteration
            for (TreeNode<K,V> e = b, next; e != null; e = next) {
                //Next is a one-way linked list pointing to the next node, not a red black tree. The tree is iterated as a linked list (although it is a tree, the pointing relationship of the linked list remains)
                next = (TreeNode<K,V>)e.next;
                e.next = null;
                if ((e.hash & bit) == 0) {
                    if ((e.prev = loTail) == null)
                        loHead = e;
                    else
                        loTail.next = e;
                    loTail = e;
                    ++lc;
                }
                else {
                    if ((e.prev = hiTail) == null)
                        hiHead = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                    ++hc;
                }
            }

            if (loHead != null) {//Low non empty
                //The length of the linked list is less than or equal to 6
                if (lc <= UNTREEIFY_THRESHOLD)
                    //Convert tree to linked list
                    tab[index] = loHead.untreeify(map);
                else {
                    tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                        loHead.treeify(tab);
                }
            }
            if (hiHead != null) {//High non empty
                if (hc <= UNTREEIFY_THRESHOLD)
                    tab[index + bit] = hiHead.untreeify(map);
                else {
                    tab[index + bit] = hiHead;
                    if (loHead != null)
                        hiHead.treeify(tab);
                }
            }
        }

static final int UNTREEIFY_THRESHOLD = 6;//If the length of the linked list is less than or equal to 6, turn the tree into a linked list

When will red and black trees degenerate into linked lists?

During capacity expansion, when a tree in the old array is moved to the new array, the length of the original red and black tree is less than or equal to 6 after it is disassembled (part in the low position and part in the high position), and it will degenerate into a linked list

1.3 query mechanism

1. When querying, locate the slot first, and then iterate the linked list or tree from the slot to find the corresponding node;
2. During iteration, first traverse the slot, then traverse the linked list or tree in the slot, and traverse all nodes.

Source code interpretation:

get

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

//
final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //Find the position of the head node according to the key
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {//Get header node

            if (first.hash == hash && // always check first node
                //Judge whether the key you pass in is equal to the key of the header node
                ((k = first.key) == key || (key != null && key.equals(k))))
                //Equal returns the header node
                return first;
            //Unequal iteration
            if ((e = first.next) != null) {
                //Iterative linked list
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

Iteration key

public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}

//
 final class KeySet extends AbstractSet<K> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
     //iterator 
        public final Iterator<K> iterator()     { return new KeyIterator(); }
       . . . . . . 
        
    }

//Concrete iterator
final class KeyIterator extends HashIterator//inherit
        implements Iterator<K> {
        public final K next() { return nextNode().key; }
    }

//Parent iterator
abstract class HashIterator {
        Node<K,V> next;        // next entry to return
        Node<K,V> current;     // current entry
        int expectedModCount;  // for fast-fail
        int index;             // current slot

        HashIterator() {
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            //Traverse the slot from scratch
            if (t != null && size > 0) { // advance to first entry
                //First non empty slot found
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }

        public final boolean hasNext() {
            return next != null;
        }

    //Find next node
        final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            if ((next = (current = e).next) == null && (t = table) != null) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

        . . . . . 
    }

1.4 relevant parameters

It doesn't mean that if the length of the linked list reaches 8, it will be transformed into a tree. It also depends on whether the length of the array reaches 64

02 / TreeMap

The bottom layer of TreeMap is implemented by red black tree structure. When inserting elements, it needs to be compared. TreeMap allows elements to be compared through the default comparator or the specified comparator. These two comparison methods are called natural sorting and custom sorting respectively. Data structure and sorting rules are the key contents to be paid attention to when learning TreeMap.

Source code interpretation:

 private transient Entry<K,V> root;//Root node Entry of the tree

// Entry structure red black tree
static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;//Identification of color
}

comparator

 private final Comparator<? super K> comparator;

//The default constructor initializes the comparator to null, so that the method provided by the element can be sorted naturally
public TreeMap() {
        comparator = null;
    }

//Pass in the constructor you specified to customize the sorting
 public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

//The key of the comparison rule TreeMap must implement the Comparable interface!!!
final int compare(Object k1, Object k2) {
    //If the comparator is empty, the two key s are compared. If it is not empty, custom sorting is used
        return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
    }

put

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        //Purpose to use this method to check the key. The key may be null or does not implement the Comparable interface
        compare(key, key); // type (and possibly null) check

        //When the root node is empty, initialize the root node first
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {//Comparator is not empty, custom sorting
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {//Natural sorting
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);//Comparison using custom comparator
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    Entry<K,V> e = new Entry<>(key, value, parent);
    //Add data
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

01 / sync collection

The Collections class provides multiple synchronizexXxx() methods, which can wrap the specified collection into a thread synchronized collection, so as to solve the thread safety problem when multiple threads access the collection concurrently.

Collections is a tool class and Collection is an interface

public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
    return new SynchronizedCollection<>(c);
}

 static class SynchronizedCollection<E> implements Collection<E>, Serializable {
        private static final long serialVersionUID = 3053995032091335093L;

        final Collection<E> c;  // Backing Collection
        final Object mutex;     // Object on which to synchronize

        SynchronizedCollection(Collection<E> c) {
            this.c = Objects.requireNonNull(c);
            mutex = this;
        }

        SynchronizedCollection(Collection<E> c, Object mutex) {
            this.c = Objects.requireNonNull(c);
            this.mutex = Objects.requireNonNull(mutex);
        }
     
       public int size() {
            synchronized (mutex) {return c.size();}
        }
. . . . . 
 }

Note: the Collection does not lock all methods. The iterative method does not lock and needs to lock itself

Summary: use the synchronizexXxx() method of Collections to turn a Collection into a thread safe Collection. Almost all methods will be locked, but the iterative methods of Collection are not locked

02 / invariant set

Collections provides the following three types of methods to return an immutable Collection. The parameters of these three types of methods are the original Collection object, and the return value is the "read-only" version of the Collection. Through the three types of methods provided by collections, a "read-only" Collection or Map can be generated.

• emptyxxx(): returns an empty immutable collection object;
• singletonx): returns an immutable collection object containing only the specified object;

• Unmodifiablexxxxx(): returns the immutable view of the specified collection object.

Immutable. It is thread safe at this time, and it can also solve the problem of concurrent thread safety

Collection under JUC package

brief introduction

01 / CopyOnWriteArrayList

As its name implies, CopyOnWriteArrayList implements write operations by copying the underlying array. When a thread performs a read operation on the CopyOnWriteArrayList collection, the thread will directly read the collection itself without locking and blocking.
When a thread writes to the copyonwritearraylist collection, the collection will copy a new array at the bottom, and then write to the new array. Since the copyonwritearraylist collection writes to a copy of the array, it is line safe.
It should be noted that CopyOnWriteArrayList has poor performance because it needs to copy arrays frequently when performing write operations. However, since the read operation and write operation are not the same array, and the read operation does not need to be locked, the read operation is fast and safe. Therefore, CopyOnWriteArrayList is suitable for scenarios where the read operation is much larger than the write operation , such as caching, etc.

Source code interpretation:

final transient ReentrantLock lock = new ReentrantLock();//With reentrant lock
private transient volatile Object[] array;//The bottom layer is an array

//default constructor 
 public CopyOnWriteArrayList() {
        setArray(new Object[0]);//Initialization array length is 0
    }
//Pass in an array. Now copy the array
public CopyOnWriteArrayList(E[] toCopyIn) {
        setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
    }

The get read method is unlocked

public E get(int index) {
    return get(getArray(), index);
}
 private E get(Object[] a, int index) {
        return (E) a[index];
    }

Modify operation (lock when copying array)

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        //Copy array
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        //Replace original array
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

Iterative method

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
}

static final class COWIterator<E> implements ListIterator<E> {
        /** Snapshot of the array */
        private final Object[] snapshot;
        /** Index of element to be returned by subsequent call to next.  */
        private int cursor;

    //Assign the original array to snapshot (iterative copy)
        private COWIterator(Object[] elements, int initialCursor) {
            cursor = initialCursor;
            snapshot = elements;
        }

Summary: CopyOnWriteArrayList is not mutually exclusive in reading and writing (solved through the copy array), but is mutually exclusive in writing (because a lock is added to the writing)

02 / ConcurrentHashMap

Implementation method in JDK 7:
In order to improve concurrency, in JDK 7, a HashMap is divided into multiple sub hashmaps. Each sub HashMap is called a Segment (reducing lock granularity), and multiple threads operate multiple segments independently of each other. The segmentation lock in JDK 7 has three advantages:

1. Reduce Hash conflicts and avoid too many elements in a slot.

2. Improve the concurrency of reading and writing, and segments are independent of each other.

3. The concurrency of capacity expansion is improved. Instead of expanding the entire ConcurrentHashMap, each Segment is expanded independently.

Each slot stores segments, and each segment stores a HashMap.

Summary: lock in sections

Implementation method in JDK 8:
There are great changes in the implementation of JDK 8. First, there is no segment lock, and all data is placed in a large HashMap. Second, a red black tree is introduced. If the head Node is a Node type, it is followed by an ordinary linked list. If the head Node is a TreeNode type, its back is a red black tree, and TreeNode is a subclass of Node. The advantages of this implementation are:

1. Using the red black tree, when there are many elements in a slot, its query and update speed will be much faster than the linked list, and the problem of Hash conflict can be better solved.
2. The granularity of locking is not the entire ConcurrentHashMap, but each head Node is locked separately, that is, the degree of concurrency, that is, the length of the Node array. The initial length is 16, which is the same as the number of initial segments in JDK 7.

3. Concurrent capacity expansion is the most difficult. In JDK7, once the number of - segments is established during initialization, it cannot be changed, and the concurrency is fixed. After that, it is only expanded within each Segment, which means that each Segment is expanded independently, does not affect each other, and there is no problem of concurrent capacity expansion. However, in jdk8, it is equivalent to only one Segment, when a thread wants to expand a Node Array, other threads have to read and write, so the processing process is very complex.

Node (linked list) and TreeNode (tree) can be stored in each slot

Source code interpretation:

//Two table s
transient volatile Node<K,V>[] table;//An array of storage elements
 private transient volatile Node<K,V>[] nextTable;//table used during capacity expansion

private transient volatile int sizeCtl;//Control the initialization and capacity expansion mechanism

//constructor 
 public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
        this.sizeCtl = DEFAULT_CAPACITY;//Default capacity 16
        putAll(m);
    }
//The constructor of the specified capacity converts the specified number to the nth power close to 2
 public ConcurrentHashMap(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));//Expand capacity to 1.5x
        this.sizeCtl = cap;
    }

//
 public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel) {
     //
        if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
     //Initial capacity < concurrency level (number of concurrent threads, computer cores)
        if (initialCapacity < concurrencyLevel)   // Use at least as many bins
            //Increase the specified capacity to the number of computer cores
            initialCapacity = concurrencyLevel;   // 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;
    }

put

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    //Iterative array
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        //The array is empty
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();//Initialize array
        //If the head node at position i is empty
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            //Create a new node and save it
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        //If the header node is not empty: judge that the hsah value of the header node is - 1 (migrating to a new array during capacity expansion)
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);//To help with capacity expansion and data migration
        else {//The header node is not empty and is not migrating: data can be saved
            V oldVal = null;
            synchronized (f) {//Lock the head node!!!!
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {//hash of the head Node = 0 (ordinary Node, linked list, add the number to the linked list)
                        . . . . 
                            }
                        }
                    }
                    //The node is a tree. Add the number to the tree
                    else if (f instanceof TreeBin) {
                        . . . 
                        }
                    }
                }
            }
            //After adding the number, judge whether the length of the linked list has reached the threshold
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    //Judge whether the element length of the array has reached the threshold (3 / 4)
    addCount(1L, binCount);
    return null;
}

Points that may cause capacity expansion during put:

1. tab = helpTransfer(tab, f); / / help with capacity expansion and data migration

2. treeifyBin(tab, i); / / when converting to a tree, first look at the array capacity. Do you want to expand it

3. addCount(1L, binCount); / / judge whether the element length of the array reaches the threshold (3 / 4)

addCount

private final void addCount(long x, int check) {
  . . . . . 
                transfer(tab, null);//Real capacity expansion
            s = sumCount();
        }
    }
}

Real capacity expansion mechanism

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    //Step size, calculate how many nodes each cpu processes
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; // subdivide range
    //Construct a new array before migration
    if (nextTab == null) {            // initiating
        try {
            @SuppressWarnings("unchecked")
            //The capacity of the new array is 2x
            Node<K,V>[] nt = (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;
    //Forwarding node. When querying the old array, save the node corresponding to the new array
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    boolean advance = true;
    boolean finishing = false; // to ensure sweep before committing nextTab
    
    for (int i = 0, bound = 0;;) {//bound is the boundary
        . . . 
            //Grab the task in the way of CAS
            else if (U.compareAndSwapInt
                     (this, TRANSFERINDEX, nextIndex,
                      nextBound = (nextIndex > stride ?
                                   nextIndex - stride : 0))) {
                bound = nextBound;
                i = nextIndex - 1;
                advance = false;
            }
        }
        //The whole collection is traversed
        if (i < 0 || i >= n || i + n >= nextn) {
            int sc;
            if (finishing) {//Transfer complete
                nextTable = null;
                table = nextTab;//Replace the old array
                sizeCtl = (n << 1) - (n >>> 1);//Calculate again as the threshold for the next expansion
                return;
            }
            . . . . 
        }
        //The ith location is empty (the migration has been completed)
        else if ((f = tabAt(tab, i)) == null)
            advance = casTabAt(tab, i, null, fwd);//Set the old array as the forwarding node
        else if ((fh = f.hash) == MOVED)//Migrating
            advance = true; // already processed
        else {
            synchronized (f) {//Lock the head node and move the number of plays
                if (tabAt(tab, i) == f) {
                    Node<K,V> ln, hn;
                    if (fh >= 0) {//Description is a linked list, copy several plays
                        . . . . 
                    }
                    else if (f instanceof TreeBin) {//It means that the red and black tree plays
                        . . . 
                    }
                }
            }
        }
    }
}

Initialize array

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    //If the array is empty, initialize
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0)//Determine whether other threads are initializing the array
            Thread.yield(); // lost initialization race; just spin, the thread makes a concession and turns to the ready state
        //Initialize the array as CAS
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    //Array initialized to or default
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    //Change, 3 / 4 of the original value, the key node for the next expansion
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

Summary of ConcurrentHashMap mechanism:

• Initial operation: initialize the array and header node in CAS mode;
• Insert node: lock when inserting a node at a certain location;
• Capacity expansion: each thread is responsible for expanding part of the data, and locking is performed during capacity expansion. In addition, read and write operations are still supported during capacity expansion. If the node at this location is not fwd, read and write directly. Otherwise, access the new array for reading and writing.