CopyOnWriteArrayList与CopyOnWriteArraySet

2019-01-30 22:10:36

一. CopyOnWriteArrayList

CopyOnWriteArrayList实现了List接口,可以认为是ArrayList的一个线程安全的版本。在多个线程读的时候没有限制,就算一个线程在写的时候也可以读,因为对容器的修改操作是将底层数组复制一份,然后对复制出来的新数组进行修改,然后将数组引用指向新数组,这些操作都是加锁同步的,所以不能多个线程同时写。由此可见,CopyOnWriteArrayList适合读多写少的场景,而且虽然是线程安全的,但是只能保证最终的数据一致性,不能保证数据的实时一致性。

  1. get操作,可以看到,读操作没有加任何限制,成员变量被volatile修饰,确保每次调用getArray()时获取到的数组都是最新的。

    1. private transient volatile Object[] array;
    2. public E get(int index) {
    3. return elementAt(getArray(), index);
    4. }
    5. final Object[] getArray() {
    6. return array;
    7. }
    8. static <E> E elementAt(Object[] a, int index) {
    9. return (E) a[index];
    10. }
  2. add操作被加锁了,所以不能有多个线程同时修改,上锁后,将原来的数组复制到一个新的数组,而且长度加1,然后将插入元素放到新数组中,再将新数组赋给成员变量array,其他的修改操作也是类似的。

    1. final transient Object lock = new Object();
    2. public boolean add(E e) {
    3. synchronized (lock) {
    4. Object[] es = getArray();
    5. int len = es.length;
    6. es = Arrays.copyOf(es, len + 1);
    7. es[len] = e;
    8. setArray(es);
    9. return true;
    10. }
    11. }
    12. final void setArray(Object[] a) {
    13. array = a;
    14. }
  3. 迭代器,和ArrayList的迭代器差不多,但是这里为了防止多个线程并发修改,将迭代器的所有写操作都设为不支持的操作。迭代器对象内部保留了一份指向底层数组的引用,所以在一个迭代器对象的生命周期中,使用的都是同一份数组,其内部数据不会被修改。

    1. public Iterator<E> iterator() {
    2. return new COWIterator<E>(getArray(), 0);
    3. }
    4. static final class COWIterator<E> implements ListIterator<E> {
    5. /** Snapshot of the array */
    6. private final Object[] snapshot;
    7. /** Index of element to be returned by subsequent call to next. */
    8. private int cursor;
    9. COWIterator(Object[] es, int initialCursor) {
    10. cursor = initialCursor;
    11. snapshot = es;
    12. }
    13. public boolean hasNext() {
    14. return cursor < snapshot.length;
    15. }
    16. public boolean hasPrevious() {
    17. return cursor > 0;
    18. }
    19. @SuppressWarnings("unchecked")
    20. public E next() {
    21. if (! hasNext())
    22. throw new NoSuchElementException();
    23. return (E) snapshot[cursor++];
    24. }
    25. @SuppressWarnings("unchecked")
    26. public E previous() {
    27. if (! hasPrevious())
    28. throw new NoSuchElementException();
    29. return (E) snapshot[--cursor];
    30. }
    31. public int nextIndex() {
    32. return cursor;
    33. }
    34. public int previousIndex() {
    35. return cursor - 1;
    36. }
    37. public void remove() {
    38. throw new UnsupportedOperationException();
    39. }
    40. public void set(E e) {
    41. throw new UnsupportedOperationException();
    42. }
    43. public void add(E e) {
    44. throw new UnsupportedOperationException();
    45. }
    46. ...
    47. }
  4. subList返回一个子列表视图,由于这个视图是要能够正确反映出原列表中的数据,所以,无论是在创建这个视图的过程,还是视图对象的所有读写操作,都要加锁,防止在上述操作过程中有其他线程修改列表底层数组。视图对象创建时,保留了一个当前底层数组对象的引用,之后无论时视图对象的读还是写操作,除了要加锁,还要检查保留的引用和真正的底层数组引用是不是一个,如果不一致,说明已被修改,则视图对象应失效,抛出并发修改异常,这一点和ArrayList的设计是差不多的,只不过ArrayList使用modCount来判断是否并发修改,这里直接使用数组引用判断。

    1. public List<E> subList(int fromIndex, int toIndex) {
    2. synchronized (lock) {
    3. Object[] es = getArray();
    4. int len = es.length;
    5. int size = toIndex - fromIndex;
    6. if (fromIndex < 0 || toIndex > len || size < 0)
    7. throw new IndexOutOfBoundsException();
    8. return new COWSubList(es, fromIndex, size);
    9. }
    10. }
    11. private class COWSubList implements List<E>, RandomAccess {
    12. private final int offset;
    13. private int size;
    14. private Object[] expectedArray;
    15. COWSubList(Object[] es, int offset, int size) {
    16. // assert Thread.holdsLock(lock);
    17. expectedArray = es;
    18. this.offset = offset;
    19. this.size = size;
    20. }
    21. private void checkForComodification() {
    22. // assert Thread.holdsLock(lock);
    23. if (getArray() != expectedArray)
    24. throw new ConcurrentModificationException();
    25. }
    26. ...
    27. }

    二. CopyOnWriteArraySet

CopyOnWriteArraySet在内部使用一个CopyOnWriteArrayList对象来存放数据,所以对大部分方法的调用都会转为对list对象方法的调用。在存放数据时,先遍历一下数组,如果数据不存在就插入,存在就不插入,从而达到set数据不重复的目的,这种方式在数据量大的时候效率并不是很高,但是不要忘记,CopyOnWrite容器是用于读远多于写的情况。
add方法:

  1. private final CopyOnWriteArrayList<E> al;
  2. public boolean add(E e) {
  3. return al.addIfAbsent(e);
  4. }

下面是CopyOnWriteArrayList的源码

  1. // 如果没有e则添加
  2. public boolean addIfAbsent(E e) {
  3. Object[] snapshot = getArray();
  4. return indexOfRange(e, snapshot, 0, snapshot.length) < 0
  5. && addIfAbsent(e, snapshot);
  6. }
  7. // snapshot已经是确定不包含e的快照版本
  8. private boolean addIfAbsent(E e, Object[] snapshot) {
  9. synchronized (lock) {
  10. Object[] current = getArray();
  11. int len = current.length;
  12. // 在获得锁之前,有其他线程进行了修改
  13. if (snapshot != current) {
  14. // 取两个版本长度的最小值
  15. int common = Math.min(snapshot.length, len);
  16. for (int i = 0; i < common; i++)
  17. // 因为snapshot中已经确定不含e了
  18. // 所以只有current[i] != snapshot[i]时current[i]才可能等于e
  19. if (current[i] != snapshot[i]
  20. && Objects.equals(e, current[i]))
  21. return false;
  22. // 新版本数组的[0, common)部分不包含e,检查剩余部分
  23. if (indexOfRange(e, current, common, len) >= 0)
  24. return false;
  25. }
  26. // 新版本也不包含e,创建新数组,添加e到数组末尾
  27. Object[] newElements = Arrays.copyOf(current, len + 1);
  28. newElements[len] = e;
  29. setArray(newElements);
  30. return true;
  31. }
  32. }

0
2
0

添加评论

正在回复:
取消
0
0
2
0