List and Set copied on write

When writing copy (CopyOnWrite) the implementation of the principle is to write copy, it is thread-safe, support concurrent access, support, speaking, reading and writing at the same time, its modification action is not supported by the iterator, also won’t throw ConcurrentModifationException, implement some complex operation in atomic way.

1 CopyOnWriteArrayList

Supports two atomic methods:

Public Boolean addIfAbsent(E E); public Boolean addIfAbsent(E E); Public int addAllAbsend(Collection<? extends E> c);Copy the code

The implementation principle of CopyOnWriteArrayList is very simple, internal use of ReentrantLock to maintain an array, read data directly through the subscript returned array elements, modify by ReentrantLock protection, and then copy a new array through the original array, in the new array modification, After that, we point the old array to the new array. The advantage of this is that if another thread is accessing the new array while you are modifying it, the content is still correct because the new array is being modified and the other thread is accessing the old array. To put it more simply, the idea of splitting read and modify into two targets by copying on write is a great idea. Unlike synchronized and CAS, which protect the same target, synchronized and CAS split the two targets directly, cleverly avoiding resource competition. Let’s take a quick look at the add() and get() sources:

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; // Set the contents of the new array to the old array setArray(newElements); return true; } finally {// unlock lock.unlock(); }}Copy the code

As you can see, add() is cas-based write replication and is safe for high concurrency, so let’s look at get():

Public E get(int index) {return get(getArray(), index); } final Object[] getArray() {return array; } private E get(Object[] a, int index) {return (E) a[index]; }Copy the code

As you can see, get() is unlocked because it does not modify the array, so there is no security issue. Inside a for() loop, it is perfectly reasonable to call get() repeatedly to retrieve data, possibly with different results each time because other threads may have modified the data in the meantime.

2 CopyOnWriteArraySet

The CopyOnWriteArrayList implementation is simple and wraps the CopyOnWriteArrayList implementation directly.

Public CopyOnWriteArraySet() {al = new CopyOnWriteArrayList<E>(); } public Boolean add(E E) {return al. AddIfAbsent (E); }Copy the code

CopyOnWriteArrayList/Set uses the idea of copying while writing to avoid resource competition, but the efficiency of copying itself is low, so it is applicable to read far more than write, read more write less, Set is not large scene.

ConcurrentHashMap

Concurrent security, support some complex operation in atomic way, read operation completely parallel, the write operation support certain granularity parallel, with weak consistency, and ConcurrentModificationException.

The following operations are atomic:

// This function is equivalent to the put(key,value) of the HashMap, but this is the V putIfAbsent(K key, V value) of the atom; Boolean remove(Object key, Object value); Boolean repalce(K key, V oldValue, V newValue) Return null V replace(K key, V value)Copy the code

ConcurrentHashMap is basically the same as HashMap, but it is highly concurrent. It uses a fragmented locking technique, that is, the data is split into multiple segments, each with a separate lock, each segment is equivalent to a separate Hash table, and the segmentation is based on the Hash value. The default is 16 segments. But it can be set using the constructor:

// The third argument represents the number of threads supporting Concurrent updates, i.e. the number of segment locks, which Concurrent converts to an NTH power of 2. public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrentLevel);Copy the code

ConcurrentHashMap reads are completely parallel and do not require locks. Write operations are supported by “segment parallel”. For example, if there are 4 segment locks (ABCD), then there will be 4 locks (LockA, LockB, LockC, LockD). If I’m writing A, my LockA is in effect, and if I’m writing B, my LockB is in effect, so I can write in parallel, so I can write in parallel, so that’s kind of the same idea, just like CopyOnWriteArrayList, which splits the target, except CopyOnWriteArrayList splits the target of the read/write operation, ConcurrentHashMap splits the target of the write operation, but the idea is the same, namely “target splitting”, or “target refinement”, which is a NB idea worth learning.

Weak ConcurrentHashMap consistency only refers to: If another thread is making changes during traversal, the iterator will not reflect the changes if they occur in the part that has already been traversed. If they occur in the part that has not yet been traversed, the iterator will reflect them. This is weak consistency, of course.

Jump table

Based on jump table ConcurrentSkipListMap and ConcurrentSkipListSet, don’t use the lock, all operations can be parallel, ConcurrentModificationException, has weak consistency, orderly, The default is natural.

ConcurrentSkipListSet is a wrapper around the ConcurrentSkipListMap implementation, we just need to understand the latter.

The ConcurrentSkipListMap size() function takes O(n) time to iterate through all the elements, and the number of elements may have changed after the iterate, because of one of the disadvantages of not using locks.

The implementation code of the jump table is very complex, even using the GOto statement, we just look at the principle.

Jump table is based on the list, add multilayer index on the basis of the linked list, a bit like a tree, accurately, it should be a directed graph, such as a collection:,6,7,9,12,17,19,21,25,26 {3} structure is as follows:Where each layer is ordered, the higher one is 1/2 of the lower one, and so on, the right pointer points to the next node of the same layer, the lower pointer points to the same node of the next layer, on this structure, you can proceedBinary search. The lookup process is simple, start at the top of the comparison, move to the right if greater, otherwise move down, as shown in the following example of finding 8 and 19:The time for this search is order log of n,

That’s how they work, but how are they thread-safe? This principle is very complex, using the famous Amdar law, interested in the relevant paper, or directly read the JDK in the relevant notes, no more nonsense here.

Other concurrent queues

Here’s a quick look at the common concurrent queues, most of which are used in thread pools.

Non-blocking concurrent queues: ConcurrentLinkedQueue and ConcurrentLiknedDeque

Both use CAS and are based on a linked list, so there is no size limit. Size () is not a constant operation and needs to traverse the whole set. Queue is a unidirectional linked list, with one end joining the Queue and the other end leaving the Queue. Deque is a two-end Queue, and both ends can join and leave the Queue.

Normal blocking queue: ArrayBlockingQueue (based on array) and LinkedBlockingQueue/LinkedBolckingDeque (based on the list)

Both internally use ReentrantLock and Condition, where ArrayBlockingQueue is based on a circular array and the other two are based on a linked list and have no size limit.

PriorityBlockingQueue: PriorityBlockingQueue

This is similar to the PriorityQueue, which is queued and queued according to priority. There is no size limit, and it is implemented using ReentrantLock and Condition.

Delay blocking queue: DelayQueue

Based on the implementation of PriorityQueue, there is no size limit, can be used to implement scheduled tasks, according to the delay time of the element out of the queue.

Other blocking queues: SynchronousQueue and LinkedTransferQueue

SynchronousQueue has no space to store elements. Its entry must wait for another thread to dequeue, and the same is true for dequeuing. Otherwise, both put and take wait. The thread pool: Executors newCachedThreadPool () used in the SynchronousQueue will. LinkedTransferQueue is based on a linked list, has no size limit and is suitable for the producer-consumer model.

In this chapter, the most useful one is CopyOnWriteArratList and ConcurrentHashMap’s “target granular idea”. In other words, it means to “granulize” the competitive target, so that “competition for the same large particle” becomes “access to different small particles”, thus avoiding competition.