[Beautiful JUC Part.8] ConcurrentHashMap and other concurrent collections
Overview of concurrent containers, history of collection classes, ConcurrentHashMap (key points, common interview tests)
CopyOnWriteArrayList, concurrent queue Queue (blocking queue, non-blocking queue)
1. Overview of concurrent containers
-
ConcurrentHashMap: Thread-safe HashMap
-
CopyOnWriteArrayList: Thread-safe List
-
BlockingQueue: This is an interface that represents a blocking queue, which is very suitable for use as a channel for data sharing
-
ConcurrentLinkedQueue: An efficient non-blocking concurrent queue, implemented using a linked list. Can be viewed as a thread-safe LinkedList
-
ConcurrentSkipListMap: It is a Map that uses the data structure of a skip table for quick search.
2. Ancient and obsolete synchronization container (history)
1, Vector and Hashtable
The main problem with the concurrency-safe collection classes designed early in the JDK was poor performance.
Most of the vector source code is protected by synchronized and has poor performance.
The same is true for hashtables. Most of them are synchronized and have poor high concurrency performance.
2. HashMap and ArrayList
These two are thread-unsafe, but there are upgraded versions
The following is the specific implementation code
It can be seen that it is similar to declaring vector and hashtable. So the performance is mediocre.
3. ConcurrentHashMap and CopyOnWriteArrayList
Replaces synchronized HashMap and synchronized ArrayList
In most concurrency situations, ConcurrentHashMap and CopyOnWriteArrayList perform better
Three, ConcurrentHashMap
Introduction to Map, why ConcurrentHashMap is needed, and analysis of HashMap
Implementation and analysis of ConcurrentHashMap in JDK1.7
ConcurrentHashMap implementation and source code analysis in JDK1.8
Compare the pros and cons of the two versions
Combining operations: ConcurrentHashMap is not thread-safe too?
1. Map introduction
HashMap, Hashtable, LinkedHashMap, and TreeMap are all implementations of this interface.
2. Why do we need ConcurrentHashMap?
HashMap is thread-unsafe
At the same time, put collision causes data loss
At the same time, put expansion leads to data loss.
CPU 100% caused by infinite loop (only exists in JDK7 and before)
- When multiple threads are expanded, it will cause an infinite loop in the linked list (you point to me, I point to you)
- In fact, this is not a problem in the first place, because HashMap itself does not support concurrency. If you want concurrency, use ConcurrentHashMap
3. HashMap concurrency characteristics
It is not thread-safe, content is not allowed to be modified during iteration, and read-only concurrency is safe. If you must use HashMap in a concurrent environment, use Collections.synchronizedMap(new HashMap())
4. JDK1.7’s ConcurrentHashMap implementation and analysis
The outermost layer of ConcurrentHashMap in Java7 is multiple segments. The underlying data structure of each segment is similar to HashMap. It is still a zipper method composed of arrays and linked lists.
Each segmentis locked by ReentrantLock independently, and each segment does not affect each other, improving concurrency efficiency.
ConcurrentHashMap has 16 Segments by default, so it can support concurrent writing by up to 16 threads at the same time (the operations are distributed on different Segments). This devil can be set to other values during initialization, but once initialized, it cannot be expanded.
5. JDK1.8’s ConcurrentHashMap implementation and analysis
The red-black tree changes the query from O(n) to O(logn)
putVal’s process
get process
6. Why should the structure of 1.7 be changed to the structure of 1.8
data structure
Hash collision
Ensure concurrency safety
- 1.7 uses segment lock to ensure concurrency security. Segment inherits from ReentrantLock.
- 1.8 is through CAS plus synchronized
Query complexity increased
Why does it need to be converted to a red-black tree if it exceeds 8?
The default is a linked list. It is difficult to achieve a conflict of 8 under normal circumstances. The probability is only one in ten million. If such a situation really occurs, it can be ensured that in extreme cases, a red-black tree will be used to occupy a larger space. , improve query efficiency.
Combined operation thread is not safe
import java.util.concurrent.ConcurrentHashMap;
/**
* Description: Combining operations does not guarantee thread safety
*/
public class OptionsNotSafe implements Runnable{
private static ConcurrentHashMap<String, Integer> scores = new ConcurrentHashMap<String, Integer>();
public static void main(String[] args) throws InterruptedException {
scores.put("Xiao Ming", 0);
Thread t1 = new Thread(new OptionsNotSafe());
Thread t2 = new Thread(new OptionsNotSafe());
t1.start();
t2.start();
t1.join();
t2.join();
System.out.println(scores.get("Xiao Ming"));
}
@Override
public void run() {
for (int i = 0; i < 1000; i + + ) {
Integer score = scores.get("Xiao Ming");
Integer newScore = score + 1;
scores.put("Xiao Ming", newScore);
}
}
}
ConcurrentHashMap can guarantee that a single operation, such as a single put or get operation, is thread-safe, but combined operations are not guaranteed.
Solution
Method 1: Lock
This method is not good. It is no different from an ordinary HashMap.
Method 2: Use the replace method
operation result
Method 2 evolution:
4. CopyOnWriteArrayList
1. Birth History
2. Usage Scenario
Read operations can be as fast as possible, and it doesn’t matter if writes are slower.
Read more and write less: blacklist, updated daily; listener: there are far more fall operations than modification operations
3. Reading and Writing Rules
4. Ordinary ArrayList defects
package collections.copyonwirte;
import java.util.ArrayList;
import java.util.Iterator;
/**
* Description: Demonstrates that CopyOnWriteArrayList can modify the array content during iteration
* But ArrayList does not work
*/
public class CopyOnWriteArrayListDemo1 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
list.add("5");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println("list is" + list);
String next = iterator.next();
System.out.println(next);
if (next.equals("2")) {
list.remove("5");
}
if (next.equals("3")) {
list.add("3 found");
}
}
}
}
The flaw is that modifications cannot be made during iterations.
5. CopyOnWriteArrayList application
Change the code in 4
operation result
Why does the iterator end up with 5? This is its characteristic. During the iteration process, you change your content and I will implement it according to the original version.
6. Implementation Principle
The meaning of CopyOnWrite
This means that when writing, copy the original data to the new memory, and then perform the write operation in the new memory, so that after the modification is completed, the pointer points to the new memory area, thus achieving Thread safe. And the applicable scenarios for CopyOnWrite are mostly where the reading situation is relatively high and the writing operations are small.
The summary is to create new copies, separate reading and writing, and the old container is immutable.
Iterator comparison
import java.util.Iterator;
import java.util.concurrent.CopyOnWriteArrayList;
/**
* Description: Compare two iterators
*/
public class CopyOnWriteArrayListDemo2 {
public static void main(String[] args) throws InterruptedException {
CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>(new Integer[]{1, 2, 3});
System.out.println(list);
Iterator<Integer> itr1 = list.iterator();
list.remove(2);
Thread.sleep(1000);
System.out.println(list);
Iterator<Integer> itr2 = list.iterator();
itr1.forEachRemaining(System.out::println);
itr2.forEachRemaining(System.out::println);
}
}
It can be seen that the iterator is related to the state when the iterator is generated, and does not change in real time.
Source code analysis
It is an array array, and ReentrantLock() is used when locking.
The above addition operation is locked. Let’s take a look at the get() method.
The entire get method is not locked, and the read operation will not be blocked.
7. Disadvantages
Five, concurrent queues
1. Why use queue
Queues can pass data between threads: producer consumer model, bank transfer
The burden of considering thread safety has been shifted to “queues”
2. Blocking queue BlockingQueue
What is a blocking queue
Blocking function: the two most distinctive methods with blocking function
-
take() method: Get and remove the head node of the queue. Once there is no data in the queue when take is executed, it will block until there is data in the queue.
-
put() method: insert elements. But if the queue is full, then insertion cannot continue, and it will block until there is free space in the queue.
-
Whether it is bounded (how big the capacity is): This is a very important attribute. Unbounded queue means that it can accommodate a lot (Integer.MAX_VALUE, which is about 2 times 31 times. It is a very large number and can be considered to have unlimited capacity. )
-
The relationship between blocking queue and thread pool: blocking queue is an important part of thread pool
BlcokingQueue’s main method
3. important implementation of ArrayBlockingQueue
Use Cases
There are 10 interviewers and only 1 interviewer in total. There are 3 seats in the hall for the interviewers to rest. The interview time for each person is 10 seconds, simulating the interview scene for everyone.
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
/**
* Description: TODO
*/
public class ArrayBlockingQueueDemo {
public static void main(String[] args) {
ArrayBlockingQueue<String> queue = new ArrayBlockingQueue<String>(3);
Interviewer r1 = new Interviewer(queue);
Consumer r2 = new Consumer(queue);
new Thread(r1).start();
new Thread(r2).start();
}
}
class Interviewer implements Runnable {
BlockingQueue<String> queue;
public Interviewer(BlockingQueue queue) {
this.queue = queue;
}
@Override
public void run() {
System.out.println("All 10 candidates are here");
for (int i = 0; i < 10; i + + ) {
String candidate = "Candidate" + i;
try {
queue.put(candidate);
System.out.println("arranged" + candidate);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
try {
queue.put("stop");
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
class Consumer implements Runnable {
BlockingQueue<String> queue;
public Consumer(BlockingQueue queue) {
this.queue = queue;
}
@Override
public void run() {
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
String msg;
try {
while(!(msg = queue.take()).equals("stop")){
System.out.println(msg + "Arrived");
}
System.out.println("All candidates have ended");
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
Source code analysis
4. LinkedBlockingQueue
Unbounded, capacity is Integer.MAX_VALUE, internal structure: Node, two locks.
Construction method
Internal attributes: There are two locks, take and put locks
put method
If it is full, take a rest. If it is not full, put the node into the queue.
5. Other blocking queues
PriorityBlockingQueue
Support priority
Natural order (rather than first-in-first-out)
unbounded queue
Thread-safe version of PriorityQueue
SynchronusQueue
DelayQueue
6. Non-blocking concurrent queue
7. How to choose a queue that suits you
Consider boundaries, space, throughput
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Java Skill Tree CollectionMap Interface 132160 people are learning the system