集合框架 List篇（2）—CopyOnWriteArrayList

资料

来源：互联网

List
-----------
1.ArrayList（jdk1.5以前版本中Vector）
2.LinkedList（jdk1.5以前版本中Stack）
3.CopyOnWriteArrayList

----------------------------------------CopyOnWriteArrayList----------------------------------------

CopyOnWriteArrayList 用在“读多，改少”的“并发”应用中。

不存在“扩容”的概念，每次写操作（add or remove）都要copy一个副本，在副本的基础上修改后改变array引用---所以称为“CopyOnWrite”，因此在写操作是加锁，并且对整个list的copy操作时相当耗时的，过多的写操作不推荐使用该存储结构。

CopyOnWriteArrayList的类层次结构

public class CopyOnWriteArrayList <E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

CopyOnWriteArrayList的全局变量

transient final ReentrantLock lock = new ReentrantLock();//全局锁

private volatile transient Object[] array;//volatile（修改可见）类型的数组array

//内部的实现中仅通过array的get和set方法对其进行操作

final Object[] getArray() {
return array;
}

final void setArray(Object[] a) {
array = a;
}

CopyOnWriteArrayList的构造方法

/**
* 创建一个空的list，默认容量为0，这个和ArraList中的默认10不同，主要是因为在对CopyOnWriteArrayList的修改操作时都是先copy

*一个数组（容量+1或容量-1），处理后再把引用赋给array的，不存在扩容的情况，所以当初始化时就没必要指定长度了。

*/
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}

//通过已有集合构建CopyOnWriteArrayList

public CopyOnWriteArrayList(Collection<? extends E> c) {
Object[] elements = c.toArray();
if (elements.getClass() != Object[].class)
elements = Arrays.copyOf(elements, elements.length, Object[].class);//copy一个数组
setArray(elements);//把array引用指向新的数组
}

//通过给定的数组创建List

public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

CopyOnWriteArrayList的get方法

//get操作 ，不加锁

public E get(int index) {
//直接定位到数组的index下标处，没有加锁操作

//（array是volatile类型的，volatile的 happen-before原则就是所有的“写操作”都在“读操作”前发生，保证了数据的一致性）

return (E)(getArray()[index]);

}

CopyOnWriteArrayList的set方法

//set 修改元素操作，加锁

public E set(int index, E element) {//在指定的位置index处设置element
final ReentrantLock lock = this.lock;
lock.lock();//加锁
try {
Object[] elements = getArray();
Object oldValue = elements[index];//获得数组中index坐标下的值

if (oldValue != element) {//如果传入的element和目前坐标index处的值不同
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len);//copy一个数组副本
newElements[index] = element;//并把指定index处的值进行替换
setArray(newElements);//array引用指向新的数组
} else {
// Not quite a no-op; ensures volatile write semantics
setArray(elements);//保证volatile的happen-before原则
}
return (E)oldValue;
} finally {
lock.unlock();//解锁
}
}

CopyOnWriteArrayList的add方法

//add 添加元素操作 ，加锁

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;//在新数组的最后一个位置加入e元素
setArray(newElements);
return true;
} finally {
lock.unlock();//解锁
}
}

//在指定的index处加入元素element，加锁

public void add(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();// 加锁
try {
Object[] elements = getArray();
int len = elements.length;
if (index > len || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+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);//index前的元素
System.arraycopy(elements, index, newElements, index + 1, numMoved);//index后的元素
}
newElements[index] = element;
setArray(newElements);
} finally {
lock.unlock();//解锁
}
}

CopyOnWriteArrayList的remove方法

//remove 删除操作，加锁

public E remove(int index) {
final ReentrantLock lock = this.lock;
lock.lock();//加锁
try {
Object[] elements = getArray();
int len = elements.length;
Object oldValue = 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 (E)oldValue;
} finally {
lock.unlock();//解锁
}
}

//remove参数是元素对象，需要遍历比较，加锁

public boolean remove(Object o) {
final ReentrantLock lock = this.lock;
lock.lock();//加锁
try {
Object[] elements = getArray();
int len = elements.length;
if (len != 0) {
// Copy while searching for element to remove
// This wins in the normal case of element being present
int newlen = len - 1;
Object[] newElements = new Object[newlen];//创建一个length-1的数组

for (int i = 0; i < newlen; ++i) {
if (eq(o, elements[i])) {
// 如果找到了该元素，就把其后继拷贝到新数组中

for (int k = i + 1; k < len; ++k)
newElements[k-1] = elements[k];
setArray(newElements);
return true;
} else

//把其前面的节点一一设置到新数组中去
newElements[i] = elements[i];
}

// 特殊的判断：和最和一个元素比较（如果刚好是最后一个，就大大减少比较）

if (eq(o, elements[newlen])) {
setArray(newElements);
return true;
}
}
return false;
} finally {
lock.unlock();//解锁
}

}

 

http://hi.baidu.com/yao1111yao/item/5c2f7f0984f3bb36a2332a6d

发表评论