集合框架 List篇(2)—CopyOnWriteArrayList

  categories:资料  tags:  author:

来源:互联网

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




快乐成长 每天进步一点点      京ICP备18032580号-1