Writing in the front
All the source code of ConcurrentHashMap in this article is based on JDK 1.6. There are some differences between DIFFERENT JDK versions, but it does not affect the overall understanding and understanding of the data structure and principle of ConcurrentHashMap
ConcurrentHashMap, an important member of the J.U.C(java.util.concurrent package), is a thread-safe, efficient concurrency version of HashMap
ConcurrentHashMap overview
HashMap is an important member of the Java Collection Framework and one of the most commonly used of the Map family (shown below). Unfortunately, HashMap is not thread-safe
HashMap the disadvantages tend to cause inconvenience, although in concurrent scenarios HashMap HashTable and by synchronous wrappers (collections.synchronizedmap (Map < V > K, m)) can replace a HashMap, However, they both use a global lock to synchronize concurrent access between different threads, and therefore pose significant performance problems. Fortunately, the JDK solves this problem for us by providing a thread-safe and efficient version of HashMap called ConcurrentHashMap
In ConcurrentHashMap, high performance is guaranteed for both read and write operations: locks are (almost) not required for read operations, while locks are only used for write operations without affecting client access to other segments. In particular, ConcurrentHashMap ideally supports concurrent writes by 16 threads (if the concurrency level is set to 16) and reads by any number of threads
The efficient concurrency mechanism of ConcurrentHashMap is guaranteed by the following three aspects
- Write operation in concurrent environment can be guaranteed by lock segment technology.
- Efficient and safe read operations are guaranteed through the invariance of HashEntry, memory visibility of Volatile variables, and locking re-read mechanism.
- The security of cross – segment operation is controlled by locking and unlocking schemes.
ConcurrentHashMap is defined in the JDK
The ConcurrentHashMap class contains two static inner classes
- HashEntry: Encapsulates a specific K/V pair, which is a typical quad
- Segment: Acts as a lock. Each Segment object guards buckets of the entire ConcurrentHashMap (think of the Segment as a small hash table), where each bucket is a linked list of HashEntry objects
ConcurrentHashMap creates an array of 16 segments at the default concurrency level. If the key is evenly hashed, each Segment is approximately 1/16 of the total number of buckets in the hash.
Class structure definition
ConcurrentHashMap extends AbstractMap and implements the ConcurrentMap interface, which is defined in JDK as:
public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
implements ConcurrentMap<K, V>, Serializable {
...
}
Copy the codeMember variable definition
Compared to HashMap, ConcurrentHashMap adds two attributes for locating segments, namely segmentMask and segmentShift. Also, unlike a HashMap, the ConcurrentHashMap underlying structure is an array of segments rather than objects
final int segmentMask; // The segment size is equal to the size of the segments array minus 1, which is an immutable final int segmentShift; // The size is equal to 32(hashFinal Segment<K,V>[] segments; final Segment<K,V>[] segments; // The underlying structure of ConcurrentHashMap is a Segment arrayCopy the codeDefinition: Segment
The Segment class inherits from the ReentrantLock class so that the Segment object can act as a lock
In Segment, the count variable is a counter that represents the total number of hashentries that are contained in the table array managed by each Segment object. In particular, include a counter in each Segment object instead of using a global counter in ConcurrentHashMap because of ConcurrentHashMap concurrency: This is because you don’t have to lock the entire ConcurrentHashMap when you need to update the counter
Base element: HashEntry
Similar to Entry in a HashMap, HashEntry contains the same four fields: key, Hash, Value, and Next. In contrast, in the HashEntry class, the key, hash, and next fields are declared final, and the value field is modified by volatile. Therefore, the HashEntry object is almost immutable, which is an important reason why the ConcurrentHashmap read does not require locking
Because the value field is volatile, it ensures that the read thread reads the latest value, which is another important reason that the ConcurrentHashmap read does not need to be locked.
Constructor of ConcurrentHashMap
1, ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)
This constructor is intended to construct an empty ConcurrentHashMap with a specified capacity, a specified load factor, and a specified number of segments/concurrency level (adjusted to a power of 2 if not two)
2, ConcurrentHashMap(int initialCapacity, float loadFactor)
This constructor is intended to construct an empty ConcurrentHashMap with the specified capacity, the specified load factor, and the default concurrency level (16)
3, ConcurrentHashMap (int initialCapacity)
This constructor is intended to construct an empty ConcurrentHashMap with the specified capacity, default load factor (0.75), and default concurrency level (16)
4, ConcurrentHashMap ()
This constructor is intended to construct an empty ConcurrentHashMap with a default initial capacity (16), default load factor (0.75), and default concurrency level (16)
5, ConcurrentHashMap (Map <? extends K, ? extends V> m)
The purpose of this constructor is to construct a ConcurrentHashMap that has the same mapping as the specified Map, with an initial capacity of at least 16 (depending on the size of the specified Map), a load factor of 0.75, and a concurrency level of 16. Is recommended by the Java Collection Framework specification
summary
Here, we have mentioned three very important parameters that affect the performance of ConcurrentHashMap: initial capacity, load factor, and concurrency level
ConcurrentHashMap data structure
By using segments to divide the ConcurrentHashMap into different parts, the ConcurrentHashMap can use different locks to control changes to different parts of the hash table. This allows multiple modification operations to occur concurrently, which is the core of ConcurrentHashMap lock fragmentation technology
ConcurrentHashMap concurrent access
In ConcurrentHashMap, read operations on the mapping table by threads do not need to be locked. Structural changes to the container (such as PUT and remove operations) need to be locked.
Implement concurrent write operations between multiple threads with segmented locking mechanism: PUT (key, vlaue)
Typical structural modification operations in ConcurrentHashMap include PUT, remove, and clear. The following uses the PUT operation as an example to describe the structural modification process of ConcurrentHashMap
public V put(K key, V value) {
if (value == null)
throw new NullPointerException();
int hash = hash(key.hashCode());
return segmentFor(hash).put(key, hash, value, false);
}
Copy the codeConcurrentHashMap differs from HashMap in that neither key nor value is allowed to be null
The source code for the segmentFor() method for locating segments is as follows
final Segment<K,V> segmentFor(int hash) {
return segments[(hash >>> segmentShift) & segmentMask];
}
Copy the codeWhere is the element in the Segment based on the hash value of the key
The source code for the put() method of the section is shown below
V put( K key, int hash, V value, boolean onlyIfAbsent ) { lock(); /* lock */ try {int c = count;if ( c++ > threshold ) /* ensure capacity */
rehash(a); HashEntry<K, V>[] tab = table; /* table is Volatile */ int index =hash& (tab.length - 1); /* Locate the bucket in the segment */ HashEntry<K, V> first = TAB [index]; */ HashEntry<K, V> e = first; /* Check whether there are nodes with the same key */ in the bucketwhile( e ! = null && (e.hash ! =hash| |! key.equals( e.key ) ) ) e = e.next; V oldValue;if( e ! {oldValue = e.value;if(! onlyIfAbsent ) e.value = value; /* Update value */}else{/* There is no node with the same key */ oldValue = null; ++modCount; /* modCount + 1 */ TAB [index] = new HashEntry<K, V>(key,hash, first, value ); /* Create HashEntry and chain it to the table header */ count = c; /* write-volatile, count must be updated in the last step (volatile variables) */}return(oldValue); } finally {unlock(); /* Unlock in the finally clause */}}Copy the codeConcurrentHashMap provides a qualitative improvement in concurrent access performance compared to HashTable and HashMap wrapped in synchronous wrappers, where only one thread can read or write at a time. Ideally, ConcurrentHashMap can support concurrent writes from up to 16 threads (if the concurrency level is set to 16) and reads from any number of threads