死磕 java集合之CopyOnWriteArrayList源码分析

原创
2020/02/07 10:32
阅读数 231

🖕点击上方蓝字“彤哥读源码关注,与彤哥一起畅游源码的海洋。

简介

CopyOnWriteArrayList是ArrayList的线程安全版本,内部也是通过数组实现,每次对数组的修改都完全拷贝一份新的数组来修改,修改完了再替换掉老数组,这样保证了只阻塞写操作,不阻塞读操作,实现读写分离。

继承体系

CopyOnWriteArrayList实现了List, RandomAccess, Cloneable, java.io.Serializable等接口。

CopyOnWriteArrayList实现了List,提供了基础的添加、删除、遍历等操作。

CopyOnWriteArrayList实现了RandomAccess,提供了随机访问的能力。

CopyOnWriteArrayList实现了Cloneable,可以被克隆。

CopyOnWriteArrayList实现了Serializable,可以被序列化。

源码解析

属性

  
  
  
  1. /** 用于修改时加锁 */

  2. final transient ReentrantLock lock = new ReentrantLock();


  3. /** 真正存储元素的地方,只能通过getArray()/setArray()访问 */

  4. private transient volatile Object[] array;

(1)lock

用于修改时加锁,使用transient修饰表示不自动序列化。

(2)array

真正存储元素的地方,使用transient修饰表示不自动序列化,使用volatile修饰表示一个线程对这个字段的修改另外一个线程立即可见。

问题:为啥没有size字段?且听后续分解。

CopyOnWriteArrayList()构造方法

创建空数组。

  
  
  
  1. public CopyOnWriteArrayList() {

  2. // 所有对array的操作都是通过setArray()和getArray()进行

  3. setArray(new Object[0]);

  4. }


  5. final void setArray(Object[] a) {

  6. array = a;

  7. }

CopyOnWriteArrayList(Collection c)构造方法

如果c是CopyOnWriteArrayList类型,直接把它的数组赋值给当前list的数组,注意这里是浅拷贝,两个集合共用同一个数组。

如果c不是CopyOnWriteArrayList类型,则进行拷贝把c的元素全部拷贝到当前list的数组中。

  
  
  
  1. public CopyOnWriteArrayList(Collection<? extends E> c) {

  2. Object[] elements;

  3. if (c.getClass() == CopyOnWriteArrayList.class)

  4. // 如果c也是CopyOnWriteArrayList类型

  5. // 那么直接把它的数组拿过来使用

  6. elements = ((CopyOnWriteArrayList<?>)c).getArray();

  7. else {

  8. // 否则调用其toArray()方法将集合元素转化为数组

  9. elements = c.toArray();

  10. // 这里c.toArray()返回的不一定是Object[]类型

  11. // 详细原因见ArrayList里面的分析

  12. if (elements.getClass() != Object[].class)

  13. elements = Arrays.copyOf(elements, elements.length, Object[].class);

  14. }

  15. setArray(elements);

  16. }

CopyOnWriteArrayList(E[] toCopyIn)构造方法

把toCopyIn的元素拷贝给当前list的数组。

  
  
  
  1. public CopyOnWriteArrayList(E[] toCopyIn) {

  2. setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));

  3. }

add(E e)方法

添加一个元素到末尾。

  
  
  
  1. public boolean add(E e) {

  2. final ReentrantLock lock = this.lock;

  3. // 加锁

  4. lock.lock();

  5. try {

  6. // 获取旧数组

  7. Object[] elements = getArray();

  8. int len = elements.length;

  9. // 将旧数组元素拷贝到新数组中

  10. // 新数组大小是旧数组大小加1

  11. Object[] newElements = Arrays.copyOf(elements, len + 1);

  12. // 将元素放在最后一位

  13. newElements[len] = e;

  14. setArray(newElements);

  15. return true;

  16. } finally {

  17. // 释放锁

  18. lock.unlock();

  19. }

  20. }

(1)加锁;

(2)获取元素数组;

(3)新建一个数组,大小为原数组长度加1,并把原数组元素拷贝到新数组;

(4)把新添加的元素放到新数组的末尾;

(5)把新数组赋值给当前对象的array属性,覆盖原数组;

(6)解锁;

add(int index, E element)方法

添加一个元素在指定索引处。

  
  
  
  1. public void add(int index, E element) {

  2. final ReentrantLock lock = this.lock;

  3. // 加锁

  4. lock.lock();

  5. try {

  6. // 获取旧数组

  7. Object[] elements = getArray();

  8. int len = elements.length;

  9. // 检查是否越界, 可以等于len

  10. if (index > len || index < 0)

  11. throw new IndexOutOfBoundsException("Index: "+index+

  12. ", Size: "+len);

  13. Object[] newElements;

  14. int numMoved = len - index;

  15. if (numMoved == 0)

  16. // 如果插入的位置是最后一位

  17. // 那么拷贝一个n+1的数组, 其前n个元素与旧数组一致

  18. newElements = Arrays.copyOf(elements, len + 1);

  19. else {

  20. // 如果插入的位置不是最后一位

  21. // 那么新建一个n+1的数组

  22. newElements = new Object[len + 1];

  23. // 拷贝旧数组前index的元素到新数组中

  24. System.arraycopy(elements, 0, newElements, 0, index);

  25. // 将index及其之后的元素往后挪一位拷贝到新数组中

  26. // 这样正好index位置是空出来的

  27. System.arraycopy(elements, index, newElements, index + 1,

  28. numMoved);

  29. }

  30. // 将元素放置在index处

  31. newElements[index] = element;

  32. setArray(newElements);

  33. } finally {

  34. // 释放锁

  35. lock.unlock();

  36. }

  37. }

(1)加锁;

(2)检查索引是否合法,如果不合法抛出IndexOutOfBoundsException异常,注意这里index等于len也是合法的;

(3)如果索引等于数组长度(也就是数组最后一位再加1),那就拷贝一个len+1的数组;

(4)如果索引不等于数组长度,那就新建一个len+1的数组,并按索引位置分成两部分,索引之前(不包含)的部分拷贝到新数组索引之前(不包含)的部分,索引之后(包含)的位置拷贝到新数组索引之后(不包含)的位置,索引所在位置留空;

(5)把索引位置赋值为待添加的元素;

(6)把新数组赋值给当前对象的array属性,覆盖原数组;

(7)解锁;

addIfAbsent(E e)方法

添加一个元素如果这个元素不存在于集合中。

  
  
  
  1. public boolean addIfAbsent(E e) {

  2. // 获取元素数组, 取名为快照

  3. Object[] snapshot = getArray();

  4. // 检查如果元素不存在,直接返回false

  5. // 如果存在再调用addIfAbsent()方法添加元素

  6. return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :

  7. addIfAbsent(e, snapshot);

  8. }


  9. private boolean addIfAbsent(E e, Object[] snapshot) {

  10. final ReentrantLock lock = this.lock;

  11. // 加锁

  12. lock.lock();

  13. try {

  14. // 重新获取旧数组

  15. Object[] current = getArray();

  16. int len = current.length;

  17. // 如果快照与刚获取的数组不一致

  18. // 说明有修改

  19. if (snapshot != current) {

  20. // 重新检查元素是否在刚获取的数组里

  21. int common = Math.min(snapshot.length, len);

  22. for (int i = 0; i < common; i++)

  23. // 到这个方法里面了, 说明元素不在快照里面

  24. if (current[i] != snapshot[i] && eq(e, current[i]))

  25. return false;

  26. if (indexOf(e, current, common, len) >= 0)

  27. return false;

  28. }

  29. // 拷贝一份n+1的数组

  30. Object[] newElements = Arrays.copyOf(current, len + 1);

  31. // 将元素放在最后一位

  32. newElements[len] = e;

  33. setArray(newElements);

  34. return true;

  35. } finally {

  36. // 释放锁

  37. lock.unlock();

  38. }

  39. }

(1)检查这个元素是否存在于数组快照中;

(2)如果存在直接返回false,如果不存在调用addIfAbsent(E e, Object[] snapshot)处理;

(3)加锁;

(4)如果当前数组不等于传入的快照,说明有修改,检查待添加的元素是否存在于当前数组中,如果存在直接返回false;

(5)拷贝一个新数组,长度等于原数组长度加1,并把原数组元素拷贝到新数组中;

(6)把新元素添加到数组最后一位;

(7)把新数组赋值给当前对象的array属性,覆盖原数组;

(8)解锁;

get(int index)

获取指定索引的元素,支持随机访问,时间复杂度为O(1)。

  
  
  
  1. public E get(int index) {

  2. // 获取元素不需要加锁

  3. // 直接返回index位置的元素

  4. // 这里是没有做越界检查的, 因为数组本身会做越界检查

  5. return get(getArray(), index);

  6. }


  7. final Object[] getArray() {

  8. return array;

  9. }


  10. private E get(Object[] a, int index) {

  11. return (E) a[index];

  12. }

(1)获取元素数组;

(2)返回数组指定索引位置的元素;

remove(int index)方法

删除指定索引位置的元素。

  
  
  
  1. public E remove(int index) {

  2. final ReentrantLock lock = this.lock;

  3. // 加锁

  4. lock.lock();

  5. try {

  6. // 获取旧数组

  7. Object[] elements = getArray();

  8. int len = elements.length;

  9. E oldValue = get(elements, index);

  10. int numMoved = len - index - 1;

  11. if (numMoved == 0)

  12. // 如果移除的是最后一位

  13. // 那么直接拷贝一份n-1的新数组, 最后一位就自动删除了

  14. setArray(Arrays.copyOf(elements, len - 1));

  15. else {

  16. // 如果移除的不是最后一位

  17. // 那么新建一个n-1的新数组

  18. Object[] newElements = new Object[len - 1];

  19. // 将前index的元素拷贝到新数组中

  20. System.arraycopy(elements, 0, newElements, 0, index);

  21. // 将index后面(不包含)的元素往前挪一位

  22. // 这样正好把index位置覆盖掉了, 相当于删除了

  23. System.arraycopy(elements, index + 1, newElements, index,

  24. numMoved);

  25. setArray(newElements);

  26. }

  27. return oldValue;

  28. } finally {

  29. // 释放锁

  30. lock.unlock();

  31. }

  32. }

(1)加锁;

(2)获取指定索引位置元素的旧值;

(3)如果移除的是最后一位元素,则把原数组的前len-1个元素拷贝到新数组中,并把新数组赋值给当前对象的数组属性;

(4)如果移除的不是最后一位元素,则新建一个len-1长度的数组,并把原数组除了指定索引位置的元素全部拷贝到新数组中,并把新数组赋值给当前对象的数组属性;

(5)解锁并返回旧值;

size()方法

返回数组的长度。

  
  
  
  1. public int size() {

  2. // 获取元素个数不需要加锁

  3. // 直接返回数组的长度

  4. return getArray().length;

  5. }

总结

(1)CopyOnWriteArrayList使用ReentrantLock重入锁加锁,保证线程安全;

(2)CopyOnWriteArrayList的写操作都要先拷贝一份新数组,在新数组中做修改,修改完了再用新数组替换老数组,所以空间复杂度是O(n),性能比较低下;

(3)CopyOnWriteArrayList的读操作支持随机访问,时间复杂度为O(1);

(4)CopyOnWriteArrayList采用读写分离的思想,读操作不加锁,写操作加锁,且写操作占用较大内存空间,所以适用于读多写少的场合;

(5)CopyOnWriteArrayList只保证最终一致性,不保证实时一致性;

彩蛋

为什么CopyOnWriteArrayList没有size属性?

因为每次修改都是拷贝一份正好可以存储目标个数元素的数组,所以不需要size属性了,数组的长度就是集合的大小,而不像ArrayList数组的长度实际是要大于集合的大小的。

比如,add(E e)操作,先拷贝一份n+1个元素的数组,再把新元素放到新数组的最后一位,这时新数组的长度为len+1了,也就是集合的size了。



欢迎关注我的公众号“彤哥读源码”,与彤哥一起畅游源码的海洋。

喜欢这篇文章

就点下在看哦

本文分享自微信公众号 - 彤哥读源码(gh_63d1b83b9e01)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部