JDK1. 8. Reading the source code of concurrenthashmap

1. Read with questions

Why is concurrent HashMap thread safe? Or how does concurrent HashMap prevent concurrency?

2. Fields and constants

First, let's take a look at some fields and constants in concurrenthashmap, which will be used in the next operation

2.1. constant

From this, we can get the following information:

2.2. field

From these fields, we can get the following information:

2.3. Inner class

It is not difficult to find by comparing the HashMap in 1.7:

As you can see, treenode inherits from node and is mainly used in tree structure. That is, treenode represents the node in the tree.

Another treebin is also inherited from node

Treebin represents the whole tree, and treenode represents the nodes in the tree

Under normal circumstances, the element at a certain position in the array should be node, and node is a linked list, which may be followed by multiple nodes.

However, when the number of nodes at a certain location exceeds the threshold (8 by default), the linked list is transformed into a red black tree, and then the element at this location in the array is treebin

That is, node represents the node in the linked list, treenode represents the node in the tree, and treebin represents the tree

3. Operation

3.1. put

Here, take another look at the puttreeval () method just now

In general, insert first and adjust later.

The general process is as follows:

3.2. resize

In the put operation in the previous step, if the array is being expanded, it is helpful to expand

Let's take a look at capacity expansion

I have always had a misunderstanding in my understanding. I always thought that the hash values of elements in the same position of the array are the same. Today, I suddenly realized that this is not the case. The reason why these elements are in the same position is that it is calculated that the element should be in this position through the hash value of the key and the length of several groups, Different hash values may also be in the same position after calculation. Therefore, the hash values of elements in the same position are not necessarily the same, or the hash values of elements in the linked list are not necessarily the same, but they happen to be in the same position in the array.

The expansion is as follows:

The following is a schematic diagram. There is no need to stick to the details, but focus on the meaning

3.3. Get and remove

Deletion and acquisition are relatively simple and will not be repeated

At this point, we can answer the questions we raised at the beginning

sychronized + volatile + CAS

During insertion, deletion and capacity expansion, the elements at the corresponding positions in the array are locked. Synchronized is used for locking

Volatile is added to the table array, Val and next in the node, and some control fields

Sun. Com is used to update some key variables misc. Some methods in unsafe