Shulou(Shulou.com)06/03 Report--

This article shows you what the java Concurrent HashMap lock segmentation technology and principle is, the content is concise and easy to understand, it can definitely brighten your eyes. I hope you can get something through the detailed introduction of this article.

1. Background:

Thread-unsafe HashMap because in a multithreaded environment, using Hashmap for put operations will cause an endless loop, resulting in a CPU utilization of close to 100%, so HashMap cannot be used in concurrency cases.

Inefficient HashTable container

HashTable containers use synchronized to ensure thread safety, but HashTable is very inefficient in the case of fierce thread competition. Because when one thread accesses the synchronization method of HashTable, other threads may enter a blocking or polling state when accessing the synchronization method of HashTable. If thread 1 uses put to add elements, thread 2 not only cannot use the put method to add elements, but also cannot use the get method to get elements, so the more fierce the competition, the lower the efficiency.

Lock segmenting technology

The reason why the HashTable container is inefficient in the highly competitive concurrency environment is that all threads accessing HashTable must compete for the same lock. If there are multiple locks in the container, and each lock is used to lock part of the data in the container, then when multiple threads access the data of different data segments in the container, there will be no lock competition between threads, which can effectively improve the efficiency of concurrent access. This is the lock segmentation technology used by ConcurrentHashMap, which first divides the data into segments of storage, and then allocates each piece of data with a lock. When a thread occupies the lock to access one segment of data, the data of other segments can also be accessed by other threads. Some methods, such as size () and containsValue (), which need to span segments, may need to lock the entire table instead of just one segment, which requires locking all segments sequentially, and releasing locks for all segments sequentially after the operation is complete. It is important to "in order" here, otherwise deadlocks are very likely to occur. Within ConcurrentHashMap, the segment array is final, and its member variables are actually final. However, just declaring the array as final does not guarantee that the array members are also final, which requires a guarantee on implementation. This ensures that deadlocks do not occur because the order in which locks are acquired is fixed.

ConcurrentHashMap is composed of Segment array structure and HashEntry array structure. Segment is a reentrant lock ReentrantLock that acts as a lock in ConcurrentHashMap, while HashEntry is used to store key-value pair data. A ConcurrentHashMap contains an Segment array, the structure of Segment is similar to HashMap, is a kind of array and linked list structure, a Segment contains an HashEntry array, each HashEntry is a linked list structure element, each Segment guardian an element in the HashEntry array, when the data of the HashEntry array is modified, it must first obtain its corresponding Segment lock.

Second, application scenarios

When you have a large array and you need to share it with multiple threads, you can consider whether to layer it to multiple nodes to avoid big locks. And we can consider using hash algorithm to locate some modules. In fact, it is not only used for threads, when designing the transaction of a data table (the transaction is also the embodiment of the synchronization mechanism in a sense), you can think of a table as an array that needs to be synchronized. If you operate too much table data, you can consider transaction separation (which is why it is necessary to avoid the emergence of large tables), such as splitting the data into fields, horizontally splitting tables, and so on.

III. Source code interpretation

There are three main entity classes in ConcurrentHashMap (1.7 and before): ConcurrentHashMap (whole Hash table), Segment (bucket), and HashEntry (node). The relationship between them can be seen in the diagram above.

/ * The segments, each of which is a specialized hash table * / final Segment [] segments

Constant (Immutable) and variable (Volatile)

ConcurrentHashMap completely allows multiple reads to occur concurrently, and reads do not need to be locked. If you use traditional techniques, such as the implementation in HashMap, if you allow elements to be added or removed in the middle of the hash chain, read operations without locking will result in inconsistent data. ConcurrentHashMap implementation technology ensures that HashEntry is almost immutable. HashEntry represents a node in each hash chain, and its structure is as follows:

Static final class HashEntry {final K key; final int hash; volatile V value; final HashEntry next;}

You can see that except that value is not final, all other values are final, which means that nodes cannot be added or removed from the middle or tail of the hash chain, because this requires the next reference value to be modified, and all node modifications can only start with the header. For put operations, all can be added to the header of the Hash chain. But for remove operations, you may need to delete a node from the middle, which requires a copy of all the nodes in front of the node to be deleted, with the last node pointing to the next node to be deleted. This will also be discussed in detail when explaining the delete operation. To ensure that the read operation can see the latest values, set value to volatile, which avoids locking.

Other

In order to speed up the speed of locating segments and hash slots in each segment, the number of hash slots in each segment is 2 ^ n, which makes it possible to locate the position of hash slots in segments and segments through bit operation. When the concurrency level is the default value of 16:00, that is, the number of segments, the top 4 bits of the hash value determine which segment to allocate. But let's not forget the lesson of introduction to algorithms: the number of hash slots should not be 2 ^ n, which may lead to uneven distribution of hash slots, which requires re-hash the hash value. (this paragraph seems a little superfluous.)

Positioning operation:

Final Segment segmentFor (int hash) {return segments [(hash > segmentShift) & segmentMask];}

Since ConcurrentHashMap uses a segmented lock Segment to protect different segments of data, when inserting and fetching elements, you must first locate the Segment through a hash algorithm. You can see that ConcurrentHashMap first uses Wang/Jenkins hash's variant algorithm to hash the element's hashCode once and again. The purpose of re-hashing is to reduce hash conflicts, so that elements can be evenly distributed on different Segment, so as to improve the access efficiency of the container. If the quality of the hash is extremely poor, then all the elements are in a Segment, not only is the access to the element slow, but the segmented lock will also be meaningless. I did a test to perform the hash calculation directly without further hashing.

System.out.println (Integer.parseInt ("0001111", 2) & 15); System.out.println (Integer.parseInt ("0011111", 2) & 15); System.out.println (Integer.parseInt ("0111111", 2) & 15); System.out.println (Integer.parseInt ("1111111", 2) & 15)

After calculation, the output hash value is all 15. Through this example, we can find that if there is no more hashing, the hash conflict will be very serious, because as long as the low bit is the same, no matter what the high bit is, the hash value is always the same. After we re-hash the above binary data, the results are as follows: in order to facilitate reading, the high bits of less than 32 bits are filled with 0, and every four bits are divided by vertical bars.

| 0100 | 0111 | 0110 | 0111 | 1101 | 1010 | 0100 | 11101111 | 0111100 | 0000 | 0100 | 1011 | 10000111 | 0111 | 0110 | 0110 | 0110 | 0011 | 11101000 | 0011 | 0000 | 0000 | 1100 | 1000 | 0001 | 1010 |

It can be found that the data of each bit is hashed, and through this re-hashing, every bit of the number can participate in the hash operation, thus reducing the hash conflict. ConcurrentHashMap locates the segment through the following hash algorithm.

By default, the segmentShift is 28 minus 15, and the maximum number after hashing is 32-bit binary data, which moves 28 bits to the right unsigned, meaning that the top 4 bits participate in the hash operation (hash > segmentShift) & the result of segmentMask is 4pg15 segmentShift 7 and 8, respectively. You can see that there is no conflict between hash values.

Final Segment segmentFor (int hash) {return segments [(hash > segmentShift) & segmentMask];}

Data structure

All members are final, of which segmentMask and segmentShift are mainly used to locate segments, see the segmentFor method above.

I don't want to discuss too much about the basic data structure of the Hash table here. A very important aspect of the Hash table is how to resolve hash conflicts. ConcurrentHashMap and HashMap use the same way, putting nodes with the same hash value in a hash chain. Unlike HashMap, ConcurrentHashMap uses multiple child Hash tables, that is, Segment.

Each Segment is equivalent to a child Hash table with the following data members:

Static final class Segment extends ReentrantLock implements Serializable {/ * * The number of elements in this segment's region. * / transient volatileint count; / * * Number of updates that alter the size of the table. This is * used during bulk-read methods to make sure they see a * consistent snapshot: If modCounts change during a traversal * of segments computing size or checking containsValue, then * we might have an inconsistent view of state so (usually) * must retry. * / transient int modCount; / * * The table is rehashed when its size exceeds this threshold. * (The value of this field is always (int) (capacity * * loadFactor).) * / transient int threshold; / * * The per-segment table. * / transient volatile HashEntry [] table; / * * The load factor for the hash table. Even though this value * is same for all segments, it is replicated to avoid needing * links to outer object. * @ serial * / final float loadFactor;}

Count is used to count the number of data in this segment. It is volatile, which is used to coordinate modification and read operations to ensure that read operations can read almost the latest changes. The coordination mode is that every time a modification operation makes a structural change, such as adding / deleting a node (the value of a modified node is not a structural change), the count value is written, and the value of count is read at the beginning of each read operation.

This takes advantage of the semantic enhancements to volatile in Java 5, where there is a happens-before relationship between writing and reading the same volatile variable. ModCount counts the number of structural changes of segments, mainly to detect whether a segment has changed during traversal of multiple segments, which will be described in detail when describing cross-segment operations. Threashold is used to indicate the boundary value for which rehash is required. The node in the table array storage segment, each array element is a hash chain, represented by HashEntry. Table is also a volatile, which makes it possible to read the latest table values without synchronization. LoadFactor represents the load factor.

Delete operation remove (key)

Public V remove (Object key) {hash = hash (key.hashCode ()); return segmentFor (hash) .remove (key, hash, null);}

The whole operation is first located to the segment and then delegated to the remove operation of the segment. When multiple deletions occur concurrently, as long as they are in different segments, they can be carried out at the same time.

The following is the remove method implementation of Segment:

V remove (Object key, int hash, Object value) {lock (); try {int c = count-1; HashEntry [] tab = table; int index = hash & (tab.length-1); HashEntry first = tab [index]; HashEntry e = first; while (e! = null & & (e.hash! = hash | |! key.equals (e.key)) e = e.nextV oldValue = null; if (e! = null) {V v = e.value If (value = = null | | value.equals (v)) {oldValue = v; / / All entries following removed node can stay / / in list, but all preceding ones need to be / / cloned. + + modCount; HashEntry newFirst = e.next. for (HashEntry p = first; p! = e; p = p.next) * newFirst = new HashEntry (p.key, p.hash, newFirst, p.value); tab [index] = newFirst; count = c; / / write-volatile}} return oldValue;} finally {unlock ();}}

The whole operation is performed with a segment lock, and the row before the blank line is mainly located to the node e to be deleted. Next, if this node does not exist, return null directly, otherwise you will copy the node before e, and the tail node points to the next node of e. The nodes after e do not need to be copied, they can be reused.

What is the for loop in the middle for? (* Mark) from the point of view of the code, all the entry after positioning is cloned and spelled back to the front, but is it necessary? Do you clone the previous element every time you delete an element? This is actually determined by the invariance of entry. If you take a closer look at the definition of entry, you can find that all the properties except value are modified with final, which means that you can't change it after you set the next field for the first time. Instead, you clone all the nodes before it. As for why entry is set to be immutable, this is related to the fact that immutable access does not need to be synchronized to save time. Here is a diagram.

Before deleting an element:

After deleting element 3:

There is actually something wrong with the second diagram. In the copied node, the node with the value of 2 is in the front, and the node with the value of 1 is behind, which is just opposite to the order of the original node. Fortunately, this does not affect our discussion.

The entire remove implementation is not complex, but there are a few points to note. First, when the node to be deleted exists, the last step of the deletion is to subtract the value of count by one. This must be the last step, or the read operation may not see the previous structural changes to the segment. Second, the remove execution starts by assigning table to a local variable, tab, because table is a volatile variable, which is expensive to read and write to the volatile variable. The compiler cannot optimize the reading and writing of volatile variables, and directly accessing non-volatile instance variables many times does not have much impact, and the compiler will optimize accordingly.

Get operation

The get operation of ConcurrentHashMap is directly delegated to the get method of Segment, and directly looks at the get method of Segment:

V get (Object key, int hash) {if (count! = 0) {/ / read-volatile whether the number of data in the current bucket is 0 HashEntry e = getFirst (hash); get the header node while (e! = null) {if (e.hash = = hash & & key.equals (e.key)) {V v = e.value; if (v! = null) return v; return readValueUnderLock (e); / / recheck} e = e.next;}} returnnull;}

No lock is required for get operations.

We know that the get method of the HashTable container needs to be locked, so how can the get operation of ConcurrentHashMap be unlocked? The reason is that the shared variables to be used in its get method are defined as volatile

The first step is to access the count variable, which is a volatile variable. Because all the modification operations will write the count variable in the last step when making structural changes, this mechanism ensures that the get operation can get almost the latest structural updates. For unstructured updates, that is, changes in node values, because the value variable of HashEntry is volatile, it is also guaranteed to read the latest values.

The next step is to traverse the hash chain according to hash and key to find the node to be obtained, and if not, call back null directly. The reason why traversing a hash chain does not require locking is that the chain pointer next is final. But the header pointer is not final, which is returned through the getFirst (hash) method, that is, the value that exists in the table array. This makes it possible for getFirst (hash) to return outdated header nodes, for example, when executing the get method, just after executing getFirst (hash), another thread performs a delete operation and updates the header node, which causes the header node returned in the get method to be not up-to-date. This allows get to read almost the most up-to-date data, although it may not be up-to-date, through the coordination mechanism for count variables. The only way to get the latest data is to use full synchronization.

Finally, if the requested node is found, it is determined that its value is returned directly if it is not empty, otherwise it is read again in a locked state. This seems a little confusing, in theory, the value of the node cannot be empty, this is because the put is judged, if it is empty, the NullPointerException is thrown. The only source of null values is the default value in HashEntry, because the value in HashEntry is not final, and it is possible to read null values from asynchronous reads.

Take a closer look at the statement of the put operation: tab [index] = new HashEntry (key, hash, first, value). In this statement, the assignment to value and the assignment to value in the HashEntry constructor may be reordered, which may cause the node to be null. Here, when v is empty, a thread may be changing the node, and the previous get operations are not locked. According to bernstein conditions, data inconsistency will be caused by reading after writing or reading after writing. Therefore, the e should be locked and read again to ensure that the correct value is obtained.

V readValueUnderLock (HashEntry e) {lock (); try {return e.value;} finally {unlock ();}}

For example, the count field used to count the current Segement size and the value of the HashEntry used to store the value. Variables defined as volatile can maintain visibility between threads, can be read by multiple threads at the same time, and guarantee that expired values will not be read, but can only be written by a single thread (there is a situation that can be written by multiple threads, that is, the written value does not depend on the original value). In get operations, you only need to read and do not need to write the shared variables count and value, so you do not need to add locks. The reason why the expired value can not be read is that according to the happen before principle of the java memory model, the write operation to the volatile field is prior to the read operation. Even if the two threads modify and obtain the volatile variable at the same time, the get operation can get the latest value. This is a classic application scenario of replacing locks with volatile.

Put operation

Similarly, the put operation is the put method delegated to the segment. Here is the put method of the segment:

V put (K key, int hash, V value, boolean onlyIfAbsent) {lock (); try {int c = count; if (C++ > threshold) / / ensure capacity rehash (); HashEntry [] tab = table; int index = hash & (tab.length-1); HashEntry first = tab [index]; HashEntry e = first; while (e! = null & & (e.hash! = hash | |! key.equals (e.key)) e = e.next; V oldValue; if (e! = null) {oldValue = e.value If (! onlyIfAbsent) e.value = value;} else {oldValue = null; + + modCount; tab [index] = new HashEntry (key, hash, first, value); count = c; / write-volatile} return oldValue;} finally {unlock ();}}

This method is also implemented in the case of holding a segment lock (locking the entire segment), of course, for the security of concurrency, modifying data cannot be carried out concurrently, and there must be a statement to determine whether it exceeds the limit to ensure that it can be rehash when the capacity is insufficient. The next step is to find out whether there is a node of the same key, and if so, replace the value of this node directly. Otherwise, create a new node and add it to the header of the hash chain, be sure to modify the values of modCount and count, and also change the value of count in the last step. The put method calls the rehash method, and the reash method is finely implemented, mainly taking advantage of the size of table 2 ^ n, which is not introduced here.

What is more difficult to understand is the sentence int index = hash & (tab.length-1). The original segment is the real hashtable, that is, each segment is a hashtable in the traditional sense, as shown in the figure above. We can see the difference from the structure of the two. Here is to find out which location of the needed entry is in the table, and then the entry is the first node of the chain. If the hashtable is null, it means it has been found. This is to replace the value of the node (onlyIfAbsent = = false), otherwise, we need to new an entry, which is followed by first, and let the tab [index] point to it. In fact, the new entry is inserted into the chain, and the rest is very easy to understand

Because the shared variable needs to be written to in the put method, it must be locked when manipulating the shared variable for thread safety. The Put method first locates to the Segment and then inserts it in the Segment. The insertion operation needs to go through two steps. The first step is to determine whether the HashEntry array in Segment needs to be expanded. The second step is to locate the location of the added elements and put them in the HashEntry array.

Whether it needs to be expanded. Before inserting elements, it will determine whether the HashEntry array in Segment exceeds the capacity (threshold). If it exceeds the threshold, the array will be expanded. It is worth mentioning that the expansion judgment of Segment is more appropriate than that of HashMap, because HashMap determines whether the element has reached its capacity after inserting the element, and if so, it will expand the capacity, but it is very likely that no new element will be inserted after the expansion, so HashMap has carried out an invalid expansion.

How to expand capacity. When you expand the capacity, you will first create an array that is twice the original capacity, then hash the elements of the original array and insert them into the new array. In order to achieve high efficiency, ConcurrentHashMap will not expand the capacity of the entire container, but only a certain segment.

The other operation is containsKey, and this implementation is much simpler because it does not need to read the value:

Boolean containsKey (Object key, int hash) {if (count! = 0) {/ / read-volatile HashEntry e = getFirst (hash); while (e! = null) {if (e.hash = = hash & & key.equals (e.key)) returntrue; e = e.next;}} returnfalse;}

Size () operation

If we want to count the size of the elements in the entire ConcurrentHashMap, we must count the size of all the elements in the Segment and sum them. The global variable count in Segment is a volatile variable, so in a multithreaded scenario, can we directly add the count of all Segment to get the entire ConcurrentHashMap size? No, although you can get the latest value of the count of each Segment when adding up, but the count that may be used before accumulation has changed, so the statistical results are not correct. So the safest thing to do is to lock all Segment's put,remove and clean methods when counting size, but this is obviously very inefficient.

Because in the process of accumulating count, the probability of changes in the previously accumulated count is very small, so the practice of ConcurrentHashMap is to first try to count the size of each Segment by not locking the Segment. If the count of the container changes during the statistical process, then use the locking method to count the size of all Segment.

So how does ConcurrentHashMap determine whether the container has changed at the time of statistics? Using the modCount variable, the variable modCount is incremented by 1 before the element is manipulated in the put, remove and clean methods, so compare whether the modCount has changed before and after counting the size to know whether the size of the container has changed.

The above content is what is the technology and principle of java Concurrent HashMap lock segmentation. Have you learned the knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.