1, Implementation principle of jdk8

The implementation of JDK8 has abandoned the Segment lock mechanism and used CAS+Synchronized to ensure the security of concurrent updates. The bottom layer still adopts the storage structure of array + linked list + red black tree.

 

2, Variable interpretation

1. table: null by default. Initialization occurs in the first insertion operation. The default size is an array of 16, which is used to store Node data. The size is always to the power of 2 during capacity expansion.

2. nextTable: null by default. The size of the newly generated array during capacity expansion is twice that of the original array.

3. sizeCtl: the default value is 0. It is used to control the initialization and capacity expansion of the table. The specific application will be reflected later.

*- 1 means that table is initializing

*- N indicates that N-1 threads are expanding

*Others:

*1. If the table is not initialized, it indicates the size of the table to be initialized.

*2. If the initialization of the table is completed, it indicates the capacity of the table. By default, it is 0.75 times the size of the table. This formula is actually used to calculate 0.75 (n - (n > > > 2)).

4. Node: a data structure that stores key, value and hash value of key.

5. ForwardingNode: a special Node with a hash value of - 1, where the reference of nextTable is stored. ForwardingNode only works when the table is expanded,

As a placeholder in the table, it indicates that the current node is null or has been moved.

 

3, Initialize

When instantiating ConcurrentHashMap with parameters, the size of the table will be adjusted according to the parameters. Assuming that the parameter is 100, it will eventually be adjusted to 256 to ensure that the size of the table is always the power of 2.

private static final int tableSizeFor(int c) {  
    int n = c - 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;  
}  

 

4, Initialize table

private final Node<K,V>[] initTable() {  
        Node<K,V>[] tab; int sc;  
        while ((tab = table) == null || tab.length == 0) {  
        //If a thread finds sizeCtl<0，Means that another thread executes CAS The operation is successful. The current thread only needs to give up cpu Time slice  
            if ((sc = sizeCtl) < 0)   
                Thread.yield(); // lost initialization race; just spin  
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {  
                try {  
                    if ((tab = table) == null || tab.length == 0) {  
                        int n = (sc > 0) ? 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;  
                }  
                break;  
            }  
        }  
        return tab;  
    }  

 

5, put operation

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;  
        for (Node<K,V>[] tab = table;;) {  
            Node<K,V> f; int n, i, fh;  
            if (tab == null || (n = tab.length) == 0)  
                tab = initTable();  
            // table Locate the index position in the, n yes table Size of
            // If f by null，explain table The element is inserted for the first time at this position in Unsafe.compareAndSwapObject Method insertion Node Node.
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {  
                
                // If CAS Success, description Node The node has been inserted, and then addCount(1L,binCout)Method will check whether the current capacity needs to be expanded. If CAS Failure indicates that another thread has inserted the node in advance. Try to insert the node at this position again.
                if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))  
                    break; // no lock when adding to empty bin  
            }  
            // If f of hash Value is-1，Description current f yes ForwardingNode Node, which means that other threads are expanding capacity, then expand capacity together.
            else if ((fh = f.hash) == MOVED)  
                tab = helpTransfer(tab, f);  
            //Omit some codes  
        }  
        addCount(1L, binCount);  
        return null;  
    }  

 

6, hash algorithm

static final int spread(int h) {return (h ^ (h >>> 16)) & HASH_BITS;}

 

7, Get the corresponding element f in table

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);
}

Doug Lea uses unsafe Getobjectvolatile. Some people may question whether it's OK to directly table[index]. Why is it so complicated?

In the java memory model, we already know that each thread has a working memory, which stores a copy of the table. Although the table is modified by volatile,

But there is no guarantee that the thread will get the latest element in the table every time, unsafe Getobjectvolatile can directly obtain the data in the specified memory, ensuring that the data is up-to-date every time.

 

8, Linked list or red black tree operation

In other cases, insert the new Node into the appropriate position in the form of linked list or red black tree. This process adopts synchronous built-in lock to realize concurrency.

synchronized (f) {
    // At node f Before the node is inserted, it is used again tabAt(tab, i) == f Judge to prevent it from being modified by other threads. 
    if (tabAt(tab, i) == f) {
        // If f.hash >= 0，explain f Is the head node of the linked list structure. Traverse the linked list. If you find the corresponding node Node, modify value，Otherwise, add nodes at the end of the linked list.
        if (fh >= 0) {
            binCount = 1;
            for (Node<K,V> e = f;; ++binCount) {
                K ek;
                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;
                if ((e = e.next) == null) {
                    pred.next = new Node<K,V>(hash, key,
                                              value, null);
                    break;
                }
            }
        }
        // If f yes TreeBin Type node, description f If it is the root node of the red black tree, traverse the elements on the tree structure and update or add nodes.
        else if (f instanceof TreeBin) {
            Node<K,V> p;
            binCount = 2;
            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                           value)) != null) {
                oldVal = p.val;
                if (!onlyIfAbsent)
                    p.val = value;
            }
        }
    }
}
// If the number of nodes in the linked list binCount >= TREEIFY_THRESHOLD(The default is 8)，Then the linked list is transformed into a red black tree structure.
if (binCount != 0) {
    if (binCount >= TREEIFY_THRESHOLD)
        treeifyBin(tab, i);
    if (oldVal != null)
        return oldVal;
    break;
}

 

9, table expansion

When the table capacity is insufficient, that is, the number of elements of the table reaches the capacity threshold sizeCtl, the table needs to be expanded.

The whole expansion is divided into two parts:

1. Build a nextTable that is twice the size of the table.

2. Copy the data of table to nextTable.

These two processes are simple to implement in a single thread, but concurrent HashMap supports concurrent insertion, and the expansion operation will naturally occur concurrently. In this case,

The second step can support concurrent replication of nodes, which naturally improves the performance, but the complexity of implementation has also increased to a higher level.

Let's look at the first step and build nextTable. There is no doubt that only a single thread can initialize nextTable in this process. The specific implementation is as follows:

private final void addCount(long x, int check) {  
        // Omit some codes  
        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();  
            }  
        }  
    }  

 

10, get operation

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) {
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0) // tree
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) { // Linked list
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}