“This is the 19th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”
Java concurrent Collection
The java.util.concurrent package was introduced in JDK1.5, where a set of thread-safe collections, called concurrent collections, is defined as an alternative to synchronous collections.
| A non-thread-safe collection | Concurrent collections | A common interface |
|---|---|---|
| ArrayList | CopyOnWriteArrayList | List |
| LinkedList | ConcurrentLinkedQueue | Queue |
| HashSet | CopyOnWriteArraySet | Set |
| TreeSet | ConcurrentSkipListSet | SortedSet |
| HashMap | ConcurrentHashMap | Map |
| TreeMap | ConcurrentSkipListMap | SortedMap |
There are two ways to implement thread-safe traversal with concurrent collections:
1. One is to traverse the snapshot of the traversal collection. Snapshot (the Snapshot) refers to the create iterator iterator object to set the internal data structures to create a copy of it reflects in the iteration of the moment condition, each thread in the iteration traversal collection, will create a copy of this thread, is equivalent to the Snapshot is unique thread object, so do not need to lock in the traversal operation. In addition, snapshots are read-only, so the returned Iterator does not support remove(). The advantage of this quick traversal mode is that the traversal operation and update operation do not affect each other, but the disadvantage is that there are too many collection elements, and the cost of creating a snapshot is high. The two collections CopyOnWriterArrayList and CopyOnWriteArraySet are quick traversal.
2, the other traversal is quasi-real-time traversal, quasi-actual traversal is not for copy traversal, nor does it use locks to ensure thread safety, traversal operation and update can be carried out concurrently, this traversal mode supports remove() operation of iterator. Concurrent collections such as ConcurrentLinkedQueue and ConcurrentHashMap use this quasi-real-time traversal approach.
Concurrent collections internally do not use locks for thread-safe purposes, use CAS operations, or optimize locks such as using extremely fine-grained locks. Compared with synchronous sets, the throughput of programs using concurrent sets increases significantly. As the number of concurrent sets increases, the thread context switch caused by contention for locks used within the set will increase.
CopyOnWriterArrayList collection
The ArrayList collection is one of the most frequently used collections. Its underlying data structure is array, and the underlying data structure is array to store the elements of the collection. It is not thread-safe. Develop multithreaded program, can use synchronous collection Vector, or call the Collections. SynchronizedList () to convert the ArrayList is not thread-safe thread safe.
In many applications, the read operation may be much faster than the write operation. It is desirable that the read operation be as fast as possible and the write operation be slower. Read operation will not modify the original data, so every time when reading lock is a waste of resources, the synchronous Vector set and the Collections. SynchronizedList () returns the thread safety set, each time will lock synchronization when reading data, they read data efficiency is low. According to the read-write lock concept, the read lock and the read lock do not conflict, the read operation will be hindered by the write operation, the read operation must wait, if the read operation, also need to wait.
To maximize read performance, the CopyOnWriteArrayList collection is referenced in JDK5, which reads data without locking at all, and writes do not block reads. From the collection class name CopyOnWrite makes a copy of itself as it writes. That is, when writing data to a collection, it does not modify the original content, but copies the original content of the collection to a copy, writes data to the copy, and then replaces the original data with the copy after writing.
The CopyOnWriteArrayList collection is quick traversal and does not support deletion during iteration.
ConcurrentLinkedQueue
ConcurrentLinkedQueue classes can be seen as a LinkedList class thread-safe version, can be used as Collections. SychronizedList (LinkedList) alternatives. ConcurrentLinkedQueue internal access to shared state variables (Pointers to the head and tail of queues) does not use locks, but uses CAS operations to keep threads safe. ConcurrentLinkedQueue is non-blocking, avoiding the overhead of context switching. The traversal mode is quasi-real-time. ConcurrentLinkedQueue is more suitable for concurrent update and traversal operations than BlockingQueue, with multiple threads adding/removing operations to/from the queue and multiple threads reading data from the collection.
BlockingQueue blocks the queue
ConcurrentLinkedQueue is an efficient read and write queue that can be used to share data between threads in multiple threads using BlockingQueue blocking queues.
BlockingQueue is an interface. There are two main implementation classes ArrayBlockingQueue and LinkedBlockingQueue. ArrayBlockingQueue is an array-based implementation that is more suitable for bounded queues. The amount of elements stored in a queue can be specified when the queue is created. LinkedBlockingQueue is based on a linked list implementation and is suitable for unbounded queues because internal elements can be added dynamically.
BlockingQueue Has two common operations :put() and take(). The put() method adds an element to the end of the queue. Take () takes an element from the head of the queue, and if the queue is empty it waits until there is an element available in the queue.
ConcurrentHashMap collection
A HashTable is a synchronized collection, and no other threads are allowed to participate while one thread manipulates the HashTable.
Collections.synchronizedmap (Map) can return a thread-safe Collections, used the decorator pattern, inside the thread-safe Collections, first to get the mutex lock, complicated with low efficiency.
ConcurrentHashMap is a highly concurrent thread-safe set of maps that can be considered an alternative to HashTable. Prior to JDK7,ConcurrentHashMap internally used extremely fine-grained locks to ensure thread-safety, or the piecewise locking protocol, which supported concurrent operations of 16 threads by default. The ConcurrentHashMap collection has been improved in JDK8, using CAS operations to achieve thread safety.
Random data structures :SkipList skip tables
A jumper is a data structure that can be used for quick queries. In contrast to a balanced tree, only parts of the integer data structure need to be operated on when a jumper is inserted/deleted. That is, in high concurrency cases, you may need a global lock to secure the entire balanced tree, but in the case of a jumper, only a partial lock is required.
Collections that use this data structure are: ConcurrentSkipListSet and ConcurrentSkipListMap, which are thread-safe collections that can sort elements, The ConcurrentSkipListMap collection is a thread-safe collection of maps that can be sorted by key.