The principle of ConcurrentHashMap analysis

Recommended for you: Get network issues from WhatsUp Gold. Not end users.
In this paper the author: Li Hongxu, reproduced please indicate the source

Background:

For the realization of the principle of ConcurrentHashMap, a lot of the time we just know that it adopts a separation technology, in the case of high concurrency can ensure the thread safe, but the specific implementation principle and implementation details are not carefully studied, today on the application scenarios and principle and share with you.



Analysis of principle



Java.util.concurrent.ConcurrentHashMap JDK1.5 then support high concurrency, high throughput was achieved by HashMap, which is to implement the map interface and ConcurrentMap interface, we look at the diagram




For the ordinary HashMap, Java is used to solve the conflict of the chain structure of hash,

Below is the representation of data structure of an ordinary HashMap, HashMap by hash algorithm distributes the data to an array (bucket), then each bucket using the list structure to solve the conflict,

We will look at the simple data structure under the ConcurrentHashMap graph



 The ConcurrentHashMap class contains two static inner classes HashEntry and Segment. HashEntry is used to encapsulate the mapping table of key / value pairs; Segment for data classification and lock role, several table each Segment object to protect the entire hash mapping table. Each table is composed of several HashEntry objects linked list. An instance of ConcurrentHashMap contains an array composed of a plurality of Segment objects, so therefore, to locate the need after two times of hash to an element, the first location to segment, the second positioning to the list head, therefore the hash time than the hash algorithm of general HashMap long.


We look at each segment is how to define:

static final class Segment extends ReentrantLock implements Serializable {
    transient volatile int count;
    transient int modCount;
    transient int threshold;
    transient volatile AtomicReferenceArray<HashEntry> table;
    final float loadFactor;
}

Segment inherits the ReentrantLock, show that each segment can be used as a lock. (ReentrantLock as previously mentioned, do not understand the words put as alternative to synchronized it) that need synchronization operation for each of the data in the segment words are implemented using each of the segment container object's lock. Only is all segment lock on the global change.

This approach above, is called a "separation of lock(lock striping)".


Below we look at the ConcurrentHashMap get operation, he need not be locked

  V get(Object key, int hash) {
            if (count != 0) { // read-volatile
                HashEntry<K,V> e = getFirst(hash);
                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;
                }
            }
            return null;
        }


In the code above, the beginning of the volatile variable count to read more, this is java5 on the enhancement of volatile semantic role, so that you can get variable visibility. So count! = 0, we can think of the corresponding hashtable is new, because of course read when no lock, in the process of get, there may be updated. When key elements according to find, but found that corresponds to the key for the value null, this time there may be other threads are writing on this element, so need to use locks in the case of reading about value, to ensure that the final value.


In ConcurrentHashMap remove, the put operation is relatively simple, it is remove or put operation to the key corresponding to the segment to do, so when several operations can be complicated by is not at the same time with the same segment. The specific code will not paste here, we are interested can go to see the realization of the source code.


Summary and matters needing attention

In the actual application, application scenarios of hash table is generally: in addition to a small number of insert and delete operations, the vast majority are read operation, and the read operation in most of the time are successful. It is based on this premise, ConcurrentHashMap for read operations to do a lot of optimization. Memory visibility through the invariance of the HashEntry object and using the volatile variable coordination between threads, so most of the time, read operation without the need for locks can obtain the correct values. This feature makes the concurrent performance of ConcurrentHashMap based on the separation of lock has a step increase.

Summary


ConcurrentHashMap is a concurrent hash mapping table implementation, allowing fully concurrent reads it, with a given number of updates and support. Compared to the HashTable and synchronization wrappers HashMap (Collections.synchronizedMap (HashMap) (New)), ConcurrentHashMap has a higher concurrency. In the HashTable and by the synchronization wrappers HashMap, lock to concurrent access synchronization between different threads use a global. At the same time, only one thread can hold the lock, that is to say at the same time, only one thread can access the container. This is to ensure the safety of concurrent threads access, but also lead to vessel access into the serialization.


In the use of locks to coordinate the multi thread concurrent access mode, reduce the lock competition can effectively improve the concurrency. There are two ways to lock can reduce competition:


1 reduction request the same lock frequency.

2 to reduce the holding time.


High concurrency of ConcurrentHashMap mainly comes from three aspects:


Shared access to 1 by separating the lock between multiple threads of deeper.

2 using the invariance of the HashEntery object to reduce the read operation thread lock on the linked list traversal demand during the.

3 based on a Volatile variable with write / read access, coordination between different threads of read / write memory visibility.


Use a separate lock, reduces the request with a frequency lock.


The invariance of the HashEntery object to a Volatile variable with the read / write to coordinate memory visibility, the read operation most of the time without the need for locks can be successful access to the required values. Because the hash mapping table in practical applications, most operations are the read operation is successful, so 2 and 3 can reduce the request the same lock frequency, can effectively reduce the holding time.


By reducing the request the same lock frequency and reduce the time that locks are held, the concurrency of ConcurrentHashMap relative to HashTable and synchronization wrappers HashMap have improved.


Reference material

http://www.ibm.com/developerworks/cn/java/java-lo-concurrenthashmap/index.html

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Monica at July 02, 2014 - 2:53 PM