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

HashTable is a thread-safe class that uses synchronized to lock the entire Hash table for thread safety, that is, locking the entire table to the thread at a time. ConcurrentHashMap allows multiple modification operations to be carried out concurrently, and the key lies in the use of lock separation technology. It uses multiple locks to control changes to different parts of the hash table. ConcurrentHashMap uses Segment internally to represent these different parts, and each segment is actually a small Hashtable, which has its own lock. As long as multiple modifications occur on different segments, they can be carried out concurrently.

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.

1. Realization principle

ConcurrentHashMap uses segmented locking technology to divide the data into segments of storage, and then assign a lock to each segment of data. When a thread occupies the lock to access one segment of data, the data of other segments can also be accessed by other threads, which can achieve real concurrent access. For example, the following figure shows the internal structure of ConcurrentHashMap:

As you can see from the figure, ConcurrentHashMap is internally divided into many Segment, each Segment has a lock, and then each Segment (inherits ReentrantLock)

Static final class Segment extends ReentrantLock implements Serializable

Segment inherits ReentrantLock, indicating that each segment can be treated as a lock. (as mentioned earlier in ReentrantLock, if you don't know about it, think of it as a replacement for synchronized.) so that if you need to synchronize the data in each segment, you use each segment container object's own lock. All segment are locked only when the overall situation needs to be changed.

There are many arrays of HashEntry lists under Segment. For a key, you need to go through three hash operations (why hash three times and will be explained in more detail below) before you can finally locate the location of the element. The three hash are:

For a key, first perform a hash operation to get the hash value H2, that is, H2 = hash2 (key)

Hash the higher bits of H2 for the second time, and get the hash value h3, that is, h3 = hash3 (H2 high bits). Through h3, you can determine which Segment the element is placed on.

Hash the resulting H2 for the third time to get the hash value h4, that is, h4 = hash4 (H2), which can be used to determine which HashEntry the element is placed on.

There are three main entity classes in ConcurrentHashMap: ConcurrentHashMap (the whole Hash table), Segment (bucket) and HashEntry (node). Corresponding to the above diagram, you can see the relationship between them.

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

Immutable and Volatile ConcurrentHashMap completely allow multiple reads to occur concurrently without locking them. 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:

1 static final class HashEntry {2 final K key; 3 final int hash; 4 volatile V value; 5 volatile HashEntry next; 6}

In JDK 1.6, the next pointer in HashEntry is also defined as final, and each time a newly added node is inserted as the head node of the chain (same as the HashMap implementation), and each time a node is deleted, all nodes before the deletion node are copied to form a new chain, and the next of the previous node of the current node is pointed to the next node of the current node, so that two chains exist after deletion. This ensures that even if one thread is deleting and the other thread is traversing in the same chain, they will work well because the traversing thread can continue to use the original chain. Therefore, this implementation is a more fine-grained happens-before relationship, that is, if the traversal thread starts after the deletion thread ends, it can see the change after deletion, and if it occurs in the middle of the deletion thread execution, it will use the original chain instead of waiting for the deletion thread to finish and then execute, that is, it will not see the impact of the delete thread. If this doesn't meet your needs, just wrap it in the synchronized version of Hashtable or HashMap, Collections.synchronizedMap ().

Of the Entry in HashMap, only key is final.

1 static class Entry implements Map.Entry {2 final K key;3 V value;4 Entry next;5 int hash

Immutable mode (immutable) is the simplest way to guarantee multithread safety. Because there's nothing you can do with him, and you don't have a chance to change it.

Immutable patterns are mainly defined by the final keyword. The final keyword also has special semantics in JMM. The Final domain makes it possible to ensure initialization security (initialization safety), which allows immutable objects to be freely accessed and shared without synchronization.

1.1 initialization

First, take a look at what the initialization of ConcurrentHashMap has done. The source code of the constructor is as follows:

1 public ConcurrentHashMap (int initialCapacity, 2 float loadFactor, int concurrencyLevel) {3 if (! (loadFactor > 0) | | initialCapacity

< 0 || concurrencyLevel MAX_SEGMENTS) 6 concurrencyLevel = MAX_SEGMENTS; 7 // Find power-of-two sizes best matching arguments 8 int sshift = 0; 9 int ssize = 1;10 while (ssize < concurrencyLevel) {11 ++sshift;12 ssize >

SegmentShift) & segmentMask)

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.