前言
一看這個，咋這么長的名字，記起來有點麻煩呀！這個類使用的情況不多，最近在看EventBus的時候看到過，所以還是跳出來學(xué)習(xí)一下，看一下這個類的廬山真面目
是什么東西？
CopyOnWrite，大概能猜到跟寫時復(fù)制有關(guān)，為什么要有這個東西？不難想出這是為了線程安全而設(shè)計的，否則直接用 ArrayList 就行了，那好了，說的這個東西就是一個ArrayList ，在此基礎(chǔ)上，他是線程安全的，采用了寫時復(fù)制的方法，那我們可以思考一下，他是怎么做的，如果給我們設(shè)計，我們要怎么做呢？
前世今生
它沒有擴展 ArrayList，即使是以此結(jié)尾，直接實現(xiàn)了 List，也實現(xiàn)了RandomAccess，Cloneable， Serializable 接口，Doug Lea 寫的，就是厲害
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
源碼解析
屬性
- 我們看到了一個鎖，聰明的你可能想到了，是不是可以加鎖來實現(xiàn)線程的安全？在寫的時候加鎖，讀的時候可以不用鎖
- 同樣使用了 Volatile 的 Object 數(shù)組存儲元素
- 兩個final 方法設(shè)置 elements
/**
* The lock protecting all mutators. (We have a mild preference
* for builtin monitors over ReentrantLock when either will do.)
*/
final transient Object lock = new Object();
/** The array, accessed only via getArray/setArray. */
// Android-changed: renamed array -> elements for backwards compatibility b/33916927
private transient volatile Object[] elements;
/**
* Gets the array. Non-private so as to also be accessible
* from CopyOnWriteArraySet class.
*/
final Object[] getArray() {
return elements;
}
/**
* Sets the array.
*/
final void setArray(Object[] a) {
elements = a;
}
構(gòu)造函數(shù)，默認大小為0，也可以傳入集合類對象進行復(fù)制，或者直接傳入數(shù)組，這里用到了 Arrays.copyOf，這是一個數(shù)組復(fù)制的靜態(tài)函數(shù)，底層使用了System.arraycopy，效率很高，反悔了一個新的數(shù)組
/**
* Creates an empty list.
*/
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
/**
* Creates a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection of initially held elements
* @throws NullPointerException if the specified collection is null
*/
public CopyOnWriteArrayList(Collection<? extends E> c) {
Object[] elements;
if (c.getClass() == CopyOnWriteArrayList.class)
elements = ((CopyOnWriteArrayList<?>)c).getArray();
else {
elements = c.toArray();
// defend against c.toArray (incorrectly) not returning Object[]
// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
if (elements.getClass() != Object[].class)
elements = Arrays.copyOf(elements, elements.length, Object[].class);
}
setArray(elements);
}
/**
* Creates a list holding a copy of the given array.
*
* @param toCopyIn the array (a copy of this array is used as the
* internal array)
* @throws NullPointerException if the specified array is null
*/
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
函數(shù)
get 沒有加鎖，直接返回，由于volatile，能保證讀到最新的值
private E get(Object[] a, int index) {
return (E) a[index];
}
set，果不其然，對添加數(shù)據(jù)使用了加鎖，首先檢查這個位置是否存在對象，如果不存在，那么需要拷貝一個新的數(shù)組，并且添加一個元素，在調(diào)用elements更新屬性；如果存在了，也需要設(shè)置數(shù)組，保證volatile的語義，這里不是很明白，既然都加了鎖，不需要更新數(shù)據(jù)時還要更新數(shù)據(jù)。最后返回 oldValue。
至于為什么，在這里看到有人討論 concurrency-interest，但感覺也沒有數(shù)清楚，不過我看到了，之前的jdk版本使用了 Lock而不是 synchronized ，可見synchronized 的性能以及大大提高
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 {
// Not quite a no-op; ensures volatile write semantics
setArray(elements);
}
return oldValue;
}
}
add，依然使用鎖，同樣先讀數(shù)組，在復(fù)制出一個新的數(shù)組，注意，數(shù)組長度為 len + 1，預(yù)留了一個位置，因此這個數(shù)據(jù)結(jié)構(gòu)并沒有類似 *2 的擴容機制，而是一個一個添加，個人覺得這樣效率會大打折扣，當(dāng)然，為了 tradeoff。在添加元素，最后返回true
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;
}
}
add，在某個位置插入一個元素，首先先檢查index，看是否越界，這里使用了一個小技巧，計算了移動距離，如果為0，即添加到最后，則直接復(fù)制，否則就需要調(diào)用兩次 copy 函數(shù)進行復(fù)制
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);
}
}
remove 可以刪除某個索引的元素
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);
}
return oldValue;
}
}
remove也可以刪除某個對象，不過需要遍歷數(shù)組
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 static int indexOf(Object o, Object[] elements,
int index, int fence) {
if (o == null) {
for (int i = index; i < fence; i++)
if (elements[i] == null)
return i;
} else {
for (int i = index; i < fence; i++)
if (o.equals(elements[i]))
return i;
}
return -1;
}
最后還是調(diào)用這個，也是線程安全的函數(shù)，邏輯也很簡單
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;
break findIndex;
}
}
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;
}
}
removeRange 刪除一定范圍，不用說了，相信他的代碼你早就知道該怎么寫了
void removeRange(int fromIndex, int toIndex) {
synchronized (lock) {
.....
}
}
addIfAbsent 如果不存在才添加
public boolean addIfAbsent(E e) {
Object[] snapshot = getArray();
return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
addIfAbsent(e, snapshot);
}
/**
* A version of addIfAbsent using the strong hint that given
* recent snapshot does not contain e.
*/
private boolean addIfAbsent(E e, Object[] snapshot) {
synchronized (lock) {
Object[] current = getArray();
int len = current.length;
if (snapshot != current) {
// Optimize for 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;
}
}
類似還有 addAllIfAbsent，寫得還是很不錯的，畢竟是 Doug Lea
public int addAllAbsent(Collection<? extends E> c) {
Object[] cs = c.toArray();
if (cs.length == 0)
return 0;
synchronized (lock) {
Object[] elements = getArray();
int len = elements.length;
int added = 0;
// uniquify and compact elements in cs
for (int i = 0; i < cs.length; ++i) {
Object e = cs[i];
if (indexOf(e, elements, 0, len) < 0 &&
indexOf(e, cs, 0, added) < 0)
cs[added++] = e;
}
if (added > 0) {
Object[] newElements = Arrays.copyOf(elements, len + added);
System.arraycopy(cs, 0, newElements, len, added);
setArray(newElements);
}
return added;
}
}
小結(jié)
分析別人的源碼的過程本身就是一個學(xué)習(xí)的過程，能從中學(xué)到很多新的東西，并且能夠鞏固以前的知識。
歡迎討論～
