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

This article introduces the knowledge of "Why the read operation of ConcurrentHashMap does not need to be locked". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

We know that the concurrent collection framework of ConcurrentHashmap is thread-safe. When you see the get operation of the source code, you will find that there is no lock on the whole process of the get operation. This is also the question discussed in this blog post-- why does it not need to be locked?

A brief introduction to ConcurrentHashMap

I think the basic students know that jdk1.7 is implemented in the way of Segment + HashEntry + ReentrantLock, while the bloated design of Segment is abandoned in 1.8. instead, Node + CAS + Synchronized is used to ensure the security of concurrency.

The implementation of JDK1.8 reduces the granularity of locks. The granularity of JDK1.7 version locks is based on Segment and contains multiple HashEntry, while the granularity of JDK1.8 locks is HashEntry (first node).

The JDK1.8 version of the data structure becomes simpler and makes the operation clearer and smoother. Because synchronized is already used for synchronization, the concept of segmented locking is not needed, and the data structure of Segment is not needed. due to the reduction of granularity, the complexity of implementation is also increased.

JDK1.8 uses red-black trees to optimize linked lists. Traversing based on long linked lists is a long process, while the traversal efficiency of red-black trees is very fast, instead of linked lists with a certain threshold, thus forming a best partner.

Get operation source code

First calculate the hash value, navigate to the table index location, and return if the first node matches

If you encounter capacity expansion, the find method that marks the node ForwardingNode being expanded is called to find the node, and the match will be returned.

If none of the above matches, go through the node and return the match. Otherwise, null will be returned.

/ / you will find that there is no lock public V get (Object key) {Node [] tab; Node e, p; int n, eh; K ek; int h = spread (key.hashCode ()) in the source code / / calculate hash if ((tab = table)! = null & & (n = tab.length) > 0 & (e = tabAt (tab)) (n-1) & h)! = null) {/ / read the Node element if ((eh = e.hash) = = h) of the first node {/ / if the node is the first node, return if ((ek = e.key) = = key | | (ek! = null & key.equals & key.equals (ek)) return e.val } / / A negative hash value indicates that the capacity is being expanded. At this time, check the find method of ForwardingNode to locate the nextTable to / / eh=-1, indicating that the node is a ForwardingNode and is being migrated. Call the find method of ForwardingNode to find it in nextTable. / / eh=-2, indicating that the node is a TreeBin. Call the find method of TreeBin to traverse the red-black tree. Since the red-black tree may be rotating and changing color, there will be read-write locks in the find. / / eh > = 0, indicating that there is a linked list hanging under the node, and you can directly traverse the linked list. Else if (eh < 0) return (p = e.find (h, key))! = null? P.val: null; while ((e = e.next)! = null) {/ / is neither the first node nor the ForwardingNode, then go through if (e.hash = = h & & ((ek = e.key) = = key | | (ek! = null & & key.equals (ek) return e.valt;}} return null;}

If get is not locked, how does ConcurrentHashMap ensure that the data read is not dirty?

Volatile debut

For visibility, Java provides the volatile keyword to ensure visibility and order. But atomicity is not guaranteed.

Ordinary shared variables cannot guarantee visibility, because it is uncertain when ordinary shared variables are written to main memory after they are modified, and when other threads read them, the old values may still be in memory at this time, so visibility cannot be guaranteed.

The modification of the volatile keyword to the basic type can be consistent in subsequent reads to multiple threads, but for reference types such as array, entity bean, it only guarantees the visibility of the reference, but not the visibility of the reference content.

Instruction reordering is prohibited.

Background: in order to improve the processing speed, the processor does not communicate directly with the memory, but reads the data in the system memory to the internal cache (L1, L2 or other) before operating, but does not know when it will be written to memory.

If you write to a variable that declares volatile, JVM sends an instruction to the processor to write the data from the cache line of the variable back to system memory. However, even if you write back to memory, there will be problems performing calculations if the values cached by other processors are still old.

In multiprocessors, in order to ensure that the cache of each processor is consistent, the cache consistency protocol will be implemented. When a CPU is writing data, if it is found that the variable is a shared variable, it will inform other CPU that the cache line of the variable is invalid, so other CPU will reload the data from main memory when reading the variable.

To sum up:

First: use the volatile keyword to force the modified value to be written to main memory immediately

Second: if you use the volatile keyword, when thread 2 modifies, the cache line of the cache variable in the working memory of thread 1 will be invalid (if reflected in the hardware layer, the corresponding cache line in the L1 or L2 cache of CPU is invalid)

Third: because the cache line of the cache variable in thread 1's working memory is invalid, thread 1 will go to main memory to read the value of the variable again.

Is it the volatile added to the array? / * The array of bins. Lazily initialized upon first insertion. * Size is always a power of two. Accessed directly by iterators. * / transient volatile Node [] table

We know that volatile can modify an array, but the meaning is different from what it looks like. For example, volatile int array [10] means that the address of the array is volatile rather than the value of the array element is volatile.

Node modified with volatile

Get operation can be lock-free because the element val and pointer next of Node are decorated with volatile, which is visible to thread B when thread A modifies the val of a node or adds a new node in a multithreaded environment.

Static class Node implements Map.Entry {final int hash; final K key; / / you can see that these are all modified with volatile volatile V val; volatile Node next; Node (int hash, K key, V val, Node next) {this.hash = hash; this.key = key; this.val = val; this.next = next;} public final K getKey () {return key } public final V getValue () {return val;} public final int hashCode () {return key.hashCode () ^ val.hashCode ();} public final String toString () {return key + "=" + val;} public final V setValue (V value) {throw new UnsupportedOperationException ();} public final boolean equals (Object o) {Object k, v, u; Map.Entry e Return ((o instanceof Map.Entry) & & (k = (e = (Map.Entry) o). GetKey ())! = null & & (v = e.getValue ())! = null & & (k = = key | | k.equals (key)) & & (v = (u = val) | | v.equals (u);} / * * Virtualized support for map.get () Overridden in subclasses. * / Node find (int h, Object k) {Node e = this; if (k! = null) {do {K ek; if (e.hash = = h & & (ek = e.key) = = k | | (ek! = null & & k.equals (ek) return e } while (e = e.next)! = null);} return null;}}

Since the volatile decorated array has no effect on get operations, what is the purpose of the volatile added to the array?

In fact, it is a volatile added to make the Node array visible to other threads when it expands.

Summary

The whole get operation of ConcurrentHashMap does not need to be locked in 1.8. this is one of the reasons why it is more secure than other concurrent collections such as hashtable and hashmap; wrapped in Collections.synchronizedMap ().

The whole process of get operation does not need to be locked because val, a member of Node, is decorated with volatile, which has nothing to do with arrays decorated with volatile.

The main purpose of decorating an array with volatile is to ensure visibility when the array is expanded.

This is the end of the content of "Why the read operation of ConcurrentHashMap does not need to be locked". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.