Talk a little bit about ConcurrentHashMap

preface

This paper studies the basic principle analysis of ConcurrentHashMap with B station

This article will briefly cover some of the interview questions for understanding ConcurrentHashMap, but will not be particularly in-depth

If you are not familiar with HashMaps, you may want to read my other blog post, “A Little Talk about HashMaps”, before reading this article.

How does ConcurrentHashMap work?

Jdk7 principle

The ConcurrentHashMap in JDK7 consists of segments and hashentries. That is, the ConcurrentHashMap splits the hash bucket array into smaller arrays, each consisting of N Hashentries.

Partition into several small array segments and lock each Segment. This is called Segment locking

Data is divided into sections of storage, and each section of data is assigned a lock. When a thread uses the lock to access one section of data, the number of other sections

Data can also be accessed by other threads to achieve concurrent access.

Jdk8 principle

ConcurrentHashMap uses the same structure as hashMap 1.8: array + linked list + red-black tree

In the implementation of lock, CAS + synchronized is used to achieve more fine-grained lock, abandoning the original Segment lock. The level of locking is controlled at the level of finer grained hash bucket elements. Only the head node (root node of red-black tree) of the list is locked, which does not affect the read and write of other hash bucket elements, greatly improving the concurrency.

Does the get method need to be locked? Why is that?

The get method does not need to be locked

The volatile keyword is used to ensure memory visibility

In a multi-threaded environment, changing the value of a node and adding nodes are visible to other threads

(HashEntry in 1.7 uses volatile to modify value and next in the same way.)

    static class Node<K.V> implements Map.Entry<K.V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
    }
Copy the code

What is the reason why ConcurrentHashMap does not support null key or value?

ConcurrentHashmap HashMap and Hashtable are key-value storage structures, One difference is that ConcurrentHashmap and Hashtable do not support keys or null values, whereas HashMap does

ConcurrentHashmap and Hashtable are both concurrent, so there’s a problem with that. When you get a value from get(k), you can’t tell if it’s null. If it’s put (k,v), the value is null. Again, this key has never been mapped.

HashMap is non-concurrent and can be further analyzed by using contains(key) to make this determination

ConcurrentHashmap and Hashtable that support concurrent searches may have different m values when calling m.contains (key) and m.et (key)

Is the ConcurrentHashMap iterator strongly consistent or weakly uniform?

Unlike the HashMap iterator, which is strongly consistent, the ConcurrentHashMap iterator is weakly consistent.

Once created, the iterator to ConcurrentHashMap iterates through each element in a hash table structure

However, during traversal, internal elements can change, and if the change occurs in an already traversed part, the iterator will not reflect it

If the change occurs in an untraversed part, the iterator will detect and reflect it, which is weak consistency.

In this way, the iterator thread can use the original old data, while the writer thread can also complete the change concurrently, ensuring the continuity and scalability of the concurrent execution of multiple threads, which is the key to performance improvement.

What is the difference between THE ConcurrentHashMap in JDK 7 and JDK 8?

Underlying data structure

  • The underlying data structure of JDK7 is an array + linked list organized using segments
  • In JDK8, instead of an array + list + red-black tree structure, the linked list will be converted into a red-black tree for storage when the number of linked list nodes is greater than 8 (and the total number of data is greater than or equal to 64)

Query time Complexity

  • Traversal list O(n) for JDK7
  • JDK8 becomes traversal red black tree O(logN)

Ensure thread-safety mechanism

  • JDK7 uses Segment locking mechanism to achieve thread safety, where segments inherit from ReentrantLock
  • JDK8 adopts CAS+synchronized to ensure thread safety

The granularity of the lock

  • JDK7 locks segments that require data manipulation
  • JDK8 adjusts to lock the head node of each array element

Why does synchronized replace ReentrantLock in JDK 8?

Improved synchronized performance

In JDK6, a large number of optimizations are introduced for synchronized lock implementation, such as lock expansion optimization and adaptive spin elimination of coarse lock with lock, which can be converted step by step from no lock -> biased lock -> lightweight lock -> heavyweight lock

Improves concurrency and reduces memory overhead

In CAS + synchronized mode, the locked object is the head node of each chain, which improves the concurrency relative to the Segment

Using a ReentrantLock to achieve the same effect would require a large number of objects inherited from ReentrantLock, resulting in a huge memory waste.

How is the concurrency of ConcurrentHashMap designed?

Concurrency can be interpreted as the maximum number of threads that can simultaneously update ConcurrentHashMap while the program is running without lock contention

In JDK7, this is actually the number of Segment locks in ConcurrentHashMap. The length of the Segment[array is 16 by default. This value can be set in the constructor.

If you set your own concurrency, ConcurrentHashMap uses the lowest power of 2 greater than or equal to that value as the actual concurrency

Setting concurrency too low can cause serious lock contention problems

If the concurrency is set too high, access in the same Segment will spread to different segments, resulting in application performance degradation

Because of the limitations and problems, we optimized jdK8 to lock header nodes instead of segment and segment locking

Which is more efficient, ConcurrentHashMap or Hashtable? Why is that?

ConcurrentHashMap is more efficient than Hashtable

Because Hashtable locks the entire Hashtable, it is thread-safe

ConcurrentHashMap has a lower lock granularity

  • Section lock of 1.7
  • 1.8 CAS+Synchronized locks

Are there other ways to safely manipulate maps in multiple threads?

Use Hashtable instead

Create a Hashtable that locks the entire table

Map<String, String> hashtable = new Hashtable<>();
Copy the code

Use the Collections. SynchronizedMap to synchronizedMap

The Collections synchronizedMap converts the HashMap to thread-safe synchronizedMap

It is also essentially locked on the full table, which is not as efficient as ConcurrentHashMap

        HashMap<String, String> map = new HashMap<>();
        Map<String, String> synchronizedMap = Collections.synchronizedMap(map);
Copy the code