Concurrent Sets

I learned about List (ArrayList|LinkedList), Set (HashSet|TreeSet), and Map (HashMap|TreeMap) collections, which are only suitable for single-threaded use. If multiple threads operate on a collection in a multithreaded environment, problems arise:

Code example:

package basis.stuJUC.stuSyncCollection;

import java.util.ArrayList;
import java.util.List;

public class TestCollection {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        for (int i = 0;i<5;i++){
            int temp = i;
            new Thread(()->{
                for (int j = 0;j<5;j++){
                    list.add(Thread.currentThread().getName()+"-"+temp+"-"+j);
                    System.out.println(list);
                }
            }).start();
        }
    }
}

Concurrent Modification Exception may occur in the above code, as follows:

java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
	at java.util.AbstractCollection.toString(AbstractCollection.java:461)
	at java.lang.String.valueOf(String.java:2994)
	at java.io.PrintStream.println(PrintStream.java:821)
	at basis.stuJUC.stuSyncCollection.TestCollection.lambda$main$0(TestCollection.java:14)
	at java.lang.Thread.run(Thread.java:748)

To enable collections to work in a multi-threaded environment, several synchronized start methods are provided in the Collecionts toolkit class to turn a single-threaded collection into a collection that supports concurrency.

Examples:

package basis.stuJUC.stuSyncCollection;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class Demo1 {
    public static void main(String[] args) {
        List<String> alllist= Collections.synchronizedList(new ArrayList<>());
        for(int i=0;i<5;i++){
            int temp=i;
            new Thread(new Runnable() {
                @Override
                public void run() {
                    for(int j=0;j<5;j++){
                        alllist.add(Thread.currentThread().getName()+" "+temp+" "+j);
                    }
                    System.out.println(alllist);
                }
            }).start();

        }

    }
}

Collections partial source code:

        public int hashCode() {
            synchronized (mutex) {return list.hashCode();}
        }

        public E get(int index) {
            synchronized (mutex) {return list.get(index);}
        }
        public E set(int index, E element) {
            synchronized (mutex) {return list.set(index, element);}
        }
        public void add(int index, E element) {
            synchronized (mutex) {list.add(index, element);}
        }
        public E remove(int index) {
            synchronized (mutex) {return list.remove(index);}
        }

        public int indexOf(Object o) {
            synchronized (mutex) {return list.indexOf(o);}
        }
        public int lastIndexOf(Object o) {
            synchronized (mutex) {return list.lastIndexOf(o);}
        }

It can be seen that the way to turn common collections into concurrent collections in Collections is to use synchronized keywords to lock operations. This strategy is very inefficient, so it is seldom used in actual development.

To better implement high concurrent access processing for collections, the JUC package provides us with a new set of concurrent container classes as follows:

• ConcurrentHashMap
• ConcurrentSkipListMap
• ConcurrentSkipListSet
• CopyOnWriteArrayList
• CopyOnWriteArraySet
• ArrayBlockingQueue
• LinkedBlockingQueue
• PriorityBlockingQueue
• LinkedBlockingDeque
• ConcurrentLinkedQueue

3,CopyOnWriteArrayList and CopyOnWriteArraySet

List and Set Collections:

• CopyOnWriteArrayList is equivalent to thread-safe ArrayList, which implements the List interface. CopyOnWriteArrayList supports high concurrency.
• CopyOnWriteArraySet is equivalent to thread-safe HashSet, which inherits the AbstractSet class. CopyOnWriteArraySet contains a CopyOnWriteArrayList object, which is implemented through CopyOnWriteArrayList.

(1) What is Copy-On-Write

Copy-On-Write, short for COW, is an optimization strategy for programming. The basic idea is that everyone is sharing the same content from the beginning. When someone wants to modify the content, they will really go out to form a new content and then change it. This is a delayed lazy strategy. Since JDK 1.5, two concurrency containers using CopyOnWrite mechanism have been provided in Java concurrency packages. They are CopyOnWriteArrayList and CopyOnWriteArraySet. CopyOnWrite containers are very useful and can be used in many concurrent scenarios.

(2) What is a CopyOnWrite container?

CopyOnWrite container is the container replicated at write time. The popular understanding is that when we add elements to a container, instead of directly adding them to the current container, we first Copy the current container into a new container, then add elements to the new container, and then point the reference of the original container to the new container. The advantage of this is that we can read the CopyOnWrite container concurrently without locking, because the current container will not add any elements. So the CopyOnWrite container is also an idea of separation of read and write, reading and writing different containers.

(3) Use of CopyOnWriteArrayList

package basis.stuJUC.stuSyncCollection;

import java.util.Random;
import java.util.concurrent.CopyOnWriteArrayList;

public class TestCopyOnWriteList {
    public static void main(String[] args) {
        CopyOnWriteArrayList<String> copyOnWriteArrayList=new CopyOnWriteArrayList<>();
        copyOnWriteArrayList.add("xxx");
        copyOnWriteArrayList.add("aaa");
        copyOnWriteArrayList.add("aaa");
        copyOnWriteArrayList.add("bbb");

        for (int i = 0; i < 10; i++) {
            new Thread(new Runnable() {
                @Override
                public void run() {
                    copyOnWriteArrayList.add(Thread.currentThread().getName() + new Random().nextInt(1000));
                    System.out.println(copyOnWriteArrayList);
                }
            }).start();
        }
    }
}

Results (Part):

[xxx, aaa, aaa, bbb, Thread-1419]
[xxx, aaa, aaa, bbb, Thread-1419, Thread-025]
[xxx, aaa, aaa, bbb, Thread-1419, Thread-025, Thread-2292]
[xxx, aaa, aaa, bbb, Thread-1419, Thread-025, Thread-2292, Thread-322]
[xxx, aaa, aaa, bbb, Thread-1419, Thread-025, Thread-2292, Thread-322, Thread-4737, Thread-5572]
[xxx, aaa, aaa, bbb, Thread-1419, Thread-025, Thread-2292, Thread-322, Thread-4737]

As can be seen from the results, CopyOnWriteArrayList is similar to List in that elements in the set are orderly and repeatable, because CopyOnRwriteArrayList implements the List interface.

CopyOnRwriteArrayList class declaration:

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;

    final transient ReentrantLock lock = new ReentrantLock();

    private transient volatile Object[] array;
}

(4) Use of CopyOnWriteArraySet

CopyOnWriteArraySet is basically the same as CopyOnRwriteArrayList. CopyOnWriteArraySet elements are ordered but do not allow duplication. The difference between them is the same as that between Set and List collections, because CopyOnWriteArraySet inherits the Set interface.

CopyOnWriteArraySet class declaration:

package java.util.concurrent;
/**
 * @see CopyOnWriteArrayList
 * @since 1.5
 * @author Doug Lea
 * @param <E> the type of elements held in this collection
 */
public class CopyOnWriteArraySet<E> extends AbstractSet<E>
        implements java.io.Serializable {
    private static final long serialVersionUID = 5457747651344034263L;

    private final CopyOnWriteArrayList<E> al;
}

Map collection:

• Concurrent HashMap is a thread-safe hash table (equivalent to thread-safe HashMap); it inherits from the AbstractMap class and implements the Concurrent Map interface. Concurrent HashMap was implemented by "lock segmentation" in jdk1.7 and before, and was implemented by CAS algorithm after jdk1.8, which supports concurrency.
• Concurrent SkipListMap is a thread-safe ordered hash table (equivalent to thread-safe TreeMap); it inherits from the AbstactMap class and implements the Concurrent Navigable Map interface. Concurrent SkipListMap is implemented by "table hopping", which supports concurrency.

Set collection:

• Concurrent SkipListSet is an orderly set of thread-safe (equivalent to thread-safe TreeSet); it inherits from AbstractSet and implements the Navigable Set interface. Concurrent SkipListSet is implemented through Concurrent SkipListMap, which also supports concurrency.

(1)ConcurrentHashMap

Reference blog: https://www.cnblogs.com/chengxiao/p/6842045.html

HashMap :

First of all, HashMap, HashMap is thread insecure, in concurrent environment, may form a ring list (expansion may be caused by Baidu google or view source code analysis), resulting in get operation, cpu idle, so, using HashMap in concurrent environment is very dangerous.

HashTable :

HashTable and HashMap are almost the same in principle, except that 1.HashTable does not allow key and value to be null; 2.HashTable is thread-safe. However, the implementation cost of HashTable thread security policy is too high. It is simple and rude. All relevant operations of get/put are synchronized, which is equivalent to adding a big lock to the whole hash table. When multithreaded access, as long as one thread accesses or operates on the object, the other threads can only block, which is equivalent to blocking all the other threads. Operational serialization can result in poor performance in highly competitive concurrent scenarios.

HashTable performance is poor mainly because all operations need to compete for the same lock, and if there are multiple locks in the container, each locks a piece of data, so that when multi-threaded access to different sections of data, there will be no lock competition, which can effectively improve concurrency efficiency. This is the idea of "segmented lock" adopted by Concurrent HashMap. After jdk1.8, when Concurrent HashMap is written, CAS lock-free algorithm is used to further improve the writing efficiency. The main feature of Map set is to do data query processing, so the security of data update and the concurrency of data query are considered in Concurrent HashMap design.

(2) Use of Concurrent HashMap

package basis.stuJUC.stuSyncCollection;

import java.util.concurrent.ConcurrentHashMap;

public class StuConcurrentHashMap {
    public static void main(String[] args) {
        ConcurrentHashMap<String,String> concurrentHashMap=new ConcurrentHashMap<>();
        for(int i=0;i<5;i++){
            int temp=i;
            new Thread(new Runnable() {
                @Override
                public void run() {
                    for(int j=0;j<5;j++) {
                        concurrentHashMap.put(temp+"--"+j, Thread.currentThread().getName());
                    }
                    System.out.println(concurrentHashMap);
                }
            }).start();
        }
    }
}

Concurrent HashMap class declaration

package java.util.concurrent;

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {
    private static final long serialVersionUID = 7249069246763182397L;
    
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    private static final int DEFAULT_CAPACITY = 16;

    static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;

    private static final float LOAD_FACTOR = 0.75f;

    static final int TREEIFY_THRESHOLD = 8;

    static final int UNTREEIFY_THRESHOLD = 6;

    static final int MIN_TREEIFY_CAPACITY = 64;

    private static final int MIN_TRANSFER_STRIDE = 16;

    private static int RESIZE_STAMP_BITS = 16;

    private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;

    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;

}

The ConcurrentHashMap collection inherits the AbstractMap class and implements the ConcurrentMap interface. The ConcurrentHashMap class, like the HashMap collection, declares many constants that represent the properties of the original ConcurrentMap object.

(3) Concurrent SkipListMap and Concurrent SkipListSet

Concurrent SkipListMap and Concurrent SkipListSet are thread-safe TreeMap and TreeSet, using methods similar to TreeMap and TreeSet.

5,Queue

Queue queue:

• Array BlockingQueue is a thread-safe bounded blocking queue implemented by arrays.
• LinkedBlockingQueue is a blocking queue implemented by a one-way list with FIFO sorting elements.
• LinkedBlockingDeque is a two-way concurrent blocking queue implemented by a two-way linked list, which supports both FIFO and FILO operations.
• Concurrent LinkedQueue is an unbounded queue implemented by a one-way linked list, which sorts elements by FIFO.
• Concurrent LinkedDeque is an unbounded queue implemented by a two-way linked list, which supports both FIFO and FILO modes of operation.

(1) Use Array BlockingQueue to implement producers and consumers

Producer:

package basis.stuJUC.stuSyncCollection;

import java.util.concurrent.ArrayBlockingQueue;

/*
 * Producer
 */
public class Producer{

    private ArrayBlockingQueue<String> bq;

    public Producer(ArrayBlockingQueue<String> bq) {
        this.bq = bq;
    }

    public void input(String e) {
        try {
            bq.put(e);
            System.out.println(Thread.currentThread().getName()+"Generated"+e);
        } catch (InterruptedException e1) {
            e1.printStackTrace();
        }
    }
}

Consumer:

package basis.stuJUC.stuSyncCollection;

import java.util.concurrent.ArrayBlockingQueue;

public class Consumer {
    private ArrayBlockingQueue<String> bd;

    public Consumer(ArrayBlockingQueue<String> bd) {
        this.bd = bd;
    }
    public void output(){
        try {
            String take = bd.take();
            System.out.println(Thread.currentThread().getName()+"Consumption"+take);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

Test class:

package basis.stuJUC.stuSyncCollection;

import java.util.concurrent.ArrayBlockingQueue;


public class StuArrayBlockingQueue {
    public static void main(String[] args) {
        ArrayBlockingQueue<String> bq=new ArrayBlockingQueue<>(1);
        Producer producer=new Producer(bq);
        Consumer consumer=new Consumer(bq);
        new Thread(new Runnable() {
            @Override
                public void run() {
                    for(int i=0;i<30;i++){
                        producer.input("Generated"+i);
                    }
            }
        }).start();
        new Thread(new Runnable() {
            @Override
            public void run() {
                for(int i=0;i<30;i++){
                    consumer.output();
                }
            }
        }).start();
    }
}

Test results (part):

Thread-0 generates 0
 Thread-0 generates 1
 Thread-1 consumes generated 0
 Thread-1 consumes and generates 1
 Thread-0 generates 2
 Thread-0 generates 3