How does ConcurrentHashMap keep threads safe

As we know, ConcurrentHashmap(1.8) is thread-safe. When you look at the source code for get operations, you will see that the get operation is completely unlocked. This is the question discussed in this blog post – why doesn’t it need to be locked?

The summary of ConcurrentHashMap

The implementation of JDK1.8 reduces the granularity of locks. The granularity of locks in JDK1.7 is segage-based and contains multiple hashentries, while the granularity of locks in JDK1.8 is HashEntry (the first node). Because synchronized is used for synchronization, the concept of Segment locking is not needed, and the data structure such as Segment is not needed. Due to the reduction of granularity, the implementation complexity is also increased. JDK1.8 uses red-black tree to optimize the linked list, and traversal based on long linked list is a long process. And red-black tree traversal efficiency is fast, instead of a certain threshold of the linked list, so as to form a best partner.

Get operation source code


  • First compute the hash value, locate the table index position, return if the first node matches
  • If capacity expansion occurs, the find method of ForwardingNode, which marks the node being expanded, will be called to find the node and return if the node matches
  • If none of the above is true, the node is traversed and returns if it matches, otherwise null is returned


[Java]

Plain text view
Copy the code

?
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// You will find no lock anywhere in the source code
public
V get(Object key) {

Node<K,V>[] tab; Node<K,V> e, p;
int
n, eh; K ek;

int
h = spread(key.hashCode());
/ / calculate the hash

if
((tab = table) ! =
null
&& (n = tab.length) >
0
&&

(e = tabAt(tab, (n -
1
) & h)) ! =
null
) {
// Read the Node element of the first Node

if
((eh = e.hash) == h) {
// Returns if the node is the first node

if
((ek = e.key) == key || (ek ! =
null
&& key.equals(ek)))

return
e.val;

}

// A negative hash value indicates expansion. In this case, ForwardingNode's find method is consulted to locate nextTable

//eh=-1, indicates that the node is a ForwardingNode and is being migrated. In this case, call ForwardingNode's find method to find the node in nextTable.

//eh=-2, indicating that the node is a TreeBin, call TreeBin's find method to traverse the red-black tree. Because the red-black tree may be rotating and changing colors, there will be read/write locks in the find.

//eh>=0, indicating that a linked list is attached to this node.

else
if
(eh <
0
)

return
(p = e.find(h, key)) ! =
null
? p.val :
null
;

while
((e = e.next) ! =
null
) {
// It is neither the first node nor ForwardingNode, so go ahead

if
(e.hash == h &&

((ek = e.key) == key || (ek ! =
null
&& key.equals(ek))))

return
e.val;

}

}

return
null
;
}





Volatile appearance


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







To sum up:

















Was it volatile added to the array?

[Java]

Plain text view
Copy the code

?
1
2
3
4
5
<font color=
"# 000000"
>
/ * *

* The array of bins. Lazily initialized upon first insertion.

* Size is always a power of two. Accessed directly by iterators.

* /

transient
volatile
Node<K,V>[] table; </font>

We know that volatile can modify arrays, but it doesn’t mean what it seems. For example, volatile int array[10] means that the address of the array is volatile, not that the value of the array elements is volatile.

A Node that is volatile


The get operation is unlocked because the Node element val and pointer next are volatile. In A multithreaded environment, thread A is visible to thread B when modifying val or adding A Node.

[Java]

Plain text view
Copy the code

?
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
static
class
Node<K,V>
implements
Map.Entry<K,V> {

final
int
hash;

final
K key;

// You can see that these are volatile

volatile
V val;

volatile
Node<K,V> next;

Node(
int
hash, K key, V val, Node<K,V> 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<K,V> find(
int
h, Object k) {

Node<K,V> 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
;

}
}