Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

What is ConcurrentHashMap? ConcurrentHashMap, which is an implementation of the Map in the Java collection, is a thread-safe version of the hash table, and even thread-safe versions,

The performance of ConcurrentHashMap is also impressive. However, in different JDK versions, its implementation is not the same, this article is mainly based on jdK1.8 implementation discussion.

ConcurrentHashMap is a thread-safe and efficient HashMap.

Why use ConcurrentHashMap?

1 Thread-unsafe HashMap(in a multi-threaded environment, using HashMap to put causes an infinite loop, resulting in CPU utilization approaching 100%)

2 Inefficient HashTable(The HashTable container uses synchronized to ensure thread-safety, but HashTable is very inefficient in the context of hotly contested threads)

3ConcurrentHashMap can effectively improve the concurrent access rate.

ConcurrentHashMap structure

ConcurrentHashMap consists of a Segment array structure and a HashEntry array structure.

Segment is a ReentrantLock that acts as a lock in a ConcurrentHashMap.

A ConCurrentHashMap contains an array of segments.

Segment is an array and linked list structure similar to a HashMap.

HashEntry is used to store key-value pair data.

Initialize the

ConcurrentHaspMap initializes the segments array, segmentShift, and concurrencyLevel using initialCapacity, loadFactor, and concurrencyLevel. The segmentMask and the HashEntry array in each segment

The segments array must be power-of-two size in order to locate the index of a segment array using a bitwise and hash algorithm. So the segments array must be calculated with a minimum value of 2 to the NTH power greater than or equal to concurrencyLevel. If concurrencyLevel is equal to 14,15, or 16, ssize will be 16, which means the number of locks in the container will be 16

Note that the maximum size of concurrencyLevel is 65535, which means that the segments array is 65536 bytes long and the corresponding binary is 16 bits

ConcurrentHaspMap operation

Get operation (unlocked)

The implementation of the segment get operation is very simple and efficient. It hashes once and then uses the hash value to locate the segment and then the hash algorithm to locate the element.

(1) Determine which segment the key-value pair is in

Select TAB [index] from TAB [index]

(3) Traverse the linked list to find the specified key

The steps of the get method are as follows: 1. Calculate the hash value of the key and locate the table index. 2. 3. If the element under the table index is a red-black TreeBin node, use the red-black tree method to find the element.

The put operation adds a key-value pair.

Because the put method writes to shared variables, locks must be placed when operating on shared variables for thread safety. The put method first locates the Segment and then inserts it into the Segment

Size operation (first try not locking, then try locking)

If you want to count the size of elements in the entire ConcurrentHashMap, you must count the size of elements in all segments and sum them.

Example:

import java.util.Map; import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.CountDownLatch; Public class MyConcurrentMashMapTest {public static void main(String[] arg) {ConcurrentHashMap Map<String,Integer> count=new ConcurrentHashMap<>(); //CountDownLatch can be viewed as a counter, except that its operation is atomic and the latch can only be operated by one thread. CountDownLatch endLatch = new CountDownLatch(3); Runnable runnable=new Runnable() { @Override public void run() { Integer oldvalue; for(int i=0; i<5; i++) { // Integer value = count.get("123"); If (null == value) {// Add key/value pair count.put("123", 1); } else { count.put("123", value + 1); // CountDownLatch(3); // CountDownLatch(3); The number of this counter is reduced by 1 endlatch.countdown (); }}; //new CountDownLatch(3); New Thread(runnable).start(); new Thread(runnable).start(); new Thread(runnable).start(); Try {// This method is used to block the current thread until count decreases to 0 and then resumes execution. Await method is used to get the synchronization value and returns successfully if it is 0. If it is less than 0, check again if it is the header endlatch.await (); System.out.println(count); } catch (Exception e) { e.printStackTrace(); }}}Copy the code

Results: 123 = 15} {

1. What is the use of final and volatile variables in ConcurrentHashMap? Final domains make it possible to ensure initialization safety, which allows immutable objects to be freely accessed and shared without synchronization. Volatile is used to ensure that memory changes to a variable are immediately visible to other threads, and CAS is used to support concurrent operations without locking. The get operation is unlocked because the Node element val and pointer next are volatile. In A multithreaded environment, thread A is visible to thread B when modifying val or adding A Node. 2. Can we use CocurrentHashMap instead of Hashtable? We know that Hashtable is synchronized, but ConcurrentHashMap performs better because it locks only part of the map based on the synchronization level. ConcurrentHashMap can certainly replace HashTable, but HashTable provides greater thread-safety. Both can be used in a multithreaded environment, but performance degrades dramatically when the size of a Hashtable increases to a certain point because it is locked for a long time during iteration. Because ConcurrentHashMap introduces segmentation, no matter how large it becomes, only one part of the map needs to be locked, and other threads do not need to wait for iterations to complete before they can access the map. In short, ConcurrentHashMap locks only a portion of the Map during iteration, whereas Hashtable locks the entire map. 3. What are the drawbacks of ConcurrentHashMap? ConcurrentHashMap is designed to be non-blocking. Partial data is partially locked during updates, but not the entire table is locked. Synchronous read operations are completely non-blocking. The advantage is that the efficiency is very high under the premise of ensuring reasonable synchronization. The downside is that the read operation is not strictly guaranteed to reflect the most recent update. For example, thread A calls putAll to write A large amount of data, while thread B calls GET, so only part of the data that has been successfully inserted so far can be gotten. 4. ConcurrentHashMap differences between JDK 7 and 8

  • The JDK1.8 implementation reduces the granularity of locks. The JDK1.7 version locks are segment-based and contain multiple hashentries, whereas the JDK1.8 lock granularity is HashEntry.
  • JDK1.8’s data structure has become simpler, making the operation more clear and smooth, because synchronized has been used to synchronize, so there is no need for the concept of Segment lock, so there is no need for data structure such as Segment, due to the reduction of granularity, implementation complexity has increased
  • JDK1.8 uses red-black trees to optimize linked lists. Traversal based on long linked lists is a long process, and red-black trees traversal efficiency is fast, instead of a certain threshold of linked lists, so as to form an optimal partner

Summary: 1. The data structure of ConcurrentHashMap is basically the same as that of HashMap, except that during the put process, if no conflict occurs, the CAS operation is used for lock-free update. Only when a hash conflict occurs, the operation of adding new nodes or updating nodes in the linked list is locked. 2. Operations like GET are also not synchronized. 3.ConcurrentHashMap cannot store null values. 4. The size of ConcurrentHashMap is calculated, which means that the size is not accurate in the case of extremely high concurrency. I’ll fill in the blanks later. 5. In JDK1.7, lock fragmentation is a bit more complicated. In JDK1.8, the lock on ConcurrentHashMap is locked only when a hash conflict occurs, and only the update operation on the conflicting list is affected.