CopyOnWriteArrayList 的使用与源码分析

2021-10-04 03:23:03

CopyOnWriteArrayList 的使用

优点：

CopyOnWriteArrayList 是读写安全的 ArrayList，读操作不加锁，写操作加锁。
写操作时，会复制一份当前数组，然后去添加或移除元素，不会阻塞读操作，故适合读多写少的场景。

缺点：

CopyOnWriteArrayList 每次写操作都复制一份数组，如果数组内容过多或者写操作过于频繁，容易发生 GC。
CopyOnWriteArrayList 只能保证数据的最终一致性，不能满足实时一致性（读写不互斥）。

代码示例：

@Test
public void testCopyOnWriteArrayList() throws InterruptedException {
    List<Integer> list = IntStream.rangeClosed(1, 20).boxed().collect(Collectors.toList());
    CopyOnWriteArrayList cowList = new CopyOnWriteArrayList(list);

    new Thread(() -> {
        try {
            TimeUnit.SECONDS.sleep(2);
            System.out.println("添加的元素:" + (21));
            cowList.add(21);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }, "t1").start();

    new Thread(() -> {
        try {
            TimeUnit.SECONDS.sleep(1);
            System.out.println("添加的元素:" + (22));
            cowList.add(22);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }, "t2").start();

    for (int i = 0, size = cowList.size(); i < size; i++) {
        System.out.println("cowListSize:" + (size = cowList.size()));
        System.out.println("value:" + cowList.get(i));
        TimeUnit.MILLISECONDS.sleep(500);
    }

    TimeUnit.SECONDS.sleep(10);

    /**
         * 执行的结果：
         *
         * cowListSize:20
         * value:1
         * cowListSize:20
         * value:2
         * 添加的元素:22
         * cowListSize:21
         * value:3
         * cowListSize:21
         * value:4
         * 添加的元素:21
         * cowListSize:22
         * value:5
         * cowListSize:22
         * value:6
         * cowListSize:22
         * value:7
         * cowListSize:22
         * value:8
         * cowListSize:22
         * value:9
         * cowListSize:22
         * value:10
         * cowListSize:22
         * value:11
         * cowListSize:22
         * value:12
         * cowListSize:22
         * value:13
         * cowListSize:22
         * value:14
         * cowListSize:22
         * value:15
         * cowListSize:22
         * value:16
         * cowListSize:22
         * value:17
         * cowListSize:22
         * value:18
         * cowListSize:22
         * value:19
         * cowListSize:22
         * value:20
         * cowListSize:22
         * value:22
         * cowListSize:22
         * value:21
         */
}

源码分析

数据结构

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;

    /** The lock protecting all mutators */
    final transient ReentrantLock lock = new ReentrantLock();

    // 数组
    /** The array, accessed only via getArray/setArray. */
    private transient volatile Object[] array;

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

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

    // 默认构造器，初始化一个空的数组
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }

    public CopyOnWriteArrayList(Collection<? extends E> c) {
        Object[] elements;
        if (c.getClass() == CopyOnWriteArrayList.class)
            elements = ((CopyOnWriteArrayList<?>)c).getArray();
        else {
            elements = c.toArray();
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elements.getClass() != Object[].class)
                elements = Arrays.copyOf(elements, elements.length, Object[].class);
        }
        setArray(elements);
    } 
}

size

public int size() {
    // 默认是空数组，不为 null
    return getArray().length;
}

isEmpty

public boolean isEmpty() {
    return size() == 0;
}

eq

private static boolean eq(Object o1, Object o2) {
    return (o1 == null) ? o2 == null : o1.equals(o2);
}

indexOf

private static int indexOf(Object o, Object[] elements, int index, int fence) {
    // 如果 o 是 null，则在数组 [index, fence) 区间中找出第一个为 null 的元素的位置
    if (o == null) {
        for (int i = index; i < fence; i++)
            if (elements[i] == null)
                return i;
    } else {
        // o 不为 null，则遍历找出 o 在数组中的位置
        for (int i = index; i < fence; i++)
            if (o.equals(elements[i]))
                return i;
    }
    // 元素 o 在数组中不存在，返回 -1
    return -1;
}

lastIndexOf

// 从 index 位置开始向前找等于 o 的元素位置
private static int lastIndexOf(Object o, Object[] elements, int index) {
    if (o == null) {
        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;
}

contains

public boolean contains(Object o) {
    Object[] elements = getArray();
    return indexOf(o, elements, 0, elements.length) >= 0;
}

indexOf

public int indexOf(Object o) {
    Object[] elements = getArray();
    return indexOf(o, elements, 0, elements.length);
}

indexOf

public int indexOf(E e, int index) {
    Object[] elements = getArray();
    return indexOf(e, elements, index, elements.length);
}

lastIndexOf

public int lastIndexOf(Object o) {
    Object[] elements = getArray();
    return lastIndexOf(o, elements, elements.length - 1);
}

clone

public Object clone() {
    try {
        @SuppressWarnings("unchecked")
        CopyOnWriteArrayList<E> clone =
            (CopyOnWriteArrayList<E>) super.clone();
        clone.resetLock();
        return clone;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError();
    }
}

toArray

public Object[] toArray() {
    Object[] elements = getArray();
    return Arrays.copyOf(elements, elements.length);
}

get

private E get(Object[] a, int index) {
    return (E) a[index];
}

get

public E get(int index) {
    return get(getArray(), index);
}

set

// 修改数组元素值，加锁，每次只有一个线程复制数组修改元素的值
public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        E oldValue = get(elements, index);

        if (oldValue != element) {
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len);
            newElements[index] = element;
            setArray(newElements);
        } else {
            // 保证 volatile 写语义
            // Not quite a no-op; ensures volatile write semantics
            setArray(elements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }

    /**
        JDK 11 中，源码变化如下：

        public E set(int index, E element) {
            synchronized (lock) {
                Object[] es = getArray();
                E oldValue = elementAt(es, index);

                if (oldValue != element) {
                    es = es.clone();
                    es[index] = element;
                }
                // Ensure volatile write semantics even when oldvalue == element
                setArray(es);
                return oldValue;
            }
        }
        */
}

add

// 添加元素
// 先复制一个数组（Arrays.copyOf）
// 再添加元素
// 覆盖旧数组（setArray）
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;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }

    /**
        JDK 11 中，源码变化如下：

        public boolean add(E e) {
            synchronized (lock) {
                Object[] es = getArray();
                int len = es.length;
                es = Arrays.copyOf(es, len + 1);
                es[len] = e;
                setArray(es);
                return true;
            }
        }
        */
}

add

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);
            System.arraycopy(elements, index, newElements, index + 1,
                             numMoved);
        }
        newElements[index] = element;
        setArray(newElements);
    } finally {
        lock.unlock();
    }
}

remove

// 移除元素
// 将原数组移除指定元素，再复制一个新的数组（Arrays.copyOf）
// 覆盖旧数组（setArray）
public E remove(int index) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        E oldValue = get(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 oldValue;
    } finally {
        lock.unlock();
    }
}

iterator

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
}

// 迭代器类
static final class COWIterator<E> implements ListIterator<E> {
    // 数组
    private final Object[] snapshot;
    // 当前遍历的数组下标
    private int cursor;

    private COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }

    // 是否还有元素可迭代
    public boolean hasNext() {
        // 如果当前遍历的数组下标小于数组长度，则表示还可以继续迭代
        return cursor < snapshot.length;
    }

    // 当前遍历的数组下标 cursor 前是否已经遍历过元素
    public boolean hasPrevious() {
        return cursor > 0;
    }

    // 获取当前数组下标 cursor 上的元素
    @SuppressWarnings("unchecked")
    public E next() {
        if (! hasNext())
            throw new NoSuchElementException();
        return (E) snapshot[cursor++];
    }

    @SuppressWarnings("unchecked")
    public E previous() {
        if (! hasPrevious())
            throw new NoSuchElementException();
        return (E) snapshot[--cursor];
    }

    public int nextIndex() {
        return cursor;
    }

    public int previousIndex() {
        return cursor-1;
    }

    /**
         * Not supported. Always throws UnsupportedOperationException.
         * @throws UnsupportedOperationException always; {@code remove}
         *         is not supported by this iterator.
         */
    public void remove() {
        throw new UnsupportedOperationException();
    }

    /**
         * Not supported. Always throws UnsupportedOperationException.
         * @throws UnsupportedOperationException always; {@code set}
         *         is not supported by this iterator.
         */
    public void set(E e) {
        throw new UnsupportedOperationException();
    }

    /**
         * Not supported. Always throws UnsupportedOperationException.
         * @throws UnsupportedOperationException always; {@code add}
         *         is not supported by this iterator.
         */
    public void add(E e) {
        throw new UnsupportedOperationException();
    }

    @Override
    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        Object[] elements = snapshot;
        final int size = elements.length;
        for (int i = cursor; i < size; i++) {
            @SuppressWarnings("unchecked") E e = (E) elements[i];
            action.accept(e);
        }
        cursor = size;
    }
}

码农公寓

CopyOnWriteArrayList 的使用

源码分析

数据结构

size

isEmpty

eq

indexOf

lastIndexOf

contains

indexOf

indexOf

lastIndexOf

clone

toArray

get

get

set

add

add

remove

iterator

相关文章