Source code analysis of concurrent HashMap in Java concurrency series

We know that hash table is a very efficient data structure. The addition, deletion, modification and query operation on it can reach the O (1) level by well-designed hash function. Java provides us with a ready-made hash structure, that is, the HashMap class. In the previous article, I introduced the HashMap class. I know that all its methods are not synchronized, so it is unsafe in a multithreaded environment. To this end, Java provides us with another hashtable class, which is very simple and rough for multi-threaded synchronization, that is, lock all its methods with the synchronized keyword on the basis of HashMap. Although this method is simple, it leads to a problem that only one thread can operate the hash table at the same time. Even if these threads only perform read operations, they must queue, which has a great impact on performance in a highly competitive multi-threaded environment. The concurrenthashmap introduced in this article is to solve this problem. It uses segmented locks to fine-grained the locks, so that multiple threads can operate the hash table at the same time, which greatly improves the performance. The following figure is a schematic diagram of its internal structure.

1. What are the member variables of concurrenthashmap?

Before reading this article, I believe that readers cannot understand the specific meaning and role of these member variables, but please be patient. Later, we will introduce the role of these member variables in specific scenarios. Here, readers only need to be familiar with these member variables. However, there are still some variables that we need to know now. For example, the segment array represents the set of segment locks, the concurrency level represents the number of segment locks (which also means how many threads can operate at the same time), the initialization capacity represents the capacity of the whole container, and the loading factor represents how full the container elements can be.

2. What is the internal structure of section lock?

Segment is a static internal class of concurrenthashmap. You can see that it inherits from reentrantlock, so it is essentially a lock. It internally holds a hashentry array (hash table) and ensures that all methods of adding, deleting, modifying and querying the array are thread safe. The specific implementation will be described later. All operations of adding, deleting, modifying and querying concurrenthashmap can be entrusted to segment, so concurrenthashmap can ensure safety in multi-threaded environment. Because different segments have different locks, multithreading can operate different segments at the same time, which means that multithreading can operate concurrenthashmap at the same time, which can avoid the defects of hashtable and greatly improve the performance.

3. What did concurrenthashmap do during initialization?

Concurrenthashmap has multiple constructors, but its core constructor is posted above. Other constructors complete initialization by calling it. The core constructor needs to pass in three parameters: initial capacity, loading factor and concurrency level. When introducing member variables earlier, we can know that the default initial capacity is 16, the load factor is 0.75f, and the concurrency level is 16. Now we see the code of the core constructor. First, we calculate ssize through the passed concurrencylevel. Ssize is the length of the segment array. It must be guaranteed to be a power of 2. In this way, we can calculate the subscript of the segment lock in the array through hash & ssize-1. Since the incoming concurrencylevel cannot be guaranteed to be a power of 2, it cannot be directly used as the length of the segment array. Therefore, we need to find a power of 2 closest to the concurrencylevel and use it as the length of the array. If the incoming concurrencylevel is 15, ssize = 16 and sshift = 4 can be calculated from the above code. Next, you can immediately calculate segmentshift = 16 and segmentmask = 15. Note that the segmentshift here is the shift value of the segmented lock, and the segmentmask is the mask value of the segmented lock. These two values are used to calculate the subscript of the segmented lock in the array, which we will talk about below. After calculating the number of segmented locks ssize, the capacity of each segmented lock can be calculated according to the total capacity passed in. Its value C = initialCapacity / ssize. The capacity of the segmented lock, that is, the length of the hashentry array, must also be guaranteed to be a power of 2, and the value of C calculated above cannot guarantee this. Therefore, C cannot be directly used as the length of the hashentry array. You need to find another power of 2 closest to C, assign this value to cap, and then use cap as the length of the hashentry array. Now that we have ssize and cap, we can create segment lock array segment [] and element array hashentry []. Note that with jdk1 6 different yes, in jdk1 In 7, only the segment array is created, and it is not initialized. The operation of initializing the segment is reserved for the insertion operation.

4. How to locate locks and positioning elements?

At jdk1 7 uses unsafe to obtain array elements, so it is better than jdk1 6. There are more codes for calculating the offset of array elements. We don't pay attention to these codes for the time being. Now we only need to know the following two points: A. calculate the subscript locked in the array by hash code: (H > > > segmentshift) & segmentmask. b. Calculate the subscript of the element in the array through the hash code: (tab. Length - 1) & H. Now let's assume that the two parameters passed to the constructor are initialCapacity = 128 and concurrencylevel = 16. According to the calculation, ssize = 16, sshift = 4, segmentshift = 28 and segmentmask = 15 can be obtained. Similarly, the length of the hashentry array in each segment lock is calculated to be 8, so tab length-1=7。 Based on these values, we use the following figure to explain how to locate segment locks and elements according to the same hash code.

You can see that the segment lock and the location of the element are determined by the hash code of the element. The positioning segment lock is the high value of the hash code (taken from 32 bits), and the positioning element is the low value of the hash code. Now there is a problem. They are taken from the left end of 32 bits and the right end of 32 bits. Will there be a conflict at some time? We can find maximum in the member variable_ CAPACITY = 1 << 30，MAX_ Segments = 1 < < 16, which means that the total number of bits used for positioning segment lock and positioning element does not exceed 30, and the number of bits used for positioning segment lock does not exceed 16, so there is at least 2 bits of space between them, so there will be no conflict.

5. How to find elements?

At jdk1 The get method of segment lock in 6 accesses array elements through subscripts, while in jdk1 In 7, the elements in the array are read through the getobjectvolatile method of unsafe. Why did you do that? We know that although the hashentry array reference held by the segment object is of volatile type, the element reference in the array is not of volatile type. Therefore, it is unsafe for multithreading to modify the array elements, and objects that have not been constructed may be read in the array. At jdk1 In 6, the security is ensured by the second lock reading, while jdk1 This is also guaranteed by reading through the getobjectvolatile method of unsafe in 7. To read an array element using the getobjectvolatile method, first obtain the offset of the element in the array. Here, the offset of the segment lock in the array calculated according to the hash code is u, and then try to read the segment lock through the offset U. Since the segmented lock array is not initialized during construction, a null value may be read out, so it needs to be judged first. After determining that neither the segment lock nor its internal hash table is empty, read the elements of the hashentry array through the hash code. As can be seen from the above structure diagram, the header node of the linked list is obtained at this time. Then traverse the linked list from beginning to end. If the corresponding value is found, it will be returned. Otherwise, it will return null. The above is the whole process of finding elements.

6. How to insert elements?

There are two methods to add key value pairs in concurrenthashmap. When adding through the put method, if it exists, it will be overwritten. When adding through the putifabsent method, if it exists, it will not be overwritten. Both methods call the put method of segment lock to complete the operation, but the last parameter passed in is different. In the above code, we can see that we first calculate the subscript of the segment lock in the array according to the hash code of the key, and then use the GetObject method of the unsafe class to read the segment lock according to the subscript. Since the elements in the segment array are not initialized when constructing the concurrenthashmap, a null value may be read. At this time, a new segment lock will be created through the ensuesegment method. After obtaining the segment lock, call its put method to complete the addition operation. Let's take a look at the specific operation.

In order to ensure thread safety, the put operation in the segment lock needs to be locked, so the thread will acquire the lock at the beginning. If the acquisition is successful, it will continue to execute. If the acquisition fails, it will call the scanandlockforput method to spin. During the spin process, it will first scan the hash table to find the specified key. If the key does not exist, it will create a hashentry to return, In this way, there is no need to create a new lock after obtaining the lock, so as to do something while waiting for the lock, so as not to waste time in vain. It can be seen that the author's good intentions. The specific spin method will be discussed in detail later. Now pull back the focus. After successfully obtaining the lock, the thread will obtain the element of the specified subscript according to the calculated subscript. At this time, the header node of the linked list is obtained. If the header node is not empty, the linked list is traversed and searched. After finding it, whether to replace it is determined according to the value of onlyifabsent parameter. If the traversal fails, a hashentry will be created to point to the head node. At this time, if a hashentry is created during spin, its next will directly point to the current head node. If it is not created during spin, a hashentry will be created here and point to the head node. After adding elements to the linked list, check whether the total number of elements exceeds the threshold. If it exceeds the threshold, call rehash to expand the capacity. If not, directly point the element reference of the corresponding subscript of the array to the newly added node. The setentryat method internally changes the array element reference by calling the putorderedobject method of unsafe, which ensures that other threads can read the latest value when reading.

7. How to delete elements?

Concurrenthashmap provides two deletion operations, one is to delete directly after finding, and the other is to compare and delete after finding. The two deletion methods first find the corresponding segment lock according to the hash code of the key, and then call the remove method of the segment lock to complete the deletion operation. Let's take a look at the remove method of segmented lock.

When deleting the elements in the segmented lock, you need to obtain the lock first. If the acquisition fails, call the scanandlock method to spin. If the acquisition succeeds, go to the next step. First calculate the array subscript, and then obtain the elements of the hashentry array through the subscript. Here you get the head node of the linked list, and then traverse the linked list, Before that, use the next pointer to record the subsequent nodes of the current node, and then compare the key and hash to see whether it is the node to be found. If so, execute the next if judgment. If the value is null or the value of value is equal to the current value of the node, you will enter the if statement for deletion. Otherwise, you will skip directly. There are two situations when deleting in the if statement. If the current node is the head node, set the next node as the head node directly. If the current node is not the head node, set the successor of the pred node as the next node. The pred node here represents the successor node of the current node. Each time before checking the next node, it points to the current node, which ensures that the pred node is always the successor node of the current node. Note that with jdk1 6 different, in jdk1 The next variable of the hashentry object in 7 is not final, so the element can be deleted by directly modifying the value referenced by next. Because the next variable is of volatile type, the reading thread can read the latest value immediately.

8. How is the replacement element implemented?

Concurrenthashmap also provides two replacement operations, one is to replace directly after finding, and the other is to compare and replace after finding (CAS operation). The implementation of these two operations is roughly the same, but the CAS operation has one more layer of comparison operation before replacement, so we only need to briefly understand one of them. The analysis of the CAS operation is still the old way. First, find the corresponding block lock according to the hash code of key, then call its replace method. After entering the replace method in the segmented lock, you need to obtain the lock first. If the acquisition fails, spin it. If the acquisition succeeds, proceed to the next step. First, obtain the chain header node according to the hash code, and then traverse and search according to the key and hash. After finding the corresponding element, compare whether the given oldvalue is the current value. If not, discard the modification. If yes, replace it with a new value. Since the value field of the hashentry object is of volatile type, it can be replaced directly.

9. What did you do when spinning?

As we mentioned earlier, put, remove and replace operations in segmented locks require to obtain the lock first. The next operation can be carried out only after the lock is successfully obtained. If the acquisition fails, spin will be carried out. Spin operation is also in jdk1 7, in order to avoid frequent thread hangs and wakes, so as to improve the performance of concurrent operations. ScanAndLockForPut is invoked in the put method, and scanAndLock is invoked in remove and replace methods. The two spin methods are roughly the same. Here we only analyze the scanandlockforput method. First, obtain the chain header node according to the hash code, and then the thread will enter the while loop for execution. The only way to exit the loop is to successfully obtain the lock, and the thread will not be suspended during this period. When entering the loop, the value of retries is - 1. At this time, the thread will not try to obtain the lock immediately. Instead, it will first find the node corresponding to the key (if it is not found, a new one will be created), and then set retries to 0. Next, it will try to obtain the lock again and again, and the value of corresponding retries will be increased by 1 each time until the maximum number of attempts is exceeded. If the lock has not been obtained, The lock method will be called for blocking acquisition. During the lock acquisition attempt, you will check whether the header node has been changed every other time (retries is an even number). If it has been changed, reset the retries back to - 1, and then repeat the previous process. This is what the thread does when spinning. It should be noted that if it is detected that the head node has been changed during spinning, the spin time of the thread will be prolonged.

10. What are the operations done when the hash table is expanded?

Rehash method is called in the put method. We know that new elements will be created and added to the hash array in the put method. With the increase of elements, the greater the possibility of hash conflict, and the performance of the hash table will decline. Therefore, during each put operation, check whether the total number of elements exceeds the threshold value. If it exceeds the threshold value, call the rehash method to expand the capacity. Once the array length is determined, it can no longer be changed, so you need to create a new array to replace the original array. From the code, we can know that the length of the newly created array is twice that of the original array (oldcapacity < 1). After creating a new array, you need to move all the elements in the old array to the new array, so you need to calculate the subscript of each element in the new array. The process of calculating the new subscript is shown in the figure below.

We know that the subscript directly takes the last few bits of the hash code. Since the capacity of the new array is directly obtained by shifting the capacity of the old array by 1 bit to the right, the number of mask bits is increased by 1 bit to the right, and the number of hash code bits is also increased by 1 bit to the right. As shown in the figure above, if the old mask value is 111, the element subscript is 101, and the new mask value after capacity expansion is 1111, the new subscript of the element is 0101. Since the subscripts of elements on the same linked list are the same, now assume that the subscripts of all elements in the linked list are 101. After the expansion, the new subscripts of the linked list elements are only 0101 or 1101. Therefore, the expansion of the array will disrupt the original linked list and divide the linked list elements into two batches. After calculating the new subscript, the element needs to be moved to the new array. Directly modifying the next reference in HashMap leads to multi-threaded deadlock. Although this situation is avoided by locking in concurrenthashmap, we know that the next field is volatile, and its changes can be immediately read by the reading thread. Therefore, to ensure thread safety, copy elements are used to migrate the array. However, copying every element in the linked list has a little impact on the performance. The author found that the next of many elements at the end of the linked list is unchanged, and their subscripts in the new array are the same. Therefore, we can consider moving these elements as a whole. According to statistics, only 1 / 6 of the elements in the actual operation must be copied, so moving the tail elements of the linked list (the elements after lastrun) as a whole can improve certain performance.

Note: This article is based on jdk1 Version 7.

The above is the whole content of this article. I hope it will be helpful to your study, and I hope you can support programming tips.