preface

For the record, this article uses JDK1.8

Review of previous chapters:

  • The Collection overview
  • List collection is as simple as that.
  • Map sets, hash tables, and red-black trees
  • HashMap is as simple as this
  • LinkedHashMap is as simple as this
  • TreeMap is that simple

This article focuses on ConCurrentHashMap~

It is best to have a little data structure foundation before reading this article:

  • Java implements one-way linked lists
  • Stacks and queues are that simple
  • Binary trees are that simple

Of course, if there is something wrong, please bear with me and correct me in the comments

ConCurrentHashMap analysis

ConCurrentHashMap in the beginning of learning anyway I did not touch, I do not know if you have touched ~

This class is also heard very little, in the collection is a more complex class, it involves some multithreading knowledge points.

Do not understand or forget the knowledge of multi-threading students do not be afraid, where to use the knowledge of multi-threading, I will briefly introduce, and give the corresponding information to read ~

Ok, let’s get started

1.1 I met ConCurrentHashMap

The underlying ConCurrentHashMap is a hash table + red-black tree, which is the same as a HashMap.

From the previous chapter we can also find: the fastest way to understand what a class is, we look at the source code at the top of the comments can be!

I simply translated the comments on the top (my English is poor, please forgive me if there is any mistake ~ welcome to correct in the comments section)

According to the above notes, we can summarize briefly:

  • Underlying JDK1.8 is a hash table + red-black tree
  • ConCurrentHashMap supports highly concurrent access and updates and is thread-safe
  • The retrieve operation is unlocked, and the GET method is non-blocking
  • Neither key nor value can be null

1.2JDK1.7 Underlying implementation

Hashing + red-black tree is not the same in JDK1.8

Segments +HashEntry array:

Photo source: blog.csdn.net/panweiwei19…

  • Segments inherit ReentrantLock. Each Segment has a lock called “lock Segment.”

A general understanding of the ~

1.3 Why ConCurrentHashMap is Needed when Hashtable is used

  • Hashtable uses Synchronized on every method, which is inefficient.
  • ConcurrentHashMap implements synchronization by partially locking and using the CAS algorithm.

1.4CAS algorithm and Volatile

Before looking at the source code for ConCurrentHashMap, let’s talk briefly about the CAS algorithm and the volatile keyword

CAS (Compare and Swap) is a well-known lock-free algorithm

CAS has three operands

  • Memory value V
  • The old expected value A
  • The new value B to be modified

Change the memory value V to B if and only if the expected value A and the memory value V are the same, otherwise do nothing

  • When multiple threads are trying to use the CAS for the same variable, at the same time only one thread can update the value of the variable (A and memory value V phase at the same time, amend the memory value V to B), and all the other thread failure, failure of threads will not be suspended, but was told that failed in this contest, and you can try again * * * * (or do nothing)

It should be easy to understand from the above description, first compare whether equal, if equal, replace (CAS algorithm)

Let’s take a look at the volatile keyword, which was rarely used in the beginning. Anyway, I don’t use it, and I often see it when reading Java-related interview questions. I think it is a very mysterious and difficult keyword. In fact, not, or quite easy to understand ~

The classic summary of volatile: Volatile is used only to ensure that the variable is visible to all threads, but not atomicity

Let’s break it down to explain:

  • ensureVisibility of this variable to all threads
    • In a multithreaded environment: When this variable is modified, all threads know that the variable has been modified. This is called “visibility”.
  • Atomicity is not guaranteed
    • Modifying a variable (assignment) essentially takes several steps in the JVM, and within those steps (from loading variables to modifying them), it is not safe.

If you don’t understand it or want to learn more about how it works, please refer to the following blog posts:

  • www.cnblogs.com/Mainz/p/355…
  • www.cnblogs.com/Mainz/p/354…
  • www.dataguru.cn/java-865024…

1.5 ConCurrentHashMap domain

There are several domain objects:

Let’s take a quick look at what they are:

After reading it for the first time, I don’t know what it is, but after reading it further, it may become clear

1.6ConCurrentHashMap constructor

There are five constructors of ConcurrentHashMap:

The concrete implementation looks like this:

TableSizeFor () is called in several places in the constructor.

Click on it and say, oh, I’ve seen this method before, in HashMap…..

It is used to get the number greater than the argument to the nearest power of 2…

The sizeCtl attribute specifies the size of the next expansion

1.7 put method

Here comes one of the core methods: the put method ~~~~

Let’s look at what the put method does as a whole:

Next, let’s see what happens when we initialize the hash table: initTable()

  • Let only one thread initialize the hash table!

1.8 the get method

As you can read from the top comment, the GET method is unlocked and non-blocking.

We can see that the Node Node is overwritten with the volatile keyword modifier so that it gets the latest value each time

Second, the summary

ConcurrentHashMap (ConcurrentHashMap, ConcurrentHashMap, ConcurrentHashMap, ConcurrentHashMap)

Here’s a quick summary of the core points of ConcurrentHashMap:

  • The underlying structure is hash table (array + linked list)+ red-black tree, which is the same as HashMap.
  • Hashtable is an inefficient way to synchronize all methods. ConcurrentHashMap, as a highly concurrent container, is implemented by partial locking +CAS algorithm to achieve thread safety. CAS algorithm can also be considered as a kind of optimistic lock
  • In a high concurrency environment, statistics (calculate size… And so on) is actually meaningless, because at the next moment the size value changes.
  • The GET method is non-blocking and unlocked. Rewrite the Node class to volatile next so that each fetch is the latest value
  • The key and Value of ConcurrentHashMap cannot be null

Open source project (6 K STAR) :Github.com/ZhongFuChen…

If you want to follow my updated articles and shared dry goods in real time, you can search Java3y on wechat.

The content of the PDF document is typed by hand. If you don’t understand anything, you can ask me directly (the official account has my contact information).