本小節是《并發容器》的最后一部分，這一個小節描述的是針對List/Set接口的一個線程版本。
在《并發隊列與Queue簡介》中介紹了并發容器的一個概括，主要描述的是Queue的實現。其中特別提到一點LinkedList是List/Queue的實現，但是LinkedList確實非線程安全的。不管BlockingQueue還是ConcurrentMap的實現，我們發現都是針對鏈表的實現，當然盡可能的使用CAS或者Lock的特性，同時都有通過鎖部分容器來提供并發的特性。而對于List或者Set而言，增、刪操作其實都是針對整個容器，因此每次操作都不可避免的需要鎖定整個容器空間，性能肯定會大打折扣。要實現一個線程安全的List/Set，只需要在修改操作的時候進行同步即可，比如使用java.util.Collections.synchronizedList(List<T>)或者java.util.Collections.synchronizedSet(Set<T>)。當然也可以使用Lock來實現線程安全的List/Set。
通常情況下我們的高并發都發生在“多讀少寫”的情況，因此如果能夠實現一種更優秀的算法這對生產環境還是很有好處的。ReadWriteLock當然是一種實現。CopyOnWriteArrayList/CopyOnWriteArraySet確實另外一種思路。
CopyOnWriteArrayList/CopyOnWriteArraySet的基本思想是一旦對容器有修改，那么就“復制”一份新的集合，在新的集合上修改，然后將新集合復制給舊的引用。當然了這部分少不了要加鎖。顯然對于CopyOnWriteArrayList/CopyOnWriteArraySet來說最大的好處就是“讀”操作不需要鎖了。
我們來看看源碼。
/** The array, accessed only via getArray/setArray. */
private volatile transient Object[] array;
public E get(int index) {
return (E)(getArray()[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;
}
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
public void clear() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
setArray(new Object[0]);
} finally {
lock.unlock();
}
}
對于上述代碼，有幾點說明：
- List仍然是基于數組的實現，因為只有數組是最快的。
- 為了保證無鎖的讀操作能夠看到寫操作的變化，因此數組array是volatile類型的。
- get/indexOf/iterator等操作都是無鎖的，同時也可以看到所操作的都是某一時刻array的鏡像（這得益于數組是不可變化的）
- add/set/remove/clear等元素變化的都是需要加鎖的，這里使用的是ReentrantLock。
這里有一段有意思的代碼片段。
public E set(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
Object oldValue = 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 (E)oldValue;
} finally {
lock.unlock();
}
}
final void setArray(Object[] a) {
array = a;
}
對于set操作，如果元素有變化，修改后setArray(newElements);將新數組賦值還好理解。那么如果一個元素沒有變化，也就是上述代碼的else部分，為什么還需要進行一個無謂的setArray操作？畢竟setArray操作沒有改變任何數據。
對于這個問題也是很有意思，有一封郵件討論了此問題（1、2、3）。
大致的意思是，盡管沒有改變任何數據，但是為了保持“volatile”的語義，任何一個讀操作都應該是一個寫操作的結果，也就是讀操作看到的數據一定是某個寫操作的結果（盡管寫操作沒有改變數據本身）。所以這里即使不設置也沒有問題，僅僅是為了一個語義上的補充（個人理解）。
這里還有一個有意思的討論，說什么addIfAbsent在元素沒有變化的時候為什么沒有setArray操作？這個要看怎么理解addIfAbsent的語義了。如果說addIfAbsent語義是”寫“或者”不寫“操作，而把”不寫“操作當作一次”讀“操作的話，那么”讀“操作就不需要保持volatile語義了。
對于CopyOnWriteArraySet而言就簡單多了，只是持有一個CopyOnWriteArrayList，僅僅在add/addAll的時候檢測元素是否存在，如果存在就不加入集合中。
private final CopyOnWriteArrayList<E> al;
/**
* Creates an empty set.
*/
public CopyOnWriteArraySet() {
al = new CopyOnWriteArrayList<E>();
}
public boolean add(E e) {
return al.addIfAbsent(e);
}
在使用上CopyOnWriteArrayList/CopyOnWriteArraySet就簡單多了，和List/Set基本相同，這里就不再介紹了。
整個并發容器結束了，接下來好好規劃下線程池部分，然后進入最后一部分的梳理。
©2009-2014 IMXYLZ
|求賢若渴