preface

This article introduces ConcurrentHashMap from common interview questions, and explains the design principles step by step.

HashMap is one of the most frequently used tool classes in our daily development. However, one of the biggest problems with using HashMap is that it is thread-unsafe. What if we want to be thread-safe? ConcurrentHashMap is basically the same as HashMap. ConcurrentHashMap is a thread-safe version of HashMap.

Since ConcurrentHashMap and HashMap exclude thread-safe aspects in jdk1.8, the other designs are similar, so many of the same design ideas won’t be repeated too much in this article

When it comes to interviews, I have to mention that I have compiled the most comprehensive Java interview and learning resources, etc. Please see here

ConcurrentHashMap principle

ConcurrentHashMap is a thread-safe version of HashMap, which internally uses the same array + linked list + red-black tree approach as HashMap.

How to implement thread safety? Lock. But how should this lock be added? In HashTable, synchronized is added directly to the PUT and get methods. In theory, ConcurrentHashMap can do the same, but the granularity of the lock is too large to affect the concurrency performance. Instead of such a straightforward and crude approach, ConcurrentHashMap uses a clever internal design that greatly reduces lock contention and improves concurrency.

The initialization in ConcurrentHashMap is the same as in HashMap, and the capacity is adjusted to the NTH power of 2, for reasons that will not be repeated here.

What are the improvements to ConcurrentHashMap in JDK1.8?

In JDK1.7, ConcurrentHashMap is implemented by array + Segment + Segment lock, which is divided into an array of segments. Segments are locked by inheriting ReentrantLock. Global thread-safety is achieved by reducing the granularity of locking by locking one segment at a time and ensuring thread-safety of operations in each segment. Here is the structure of ConcurrentHashMap in JDK1.7:

The downside of this is that it takes twice for each hash to determine which slot the current key should be in:

  1. A bit operation is performed using the hash value and the segment array length -1 to determine which segment the key belongs to, that is, the position of the key in the segments array.
  2. The bucket is then identified with the hash value and the table array (that is, the underlying data storage array of ConcurrentHashMap) of length -1.

To further optimize performance, in jdk1.8, ConcurrentHashMap was optimized to eliminate the fragment lock design and use cas operation and synchronized keyword instead. In JDK1.8, the storage structure of ConcurrentHashMap is basically the same as that of HashMap, as shown in the following figure:

02 Why cannot the key and value be null?

In a HashMap, both key and value can be null, but not in a ConcurrentHashMap. Why is this?

If get(key) returns null, we can’t tell because the key value is null. If get(key) returns null, we can’t tell because the key value is null. In non-concurrent programming, this can be done by calling containsKey. However, in concurrent programming, there is no guarantee that no other thread will change the key between the two methods, so null is disabled.

And Doug Lea himself believes that allowing null values in collections such as maps and sets, even in non-concurrent collections, is an open acceptance of errors in programs. This was one of the few design differences between Doug Lea and Josh Bloch (one of the authors of HashMap), and ConcurrentHashMap was developed by Doug Lea alone, so null values were banned outright.

03 How does ConcurrentHashMap Ensure thread security?

In ConcurrentHashMap, a lot of divide-and-conquer ideas are used to reduce lock granularity and improve concurrency performance. Its source code uses a large number of CAS operations to ensure security, rather than the same as HashTable, no matter what method, directly simple and crude use of synchronized keyword to achieve, in the following principle analysis, part of the similarities with HashMap will not be repeated in this paper. This paper mainly analyzes the design of ConcurrentHashMap from the aspect of security.

3.1 How to Use CAS to Ensure the security of Array initialization?

Here’s how to initialize it:

There is one very important variable, sizeCtl, that is very important to understand how the whole ConcurrentHashMap works.

SizeCtl has four meanings:

  • SizeCtl <-1: N-1 threads are performing capacity expansion. If -2:2-1 threads are performing capacity expansion.
  • SizeCtl =-1 placeholder, indicating that the array is being initialized.
  • SizeCtl =0 Default, indicating that the array has not been initialized.
  • SizeCtl >0 Specifies the size to be expanded next time.

SIZECTL defaults to 0, so if the substitution succeeds, the current thread can initialize it. If the CAS fails, the other thread takes the lead and sets SIZECTL to -1. After the capacity expansion is successful, the next capacity expansion threshold is set to THE SC, that is, sizeClt.

3.2 How does put ensure visibility of array elements?

The Node array used to store data in the ConcurrentHashMap is volatile, but this only ensures that references to the array are available between threads. It does not guarantee that elements within the array are visible between threads. So here we are checking whether a certain index has an element or not, and we can’t access it directly with the index, so how do we access it? Source code to give you the answer:

As you can see, the tabAt method is used to get the element, and the tableAt method is actually a CAS operation:

If the current node element is found to be empty, the current element is also stored through the CAS operation (casTabAt).

If the current node element is not empty, the synchronized keyword will be used to lock the current node, and the corresponding set operation will be performed:

3.3 Exquisite counting method

In a HashMap, the put method is used to store the number of elements in the current collection by ++size. In concurrent mode, this operation is not safe, so it is not possible to use this method.

It is possible to modify the size directly through the CAS operation. However, if there are many threads trying to modify the size operation at the same time, only one thread will be able to successfully replace the size, and the other threads will have to continuously try the CAS, which will affect the performance of the ConcurrentHashMap set. So the author came up with a divide-and-conquer idea to complete the counting.

The author defines an array to count, and this is used to count the arrays can also increase, each thread count is necessary, through the way of random access to an array subscript position, so that it can be as much as possible to reduce the lock granularity, finally get the size, by walking down group to implement the counting:

Private TRANSIENT volatile CounterCell[] counterCells; private transient volatile CounterCell[] counterCells; @sun.misc.Contended static final class CounterCell {volatile long value; CounterCell(long x) {value = x; }}Copy the code

3.3.1 addCount Counting method

Let’s look at the addCount method:

BASECOUNT = BASECOUNT; BASECOUNT = BASECOUNT; BASECOUNT = BASECOUNT; BASECOUNT = BASECOUNT; Instead of using the CounterCell array, baseCount is used.

If CounterCell is empty and CAS fails, the Array of Countercells is initialized by calling the fullAddCount method.

3.3.2 rainfall distribution on 10-12 fullAddCount method

This method is also long and seemingly complex, including initialization and assignment to the CounterCell array.

Initialize the CounterCell array

Let’s skip ahead and jump right into the initialization logic:

The default value of cellsBusy is 0, indicating that no thread is currently initializing or expanding. If cellsBusy==0, as ==0. If any other thread has modified the global array CounterCell, the CAS operation will change cellsBusy to 1, indicating that it is initializing, and other threads cannot initialize at the same time.

As you can see, the default is an array of length 2, which takes two array positions to store the number of elements in the current ConcurrentHashMap.

(2) How to assign CounterCell

After initialization, if the put method is called again, it enters another branch of the fullAddCount method:

If the element is empty, we need to initialize a CounterCell object and place it in the array. If the element is not empty, we only need the CAS operation to replace the number in the element.

So the logic is clear: when initializing the CounterCell, change cellBusy from 0 to 1.

(3) Can the counter array CounterCell also be expanded?

Finally, let’s move on to the other branches:

Mainly look at the branch in the red box in the figure above. Once entering this branch, it means that all the previous branches are not satisfied, namely:

  • The current CounterCell array has been initialized.
  • Elements in the subscripts of the current hash CounterCell array are not null.
  • If the CAS operation fails to modify the number of objects in the specified subscript position in the CounterCell array, it indicates that other threads are competing to modify elements in the same array subscript.
  • The current operation does not meet the condition of not allowing capacity expansion.
  • No other thread has created a new CounterCell array, and the size of the current CounterCell array is still smaller than the number of cpus.

Therefore, the capacity of the CounterCell array needs to be expanded as well. The expansion method is the same as the expansion method of ConcurrentHashMap. The original capacity is also multiplied by 2, so the capacity of the CounterCell array also meets the power of 2

3.4 Expansion of ConcurrentHashMap

Next, we need to go back to the addCount method, because this method adds the number of elements and determines whether the current ConcurrentHashMap reaches the threshold for expansion. If so, it needs to be expanded.

3.4.1 Can Capacity Expansion also support Concurrency?

The ConcurrentHashMap expansion also supports simultaneous multithreading. How does this work? Let’s go back to the addCount method.

Here check is the length of the list passed in, >=0 to check whether expansion is needed, immediately followed by a while loop, which mainly meets two conditions:

  • As mentioned earlier, sizeCtl is set to the size of the next expansion when initialized (and after), so >=sizeCtl indicates whether the expansion threshold has been reached.
  • Table is not null and the current array length is less than the maximum 2 ^ 30.

(1) What is the use of expansion stamp?

When capacity expansion conditions are met, a method is first called to obtain capacity expansion stamps, which are interesting. To understand capacity expansion stamps, we must analyze them from the binary point of view. The resizeStamp method is a single sentence, where RESIZE_STAMP_BITS is a default value of 16.

 static final int resizeStamp(int n) {
        return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
    }
Copy the code

Inside this key is an Integer. NumberOfLeadingZeros (n) this method, this method source code will not stick out, actually this method is to do one thing, that is the highest for current data are converted to binary non-zero number of zero in the former.

For example, if 16 is converted to binary, it is 10000, and the highest non-zero bit is the fifth bit. Since int is 32 bits, it has 27 bits before it, and all of them are zeros. The result of this method is 27 (1 preceded by 27 zeros).

Then 1<< (resize_stamp_bits-1) in the current version is 1<<15, that is, to get a binary number 1000000000000000, there is also one thing to do here, to move this 1 to the 16th bit. These last two Numbers is obtained by | operation must be 16th is 1, the result is because int is 32 bit, which is most 32 0, and because the default size is 16 n (ConcurrentHashMap default size), So in fact that is most 27 (11011), that is the number 1 is highest in the fifth, implement | operation is to influence the outcome of low five at most.

Note: the reason why the 16th bit is set to 1 is to ensure that the sizeCtl variable is negative. As mentioned before, the negative value of this variable means that there is a thread expanding. The relationship between this variable and sizeCtl will be explained later.

(2) Why is the count +2 instead of +1 for the first expansion?

The first expansion must not take the first two conditions, but the last condition in the red box. This condition moves rs 16 (RESIZE_STAMP_SHIFT) bits to the left through CAS operation, and then adds a 2. What does this mean? Why is it plus 2?

To answer this question, let’s first answer another question: what is the use of the expanded timestamp RS obtained by the above method? In fact, this expansion stamp represents two things:

  • The high 16 bits represent the current expansion mark, which can be understood as an era.
  • The lower 16 bits represent the number of threads to be expanded.

SizeCtl negative values represent expansion. If we move RS 16 bits to the left, the highest bit will be 1. In this case, all the 16 bits will be 0. So it should be +1, but this is +2, because -1 in sizeCtl is already used to replace the current thread size, so if +1 is used, it will conflict with the flag bit.

So if we go back to the second red box in the figure above, we will continue +1 normally, and only need +2 to initialize the first time we record the number of expansion threads

(3) Expansion conditions?

Next, we continue to look at the first red box in the figure above. There are five conditions in it, which means that if any of the five conditions is met, expansion will not be carried out:

  1. (sc >>> RESIZE_STAMP_SHIFT) ! The = rs condition is actually buggy and has been changed in JDK12.
  2. Sc == RS + 1 indicates that the last expansion thread is performing the finishing work, and the expansion is about to end.
  3. Sc == RS + MAX_RESIZERS indicates that the current capacity expansion has reached the maximum number of threads, so no more threads can be added to capacity expansion.
  4. After expansion is complete, the new array nextTable is set to NULL.
  5. TransferIndex <= 0 indicates that all subscripts available for capacity expansion are allocated and the current thread capacity expansion is complete

3.4.2 How can I Expand Capacity in Multiple Concurrent Scenarios?

How do you achieve capacity expansion without conflict in multiple concurrent scenarios? In ConcurrentHashMap, each thread is responsible for a segment. The default minimum is 16. That is, if there are only 16 slots in ConcurrentHashMap, only one thread will participate in the expansion. If the number is greater than 16, the number of threads participating in capacity expansion is allocated based on the number of cpus. The maximum number of threads participating in capacity expansion cannot exceed the number of cpus.

In the same way that a HashMap expands a space, it moves the original space one bit to the left, that is, doubles the size of the original space. Note that transferIndex represents the push index, which defaults to the size of the old array.

3.4.3 How to Ensure data Migration Security during Capacity Expansion?

With the new array initialized, it’s time to prepare the validation bounds. For example, if thread 1 is responsible for 1 to 16, then the corresponding array boundary is 0 to 15, and then the data will be migrated from the last 15:

There are three key variables:

  • The HASH value of the FWD node, which represents the placeholder node, is -1. Therefore, once the hash value of a node is -1, you can know that the node has been migrated.
  • Advance: indicates whether to advance to the next slot. This parameter can be set to true only after data in the current slot is migrated
  • Finishing: Whether data migration has been completed.

The first time we enter the while loop, advance is true by default. The first time we enter the loop is to confirm the boundary. Since the boundary value has not been confirmed, we go straight to the last branch and confirm the boundary by CAS.

The confirmation boundary is difficult to understand directly. Let’s use an example to illustrate:

Assuming that the initial space is 16, then the expanded space will be 32. At this time, transferIndex is the size of the old array 16, and in the second if judgment, transferIndex is assigned to nextIndex, so nextIndex is 1. The stride represents the number of slots each thread is responsible for, and the minimum is 16, so the stride is also 16, so nextBound= nextIndex > stride? nextIndex – stride : NextBound =0 and I =15, so the current thread takes the index from 0 to 15, advances from 0, and immediately sets advance to false, breaking out of the while loop to perform the following data migration logic.

PS: Because nextBound=0, the CAS operation actually changes transferIndex to 0, indicating that the current array subscripts have been allocated completely, which is also the fifth condition of expansion.

During data migration, the synchronized keyword is used to lock the current node. In other words, the granularity of lock is accurate to each node, which can greatly improve efficiency. The data migration after locking is basically the same as that of HashMap. It is also accomplished by distinguishing high and low bits, which will not be repeated in this article.

After the current node completes the data migration, advance is set to true, which means it is ready to advance the node, so it re-enters the first two branches of the while loop above, advances I, sets advance to false again, and repeats, Data migration is completed until the subscript advances to 0.

Thoroughly after the end of the while loop, will enter into the following if judgment, the current thread is in the red box done by itself after the migration, will increase the number of threads to decline, decline after again by a condition judgment, this condition is in fact the front before entering the expansion of the push, if found that expansion has been completed, After expansion, the nextTable is set to NULL, so the fourth condition that does not meet expansion is set here.

conclusion

This paper mainly describes how to ensure security in ConcurrentHashMap, and selects some classic common interview questions to analyze and answer. In the whole ConcurrentHashMap, the whole idea is to reduce the granularity of locks and reduce the lock competition. Therefore, a lot of divide-and-conquer ideas are adopted, such as multi-threading simultaneous expansion, as well as an array to achieve the size count.