Write up front: Java containers are a lot of stuff, and this article simply enumerates concurrent containers and how to use them, without elaborating on the source code. You can use this article as an index to learn the similarities and differences between different containers, choose which containers to use, or learn more about the underlying principles.
Introduction of the container
In the beginning, there were only two containers in the JDK, Vector and Hashtable. Both of them were implemented with synchronized by default. Then gradually developed to the present container is mainly divided into two interfaces Map and Collection. Collections are divided into three categories: List, Set, and Queue. A brief description of the containers involved in concurrency follows.
fromHashTabletoConcurrentHashMap
The following four maps are described based on a scenario where 100 threads throw 1 million values into the Map, recording the Mapcount value and write time; Let another 100 threads read the values in the Map and record the reading time.
Hashtable
public class TestHashtable {
static Hashtable<UUID, UUID> m = new Hashtable<>();
static int count = 1000000;
static UUID[] keys = new UUID[count];
static UUID[] values = new UUID[count];
static final int THREAD_COUNT = 100;
static {
for (int i = 0; i < count; i++) { keys[i] = UUID.randomUUID(); values[i] = UUID.randomUUID(); }}static class MyThread extends Thread {
int start;
int gap = count / THREAD_COUNT;
public MyThread(int start) {
this.start = start;
}
@Override
public void run(a) {
for (inti = start; i < start + gap; i++) { m.put(keys[i], values[i]); }}}public static void main(String[] args) {
// write
long start = System.currentTimeMillis();
Thread[] threads = new Thread[THREAD_COUNT];
for (int i = 0; i < threads.length; i++) {
threads[i] = new MyThread(i * (count / THREAD_COUNT));
}
for (Thread t : threads) {
t.start();
}
for (Thread t : threads) {
try {
t.join();
} catch(InterruptedException e) { e.printStackTrace(); }}long end = System.currentTimeMillis();
System.out.println(end - start);
System.out.println(m.size());
// read
start = System.currentTimeMillis();
for (int i = 0; i < threads.length; i++) {
threads[i] = new Thread(() -> {
for (int j = 0; j < 10000000; j++) {
m.get(keys[10]); }}); }for (Thread t : threads) {
t.start();
}
for (Thread t : threads) {
try {
t.join();
} catch(InterruptedException e) { e.printStackTrace(); } } end = System.currentTimeMillis(); System.out.println(end - start); }}Copy the codeThe final output is:
237
1000000
32578
Copy the codeHashMap
This doesn’t make sense to test, because it’s obvious that count doesn’t reach 1000000, and it’s not thread-safe.
SynchronizedHashMap
Use the Collections. SynchronizedMap (new HashMap < > ()) to try;
274
1000000
35984
Copy the codeFind the efficiency is about the same, briefly look at the source code. SynchronizedMap is the wrapper class for HashMap, with the final Object mutex lock added; Then thread-safe methods lock the lock. There is no difference in efficiency between locking class objects with Hashtable.
ConcurrentHashMap
Try using ConcurrentHashMap:
425
1000000
592
Copy the codeConcurrentHashMap greatly improves read efficiency. In JDK1.7, each shard is locked, while in JDK1.8, shards are replaced by sychronized + CAS, which further reduces the granularity of the lock and is much more efficient than the original locking of the entire Map. Detailed source code can be read or query other information.
fromVectortoQueue
Consider a scenario where 10 threads consume a container full of 10,000 pieces of data and automatically exit the thread when the data is consumed.
ArrayListorLinkedList
public class TestArrayList {
static List<String> list = new ArrayList<>();
static {
for (int i = 0; i < 10000; i++) {
list.add(i + ""); }}public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
new Thread(() -> {
while (list.size() > 0) {
System.out.println("Consumed" + list.remove(0)); } }).start(); }}}Copy the codeSeveral null values will be output because the last few threads have consumed the last one after the list.size() () > 0 has been consumed by other threads.
ArrayListorLinkedListlock
It is essentially the same as a Vector, because it locks an entire array or list, which is inefficient.
public class TestLock {
static List<String> list = new ArrayList<>();
static {
for (int i = 0; i < 10000; i++) {
list.add(i + ""); }}public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
new Thread(() -> {
while (true) {
synchronized (list) {
if (list.size() <= 0) {
break;
}
System.out.println("Consumed" + list.remove(0)); } } }).start(); }}}Copy the codeVector
Now we use Vector, which is thread-safe because many of the internal methods are synchronized. The final output is fine.
public class TestVector {
static Vector<String> vector = new Vector<>();
static {
for (int i = 0; i < 10000; i++) {
vector.add(i + ""); }}public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
new Thread(() -> {
while (vector.size() > 0) {
System.out.println("Consumed" + vector.remove(0)); } }).start(); }}}Copy the codeQueue
ConcurrentLinkedQueue = ConcurrentLinkedQueue = ConcurrentLinkedQueue = ConcurrentLinkedQueue = ConcurrentLinkedQueue = ConcurrentLinkedQueue
public class TestQueue {
static Queue<String> queue = new ConcurrentLinkedQueue<>();
static {
for (int i = 0; i < 10000; i++) {
queue.add(i + ""); }}public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
new Thread(() -> {
while (true) {
String s = queue.poll();
if (s == null) {
break;
}
System.out.println("Consumed"+ s); } }).start(); }}}Copy the codeConcurrent container
ConcurrentMap
Concurrent containers commonly used by Map:
-
ConcurrentHashMap: A high-concurrency container implemented with hash tables. If you need a high-concurrency Map that can be used for sorting, ConcurrentTreeMap comes naturally to mind. However, ConcurrentTreeMap is not implemented because of the complexity of manipulating trees with CAS. The sorting requirement is implemented by the hop table-based ConcurrentSkipListMap.
-
ConcurrentSkipListMap: a highly concurrent container implemented by a hop table and the Map is ordered;
CopyOnWrite
CopyOnWrite is copying while writing. There are two containers CopyOnWriteList and CopyOnWriteSet. CopyOnWriteSet is implemented based on CopyOnWriteList. CopyOnWriteList uses ReentrantLock in JDK8 and synchronized in JDK11.
jdk8:
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally{ lock.unlock(); }}Copy the codejdk11:
public boolean add(E e) {
synchronized (lock) {
Object[] es = getArray();
int len = es.length;
es = Arrays.copyOf(es, len + 1);
es[len] = e;
setArray(es);
return true; }}Copy the codeAnd you can see that when I write it I’m going to copy the original array and I’m going to add a new element at the end, and I’m going to point the container to the new array. Because each write requires low replication efficiency, it is best used when there are many reads and few writes. Also note that CopyOnWrite only guarantees final consistency, not real-time consistency. Because before the add and remove are complete, the data is still old.
BlockingQueue
BlockingQueue, a BlockingQueue, provides a series of methods for threads to block automatically. First, Queue provides a series of interfaces, such as:
add: Adds an element to the queue. If the element fails to join, an exception is thrownoffer: Adds an element to the queue and returns a Boolean value indicating whether the addition succeededpeek: Value: noremovepoll: Indicates the value andremove
BlockingQueue adds two more methods:
put: Adds elements to a queue, which blocks when the queue is fulltake: Value. If the queue is empty, it will block
Several implementations of BlockingQueue:
LinkedBlockingQueue: using a linked list to implement a blocking queue, an unbounded queue. It’s unbounded, but the upper limit isInteger.MAX_VALUE.ArrayBlockingQueue: is bounded and the capacity needs to be specified. The characteristic of this method is that there is an upper limit of queue capacity, once fullputIt gets blocked.DelayQueue: Implements time sorting. The elements stored in the queue need to be implementedDelayedInterface, that is,compareToandgetDelayMethod to specify collation rules. The queue essentially usesPriorityQueue.PriorityQueue: Internal maintenance of a binary tree, storage data will be sorted first, the smallest priority in the header.SynchronousQueue: If the capacity is 0, callputBlocks waiting for another threadtake, which is equivalent to passing data hand-in-hand to another thread. This queue is widely used in thread scheduling.TransferQueueCompared to:SynchronousQueueOnly one value can be passed, and the queue can be passed to multiple queues. And it provides a new approachtransfer, can block to wait for the other party to get the data before the follow-up work.