[Interview-oriented learning] How does ConcurrentHashMap implement concurrent access?

[Interview-oriented learning] How does ConcurrentHashMap implement concurrent access?

Preface

Before reading this article, it s best to look at several aspects on Baidu. The following aspects are not within the scope of this article, but they will be cited

  1. HashMap before Java 8
  2. HashMap after Java8
  3. ConcurrentHashMap before Java 8
  4. ConcurrentHashMap after Java8
  5. Lock-free CAS operation, Java UnSafe
  6. volatile, synchronized keywords

Concurrency point

The reason why Java introduces ConcurrentHashMap is to solve the problem of data abnormalities when operating a HashMap at the same time in a multi-threaded scenario. The commonly used operations are mainly the following operations

  • put adds data to the map
  • resize map expansion
  • addCount count
  • replace replaces a data in the map
  • remove removes objects in the map
  • clear clears one or all objects in the map

In fact, if you refine it, there are three points

  • Addition, deletion and modification operations These are all write operations to the map, so multithreading must be considered
  • Expansion operations For the storage data structure, the overall copy and replication must be considered
  • Counting operations Additions and deletions will inevitably affect counting

detailed analysis

Add, delete and modify operations

The thread safety mechanism imposed by ConcurrentHashMap on additions, deletions and modifications is similar. Take the Put method as an example below

public void put(K key, V value){

  1. Judge whether K and V are not empty, ConcurrentHashMap requires that KV cannot be empty
  2. Calculate the hash value based on K
  • Node array infinite loop begins
  1. If the Node array is empty, initialize this array. During initialization, if a thread enters Thread.yield(), let it wait. At the same time, use UnSafe.compareAndSwapInt to ensure multi-thread safety when initializing the array. The Node and Hashmap Node are mainly The difference is that val and next are volatile to ensure thread visibility
  2. After the initial tens of thousands array or the array is not null, use UnSafe.getObjectVolatile to query whether the array location pointed to by hash is empty, if it is empty, insert the Node composed of this KV into the Node array through UnSafe.compareAndSwapObject
  3. If the previous UnSafe query found that the location is not empty, there is a node, and the hash value is negative, then come here to enter the expansion process
  4. If the hash value of the previous step is positive, synchronized (f) and f are the hash values, here is a search for the linked list corresponding to this node. Since it is synchronized as soon as it comes up, the subsequent operations are thread-safe. According to K in the linked list of this Node If there is the same K, if it covers V, if not, add a Node store to the linked list. After Jdk1.8, the linked list may be longer than 8, which needs to be converted to a red-black tree, and the number of tree summary points is less At 6 o'clock, the operation of re-converting to a linked list
  • End of Node array infinite loop
  1. map counter +1

}

After talking about the logic of the Put method, we can see that there are many special operations for multi-threaded operations, which are mainly used. UnSafe provides the underlying method, and uses CAS to query and add changes to the array. CAS is very different from locks. The thread processing method is more efficient, and the common synchronized is also used. This keyword has been optimized for many times and has good performance. You can check the remove and clear methods yourself, and the general logic is similar.

Refer to java1.8 ConcurrentHashMap for detailed understanding