周末上午的CopyOnWriteArrayList源码分析
周末上午的CopyOnWriteArrayList源码分析
码农王同学
发布于 2020-12-25 14:14:17
发布于 2020-12-25 14:14:17
一，CopyOnWriteArrayList源码分析
特点：写时复制，数据的最终一致性，读写分离。
二，方法分析
2.1，构造函数
//创建一个空的集合
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
//看下setArray操作,final关键字修饰
final void setArray(Object[] a) {
//对象引用赋值
array = a;
}
/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;
volatile关键字修饰，保证了数据的可见性
2.2，add（）方法
public boolean add(E e) {
//获取lock锁的实例对象
final ReentrantLock lock = this.lock;
//进行加锁操作
lock.lock();
try {
//获取数组对象引用，赋值给临时局部变量elements
Object[] elements = getArray();
//计算当前数组的元素大小len
int len = elements.length;
//将原有的数组元素拷贝到新数组空间
Object[] newElements = Arrays.copyOf(elements, len + 1);
//将元素e添加到新数组的末尾位置，此时体现了写时复制的特点
newElements[len] = e;
//将新数组对象的引用进行赋值,setArray操作刚刚已经解释过了，就是赋值操作
setArray(newElements);
return true;
} finally {
//进行解锁操作
lock.unlock();
}
}
2.3，get（）操作
public E get(int index) {
return get(getArray(), index);
}
//根据数组的索引下标获取指定位置的元素
private E get(Object[] a, int index) {
return (E) a[index];
}
/**
* Gets the array. Non-private so as to also be accessible
* from CopyOnWriteArraySet class.
*/
//其实，注释已经很好的说明了，为啥没有使用private关键字修饰的原因了
final Object[] getArray() {
return array;
}
2.4，size（）方法
public int size() {
//获取数组的长度
return getArray().length;
}
2.5，isEmpty（）方法
public boolean isEmpty() {
//判断集合元素个数是否等于0
return size() == 0;
}
2.6，indexOf（）方法
private static int indexOf(Object o, Object[] elements,
int index, int fence) {
//fence指的是数组的长度
//由于集合里面是可以装元素为null的情况的
//所以这里在查找元素时进行区分
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;
}
indexOf()查找元素的时间复杂度为O(n)，这里特意说明了一下。
2.7，lastIndexOf（）方法
private static int lastIndexOf(Object o, Object[] elements, int index) {
if (o == null) {
//时间复杂度为O(n)
for (int i = index; i >= 0; i--)
if (elements[i] == null)
return i;
} else {
for (int i = index; i >= 0; i--)
if (o.equals(elements[i]))
return i;
}
return -1;
}
从名字上就可以看出来，这个方法是从集合的末尾进行元素的查找，时间复杂度为O(n)
2.8，contains（）方法
public boolean contains(Object o) {
Object[] elements = getArray();
//方法的复用，利用扩展，根据indexOf()的返回值和0进行对比，来判断是否包含元素o
return indexOf(o, elements, 0, elements.length) >= 0;
}
此时的contains（）方法的时间复杂度为O(n)
2.9，remove（）方法
public E remove(int index) {
//获取锁示例对象lock
final ReentrantLock lock = this.lock;
//加锁操作，主要还是为了达到线程安全的目的
lock.lock();
try {
//获取数组的地址引用
Object[] elements = getArray();
//计算数组的长度
int len = elements.length;
//获取待移除位置的元素oldValue
E oldValue = get(elements, index);
//计算移动的大小
int numMoved = len - index - 1;
//如果numMoved==0说明index是最后一个元素位置
if (numMoved == 0)
setArray(Arrays.copyOf(elements, len - 1));
else {
//说明移除的是数组中间的某个位置的元素
//这个时候计算一下新数组空间的大小
//由于移除一个元素，所以新数组空间的大小为len-1
Object[] newElements = new Object[len - 1];
//下面的两个操作就是数组元素的拷贝操作
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
//将新数组空间引用赋值给成员变量array
setArray(newElements);
}
return oldValue;
} finally {
//进行解锁操作，说明此次操作已完成
lock.unlock();
}
}
2.10，containsAll（）方法
public boolean containsAll(Collection<?> c) {
Object[] elements = getArray();
int len = elements.length;
//对集合中的每一个元素e进行判断，若其中有一个不符合的，则直接返回false
for (Object e : c) {
if (indexOf(e, elements, 0, len) < 0)
return false;
}
return true;
}
此时的时间复杂度也是O(n)啦~
2.11，removeAll（）方法
public boolean removeAll(Collection<?> c) {
if (c == null) throw new NullPointerException();
//获取锁示例对象lock
final ReentrantLock lock = this.lock;
//加锁操作
lock.lock();
try {
//将数组地址引用赋值给临时局部变量elements
Object[] elements = getArray();
//计算数组的长度
int len = elements.length;
//如果数组长度不为0，则进行移除元素的操作
if (len != 0) {
//这个注释写的真的很好了，就是作为要存储的元素的（没有被移除的元素）
// temp array holds those elements we know we want to keep
int newlen = 0;
//临时数组空间的大小为len，主要是为了保持能装下len大小的元素，确保开辟的数组空间够大
Object[] temp = new Object[len];
for (int i = 0; i < len; ++i) {
//获取数组的每一个元素
Object element = elements[i];
//如果元素element不在集合c中，则表示不是待删除的元素
//此时就需要将其移动到temp数组中
if (!c.contains(element))
temp[newlen++] = element;
}
//如果新数组的长度不等于len，说明有元素已经被删除了
//此时需要将数组空间的地址引用重新赋值
if (newlen != len) {
setArray(Arrays.copyOf(temp, newlen));
return true;
}
}
return false;
} finally {
//进行解锁操作
lock.unlock();
}
}
如果集合c为null，则抛出空指针异常，由上层调用者自己控制集合是否为空。
2.12，retainAll（）方法
这个方法主要是用来求两个集合的交集的，那么我们一起看下其具体的实现吧
public boolean retainAll(Collection<?> c) {
if (c == null) throw new NullPointerException();
//获取锁实例对象进行加锁
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
if (len != 0) {
// temp array holds those elements we know we want to keep
int newlen = 0;
Object[] temp = new Object[len];
for (int i = 0; i < len; ++i) {
Object element = elements[i];
//和刚刚removeAll（）方法整体的实现思路是一致的,如果集合c包含element说明有共同元素
//将其放入到临时数组temp中
if (c.contains(element))
temp[newlen++] = element;
}
if (newlen != len) {
//数组元素的拷贝和数组空间引用的重新赋值
setArray(Arrays.copyOf(temp, newlen));
return true;
}
}
return false;
} finally {
//进行解锁操作
lock.unlock();
}
}
2.13，clear（）方法
public void clear() {
//获取锁实例对象
final ReentrantLock lock = this.lock;
lock.lock();
try {
//直接将数组的空间置为0
setArray(new Object[0]);
} finally {
lock.unlock();
}
}
2.14，addAll（）方法
public boolean addAll(Collection<? extends E> c) {
//看到过好多集合都是这个写法，先判断是否为某个class，不是则使用object进行接收
//object是所有对象的父类
Object[] cs = (c.getClass() == CopyOnWriteArrayList.class) ?
((CopyOnWriteArrayList<?>)c).getArray() : c.toArray();
//cs.length==0，表示集合为空，直接返回添加失败即可
if (cs.length == 0)
return false;
/获取锁实例对象
final ReentrantLock lock = this.lock;
//进行加锁操作
lock.lock();
try {
//获取数组元素的引用，赋值给临时局部变量
Object[] elements = getArray();
//计算数组的长度
int len = elements.length;
//len==0表示集合为空此时就可以将cs直接赋值给成员变量array了
if (len == 0 && cs.getClass() == Object[].class)
setArray(cs);
else {
//计算新数组空间的长度，表示能容纳元素个数的最小空间
Object[] newElements = Arrays.copyOf(elements, len + cs.length);
//进行数组元素的拷贝
System.arraycopy(cs, 0, newElements, len, cs.length);
//数组引用的重新赋值
setArray(newElements);
}
return true;
} finally {
//进行解锁操作
lock.unlock();
}
}
2.15，sort（）方法
public void sort(Comparator<? super E> c) {
//加锁的目的就是为了线程安全的
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
Object[] newElements = Arrays.copyOf(elements, elements.length);
@SuppressWarnings("unchecked") E[] es = (E[])newElements;
//直接进行排序操作，关于比较器的文章自己也很早分析过了
Arrays.sort(es, c);
setArray(newElements);
} finally {
//解锁操作
lock.unlock();
}
}
三，总结一下
关于本篇的源码分析，我们可以理解一下什么是读写复制，如何实现线程安全的方法，如何进行加减锁的操作以及如何编写可扩展，可复用的代码，如何清晰的给自己编写的代码加上可读性好的注释说明，这是一个比较重要的地方，自己在这里就分析和分享完了。
这里本打算分析CopyOnWriteArraySet源码分析的，经过分析了整体的实现方法，发现它就是复用了CopyOnWriteArrayList类的已有的方法，这里就不再分析了，因为，整篇CopyOnWriteArrayList的方法分析我们都基本上分析完了，再写这样的文章是不是就有点浪费了自己的时间呢?
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-12-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录