“This is the third day of my participation in the First Challenge 2022, for more details: First Challenge 2022”.

ConcurrentHashMap is a multithreaded version of HashMap, which has various problems with concurrent operations, such as infinite loops and data overwriting. ConcurrentHashMap can be used to solve these problems. How does ConcurrentHashMap ensure thread safety? How is it implemented at the bottom? Let’s take a look.

JDK 1.7 underlying implementation

ConcurrentHashMap is implemented differently in different JDK versions,In JDK 1.7, it uses arrays and linked lists, which are divided into large arrays of segments and small arrays of HashEntry.MySQL > create a HashEntry list for MySQL > create a HashEntry list for MySQL > create a HashEntry list for MySQL > create a HashEntry list

JDK 1.7 thread-safe implementation

Now that you know the underlying implementation of ConcurrentHashMap, it’s easy to look at its thread-safe implementation. In JDK 1.7, ConcurrentHashMap is thread-safe by adding the element put method.

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    // Before writing to this Segment, make sure you get the lock
    HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value); 
    V oldValue;
    try {
        // Segment internal array
        HashEntry<K,V>[] tab = table;
        int index = (tab.length - 1) & hash;
        HashEntry<K,V> first = entryAt(tab, index);
        for (HashEntry<K,V> e = first;;) {
            if(e ! =null) {
                K k;
                // Update existing values...
            }
            else {
                // Place HashEntry into a specific position, and rehash if the threshold is exceeded
                // Ignore other code...}}}finally {
        / / releases the lock
        unlock();
    }
    return oldValue;
}
Copy the code

The Segment itself is based on ReentrantLock, which ensures that when multiple threads access the ConcurrentHashMap, only one thread can operate the corresponding node at the same time. This ensures thread-safe ConcurrentHashMap. In other words, the thread safety of ConcurrentHashMap is based on Segment lock, so we call it Segment lock or Segment lock, as shown in the following figure:

JDK 1.8 underlying implementation

In JDK 1.7, ConcurrentHashMap is thread-safe, but because its underlying implementation is array + list, it is slow to access when there is a lot of data, because it traverses the entire list. JDK 1.8 uses arrays + linked lists/red-black trees to optimize the implementation of ConcurrentHashMap.The rule for upgrading a list to a red-black tree: When the list length is greater than 8 and the array length is greater than 64, the list is upgraded to a red-black tree structure.

In JDK 1.8, ConcurrentHashMap retains the Segment definition, but this is only for serialization compatibility and is no longer structurally useful.

JDK 1.8 thread safety implementation

In JDK 1.8, ConcurrentHashMap uses CAS + volatile or synchronized to ensure thread safety.

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; K fk; V fv;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // The node is empty
            // Use CAS for lockless thread-safe operations if bin is empty
            if (casTabAt(tab, i, null.new Node<K,V>(hash, key, value)))
                break; 
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else if(onlyIfAbsent && fh == hash && ((fk = f.key) == key || (fk ! =null&& key.equals(fk))) && (fv = f.val) ! =null)
            return fv;
        else {
            V oldVal = null;
            synchronized (f) {
                   // Fine-grained synchronous modification operations...}}// If the threshold is exceeded, upgrade to red-black tree
            if(binCount ! =0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if(oldVal ! =null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}
Copy the code

As you can see from the above source code, in JDK 1.8, adding elements first determines whether the container is empty, and if so, initializes it with volatile plus CAS. If the container is not empty, the location is calculated according to the stored elements. If it is empty, CAS is used to set the node. If not empty, use Synchronize to lock the data in the bucket, replace or add nodes to the bucket, and then determine whether to convert to a red-black tree. This ensures thread-safe concurrent access. In JDK 1.8, ConcurrentHashMap uses locks on head nodes to ensure thread-safety. The granularity of locks is smaller than that of segments, and the frequency of collisions and locks is reduced, which improves the performance of concurrent operations. In addition, JDK 1.8 uses red-black tree to optimize the previous fixed list, so when the data volume is relatively large, the query performance is also greatly improved, from O(n) optimization to O(logn) time complexity, the specific locking diagram is as follows:

conclusion

ConcurrentHashMap is implemented as a data plus linked list in JDK 1.7, where arrays are divided into two classes: Large array segments and small array HashEntry. Locking is thread-safe by adding a ReentrantLock lock to the Segment. In JDK 1.8, ConcurrentHashMap uses arrays + linked lists/red-black trees. It is thread-safe through CAS or synchronized, and its lock granularity is smaller and query performance is higher.

Judge right and wrong from yourself, praise to listen to others, gain and loss in the number.

Public number: Java interview analysis

Collection of articles: gitee.com/mydb/interv…