1. Copy ideas as you write
Copy on write is an optimization strategy in computer programming. Its core idea is that if there are multiple caller requests at the same time the same resources (such as the data on the memory or disk storage), they will get the same pointer to the same common resources, until a caller tried to change the contents of the resources, the system will truly to copy a copy of a dedicated to the caller, and the other caller can see the original resources still remain the same.
2. Copy at write time in collections
Set data mainly on two operations read, write; Reading is reading content, writing is changing content; When reading data, the storage resource is read. When writing data, the storage resource is reset after the modification is copied. This has the following characteristics:
- Read and write data will not be abnormal due to non-atomic operations
- Write data does not affect each other
- When reading data, it is only up to date, not necessarily up to date in the operating logic at the time
- When writing data, the last data overwrites the previous data
Therefore, if you want to be thread-safe, you must lock on write time
The CopyOnWriteArrayList collection is this copy-on-write + write-on-lock to achieve; CopyOnWriteArraySet internal proxy CopyOnWriteArrayList, and then realize the collection of non-repeated data; So let’s talk about CopyOnWriteArrayList
CopyOnWriteArrayList collection
List collection, internally using arrays to store; Copy and lock while writing; Read data directly;
final transient Object lock = new Object();
private transient volatile Object[] array;
Copy the codeLock is a synchronized lock, array is a resource array, and volatile is used. Writes are visible the next time any thread operates on a resource
3.1 write data
3.1.1 Adding Data
public boolean add(E e) {
synchronized (lock) {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true; }}Copy the code- Synchronized keyword lock
- Get the array resources and copy the data using the Arrays utility class
- Add new data to the copy data
- Write the copy data back
public void add(int index, E element) {
synchronized (lock) {
Object[] elements = getArray();
int len = elements.length;
if (index > len || index < 0)
throw new IndexOutOfBoundsException(outOfBounds(index, len));
Object[] newElements;
int numMoved = len - index;
if (numMoved == 0)
newElements = Arrays.copyOf(elements, len + 1);
else {
newElements = new Object[len + 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index, newElements, index + 1,
numMoved);
}
newElements[index] = element;
setArray(newElements); }}Copy the codeAdd data to a specific index. You can add data anywhere.
- Check whether the index is valid. If not, an exception is thrown
- Copy data in segments, with index as the dividing line (the first and last one can be copied in one segment)
- Copy Data index Position adds data
- Write the copy data back
Ensure that data does not duplicate and increase data
public boolean addIfAbsent(E e) {
Object[] snapshot = getArray();
return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
addIfAbsent(e, snapshot);
}
private boolean addIfAbsent(E e, Object[] snapshot) {
synchronized (lock) {
Object[] current = getArray();
int len = current.length;
if(snapshot ! = current) { // Optimizefor lost race to another addXXX operation
int common = Math.min(snapshot.length, len);
for (int i = 0; i < common; i++)
if(current[i] ! = snapshot[i] && Objects.equals(e, current[i]))return false;
if (indexOf(e, current, common, len) >= 0)
return false;
}
Object[] newElements = Arrays.copyOf(current, len + 1);
newElements[len] = e;
setArray(newElements);
return true; }}Copy the code- Find the index of the data to be added
- If the index >= 0 indicates that it exists, further processing, if not, end
- The lock is repeated to check whether the data exists. If yes, the end
- If no, copy data is added to the tail of the copy data. And write the copy data back
3.1.2 Changing data
public E set(int index, E element) {
synchronized (lock) {
Object[] elements = getArray();
E oldValue = get(elements, index);
if(oldValue ! = element) { int len = elements.length; Object[] newElements = Arrays.copyOf(elements, len); newElements[index] = element;setArray(newElements);
} else {
setArray(elements);
}
returnoldValue; }}Copy the codeChange the specified location data:
- Reads data at the specified position index
- If you specify location data == to change data, write back directly;
- Copy the original data, replace the index data, and write the copy data back
3.1.3 Deleting Data of a specified location
public E remove(int index) {
synchronized (lock) {
Object[] elements = getArray();
int len = elements.length;
E oldValue = get(elements, index);
int numMoved = len - index - 1;
if (numMoved == 0)
setArray(Arrays.copyOf(elements, len - 1));
else {
Object[] newElements = new Object[len - 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements);
}
returnoldValue; }}Copy the codeLock, copy data, copy data, do not include the data to delete, copy data reset back
3.1.4 Deleting specified Data
public boolean remove(Object o) {
Object[] snapshot = getArray();
int index = indexOf(o, snapshot, 0, snapshot.length);
return (index < 0) ? false : remove(o, snapshot, index);
}
private boolean remove(Object o, Object[] snapshot, int index) {
synchronized (lock) {
Object[] current = getArray();
int len = current.length;
if(snapshot ! = current) findIndex: { int prefix = Math.min(index, len);for (int i = 0; i < prefix; i++) {
if(current[i] ! = snapshot[i] && Objects.equals(o, current[i])) { index = i;breakfindIndex; }}if (index >= len)
return false;
if (current[index] == o)
break findIndex;
index = indexOf(o, current, index, len);
if (index < 0)
return false;
}
Object[] newElements = new Object[len - 1];
System.arraycopy(current, 0, newElements, 0, index);
System.arraycopy(current, index + 1,
newElements, index,
len - index - 1);
setArray(newElements);
return true; }}Copy the code- Locate the data
- If no, no processing is required
- Find the location, then lock
- Re-check whether the data has changed. If the data has changed, re-search the position and check whether it is valid. If it is invalid, exit
- To delete the data location, copy the data in two segments, and reset the copy data back
3.1.5 Clearing Data
public void clear() {
synchronized (lock) {
setArray(new Object[0]); }}Copy the codeLock, set to an empty array
3.2 read data
Very simple logic, get data index location
public E get(int index) {
return get(getArray(), index);
}
private E get(Object[] a, int index) {
return (E) a[index];
}
Copy the codeThere are other methods, such as getting the location index, collection size, and so on
CopyOnWriteArraySet collection
It uses CopyOnWriteArrayList internally to delegate functionality; And there are fewer methods
5, summary
- When data is read without locking, the latest data is read. It is possible that the resource was read and not written back
- Data error problems do not occur
- Write locking +volatile ensures that data is executed sequentially at write time, thus ensuring synchronization
- The position of the judgment, lock after the need to re-judge; This improves performance when writing low concurrency
- Use the equal method to determine equality
Technology changes quickly, but the basic technology, the theoretical knowledge is always the same; The author hopes to share the basic knowledge of common technical points in the rest of his life. If you think the article is well written, please pay attention and like it. If there are mistakes in the article, please give me more advice!