Content of this article: 3000+ words

Estimated reading time: 7 minutes

ConcurrentHashMap (ConcurrentHashMap) In order to help you review efficiently, specially use “★” to indicate the frequency of the interview, “★” more, more high frequency!

Realize the principle of

How does ConcurrentHashMap work? U u u u u

ConcurrentHashMap is implemented differently in JDK1.7 and JDK1.8.

Take a look at JDK1.7

The ConcurrentHashMap in JDK1.7 consists of the Segment array structure and the HashEntry array structure. ConcurrentHashMap divides the hash bucket array into smaller arrays. Each small array consists of n Hashentries.

As shown in the figure below, data is first stored in segments, and then each segment of data is assigned a lock. When a thread uses the lock to access one segment of data, the data in other segments can also be accessed by other threads, realizing real concurrent access.

The Segment is an internal class of ConcurrentHashMap.

A Segment inherits a ReentrantLock, so it acts as a ReentrantLock. The Segment defaults to 16, which means the concurrency is 16.

A HashEntry class that holds elements, which is also a static inner class, consists of the following:

Volatile is used to modify the HashEntry data value and the next node next, ensuring visibility of data acquisition in multithreaded environments.

Take a look at JDK1.8

In terms of data structure, ConcurrentHashMap in JDK1.8 selects the same Node array + linked list + red-black tree structure as HashMap. In the implementation of lock, CAS + synchronized is used to achieve more fine-grained lock, abandoning the original Segment lock.

The lock level is controlled at the finer grained hash bucket element level, that is, only the head of the list (the root of the red-black tree) needs to be locked without affecting the read and write of other hash bucket elements, greatly improving the concurrency.

Why synchronized is used to replace ReentrantLock in JDK1.8? U u u u u

  • In JDK1.6, a number of optimizations have been introduced to the implementation of synchronized, and synchronized has multiple lock states, from no lock -> bias lock -> lightweight lock -> heavyweight lock.
  • Reduce memory overhead. Assuming that reentrant locks are used for synchronization support, each node needs to inherit AQS for synchronization support. However, not every node needs to be synchronized. Only the head node of the linked list (the root node of the red-black tree) needs to be synchronized, which is a huge waste of memory.

access

What is the execution logic of the put method of ConcurrentHashMap? U u u u

Take the JDK1.7

Locate the Segment and then put it.

Source code is as follows:

An attempt is made to acquire the lock first, and if it fails it is sure to be contested by another thread, using the spin of scanAndLockForPut().

  1. Try to spin the lock.
  2. If the number of retries is reachedMAX_SCAN_RETRIESBlock lock acquisition to ensure success.

Look at JDK1.8

It can be roughly divided into the following steps:

  1. Calculates the hash value based on the key.

  2. Determine whether initialization is required.

  3. Locate Node, get the first Node F, and judge the first Node F:

    • If the value is null, the CAS mode is used to add the value.
    • If it isf.hash = MOVED = -1, other threads are expanding capacity and participate in the expansion.
    • If both are not met, synchronized locks the F node, determines whether it is a linked list or a red-black tree, and traverses and inserts;

  4. When the list length reaches 8, the array is expanded or the list is converted to a red-black tree.

Source code is as follows:

What is the execution logic of the Get method of ConcurrentHashMap? U u u u

Again, look at JDK1.7 first

First, the hash value is calculated based on the key to locate the specific Segment. Then the HashEntry object is obtained and positioned based on the hash value. The HashEntry object is traversed through the linked list to find the corresponding element.

Because the shared variables involved in HashEntry are all decorated with volatile, which guarantees memory visibility, the values are updated each time they are fetched.

Source code is as follows:

Look at JDK1.8

It can be roughly divided into the following steps:

  1. Calculate the hash value based on the key to determine whether the array is empty.

  2. If it is the first node, it returns directly;

  3. If it is a red-black tree, query it from the red-black tree;

  4. If it is a linked list, loop through the judgment.

Source code is as follows:

Should the Get method of ConcurrentHashMap be locked? Why? U u u

The get method does not need to be locked. Because the Node element value and pointer next are volatile, thread A is visible to thread B when changing the value of A Node or adding A Node in A multithreaded environment.

This is it better than other concurrent Collections such as Hashtable, with Collections. SynchronizedMap () packaging HashMap is one of the reasons for high efficiency.

Does the get method not need to be locked have anything to do with volatile hash bucket arrays? U u u

It doesn’t matter. The main purpose of volatile is to ensure that the hash bucket table is visible when the array is expanded.

other

Why does ConcurrentHashMap not support key or value null? U u u

Let’s talk about why value can’t be null. If concurrenthashmap. get(key) is null, there is no way to determine whether the mapping value is null or whether the corresponding key is null.

A single-threaded HashMap can use containsKey to determine whether it contains the null.

We use contradiction to reason:

Concurrenthashmap.get (key); concurrenthashMap.get (key); concurrenthashMap.get (key); concurrenthashMap.get (key) We do not know if this null is unmapped or if the value stored is NULL.

Assuming at this point, the true case of returning null is that the corresponding key was not found. So, we can use a ConcurrentHashMap. Either containsKey (key) to verify whether our hypothesis, we expect the result is false.

But after calling concurrenthashmap. get(key) and before containsKey, thread B performs concurrenthashMap. put(key, null). So if we call containsKey it’s going to return true, and that’s not going to be true, and that’s going to be ambiguous.

The key in ConcurrentHashMap cannot also be null. If the interviewer is not satisfied, reply that the author Doug does not like NULL, so he did not allow null keys in the design. I don’t know what the interviewer is looking for in an answer to this interview question

What is the concurrency of ConcurrentHashMap? End to end

Concurrency can be understood as the maximum number of threads that can simultaneously update ConccurentHashMap while the program is running without lock contention. In JDK1.7, this is actually the number of Segment locks in ConcurrentHashMap. This is the array length of Segment[]. The default value is 16, which can be set in the constructor.

If you set your own concurrency, ConcurrentHashMap uses the lowest power of 2 greater than or equal to the value as the actual concurrency, i.e., if you set 17, the actual concurrency is 32.

If the concurrency is set too small, serious lock contention will occur. If the concurrency is set too high, the access in the same Segment will spread to different segments, resulting in a decrease in CPU cache hit ratio and program performance deterioration.

In JDK1.8, the concept of Segment has been abandoned in favor of Node array + linked list + red-black tree structure. Concurrency depends on the size of the array.

Is the ConcurrentHashMap iterator strongly or weakly consistent? End to end

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

When the iterator of ConcurrentHashMap is created, it iterates over each element in a hash table structure, but during the iteration, internal elements may change. If the change occurs in a traversed part, the iterator will not reflect it. If the change occurs in an untraversed part, the iterator will detect and reflect it. This is weak consistency.

This allows the iterator thread to use the old data, while the writer thread can make changes concurrently. More importantly, this ensures continuity and scalability for concurrent execution by multiple threads, which is key to improved performance. If you want to know more, you can read this article: ifeve.com/ConcurrentH…

What is the difference between JDK1.7 and JDK1.8 ConcurrentHashMap? U u u u u

  • Data structure: Remove Segment locking and replace it with arrays, linked lists, and red-black trees.
  • Ensure thread-safe mechanism: JDK1.7 uses Segment locking mechanism to achieve thread-safe, where segments inherit from ReentrantLock. JDK1.8 usingCAS+synchronized Ensure thread safety.
  • Lock granularity: JDK1.7 locks segments that require data manipulation, JDK1.8 locks nodes for each array element.
  • Conversion of linked list to red-black tree: The simplification of hash algorithm for locating nodes brings disadvantages and intensifies hash conflicts. Therefore, when the number of linked list nodes is greater than 8 (and the total amount of data is greater than or equal to 64), the linked list is converted to red-black tree for storage.
  • Query time complexity: from traversal list O(n) in JDK1.7 to traversal red-black tree O(logN) in JDK1.8.

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

ConcurrentHashMap is more efficient than Hashtable because Hashtable adds a large lock to the entire Hashtable to make it thread-safe. However, ConcurrentHashMap has a lower lock granularity. In JDK1.7, piecewise locking is used to achieve thread safety, and in JDK1.8, CAS+synchronized is used to achieve thread safety.

★★★★★ ★★

Hashtable uses synchronized to achieve thread safety, adding a large lock to the entire Hashtable. When multi-threaded access, as long as one thread accesses or manipulates the object, the other threads can only block and wait for the required lock to be released. In the competitive multi-threaded scene, performance will be very poor!

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

You can also use the Collections synchronizedMap method, to add synchronization lock method.

If a HashMap object is passed in, it is a wrapper around the method used in HashMap. The object lock is used to ensure thread-safety in multi-threaded scenarios. In the competitive multi-threaded environment performance is still very poor, not recommended!

The last

That’s it for ConcurrentHashMap, don’t forget to give it a thumbs up

What kind of articles do you want to read

Shoulders of giants

www.cnblogs.com/keeya/p/963…

www.justdojava.com/2019/12/18/… Here I also recommend a collection of computer books warehouse, the warehouse has hundreds of classic CS e-books, read the classic books will be deeper ~

Click this link to get you to the list of must-read books (PDF download included)

Github also has a repository at github.com/cosen1024/a… Welcome to star.