Java CopyOnWriteArrayList

Copy-On-Write简称COW，是一种用于程序设计中的优化策略。其基本思路是，从一开始大家都在共享同一个内容，当某个人想要修改这个内容的时候，才会真正把内容Copy出去形成一个新的内容然后再改，这是一种延时懒惰策略。

从JDK1.5开始Java并发包里提供了两个使用CopyOnWrite机制实现的并发容器,它们是CopyOnWriteArrayList和CopyOnWriteArraySet。CopyOnWrite容器非常有用，可以在非常多的并发场景中使用到。

什么是CopyOnWrite容器

CopyOnWrite容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。

这样做的好处是我们可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。

所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。

源码：

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;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

 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();
        }
    }

View Code

    public boolean addAll(int index, Collection<? extends E> c) {
        Object[] cs = c.toArray();
        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);
            if (cs.length == 0)
                return false;
            int numMoved = len - index;
            Object[] newElements;
            if (numMoved == 0)
                newElements = Arrays.copyOf(elements, len + cs.length);
            else {
                newElements = new Object[len + cs.length];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index,
                                 newElements, index + cs.length,
                                 numMoved);
            }
            System.arraycopy(cs, 0, newElements, index, cs.length);
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

View Code

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 {
                // Not quite a no-op; ensures volatile write semantics
                setArray(elements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }

remove:

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();
        }
    }

 public boolean remove(Object o) {
        Object[] snapshot = getArray();
        int index = indexOf(o, snapshot, 0, snapshot.length);
        return (index < 0) ? false : remove(o, snapshot, index);
    }

View Code

  private boolean remove(Object o, Object[] snapshot, int index) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] current = getArray();
            int len = current.length;
            if (snapshot != current) findIndex: {
                int prefix = Math.min(index, len);
                for (int i = 0; i < prefix; i++) {
                    if (current[i] != snapshot[i] && eq(o, current[i])) {
                        index = i;
                        break findIndex;
                    }
                }
                if (index >= len)
                    return false;
                if (current[index] == o)
                    break findIndex;
                index = indexOf(o, current, index, len);
                if (index < 0)
                    return false;
            }
            Object[] newElements = new Object[len - 1];
            System.arraycopy(current, 0, newElements, 0, index);
            System.arraycopy(current, index + 1,
                             newElements, index,
                             len - index - 1);
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

View Code

 void removeRange(int fromIndex, int toIndex) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;

            if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
                throw new IndexOutOfBoundsException();
            int newlen = len - (toIndex - fromIndex);
            int numMoved = len - toIndex;
            if (numMoved == 0)
                setArray(Arrays.copyOf(elements, newlen));
            else {
                Object[] newElements = new Object[newlen];
                System.arraycopy(elements, 0, newElements, 0, fromIndex);
                System.arraycopy(elements, toIndex, newElements,
                                 fromIndex, numMoved);
                setArray(newElements);
            }
        } finally {
            lock.unlock();
        }
    }

View Code

===============================================================================

多线程对集合进行操作：

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class Main {
    public static void main(String[] args) {
        new CopyOnWriteArrayListDemo().run();
    }
}
class CopyOnWriteArrayListDemo {
    /**
     * 读线程
     *
     * @author wangjie
     */
    private static class ReadTask implements Runnable {
        List<String> list;

        public ReadTask(List<String> list) {
            this.list = list;
        }

        public void run() {
            for (String str : list) {
                System.out.println(str);
            }
        }
    }

    /**
     * 写线程
     *
     * @author wangjie
     */
    private static class WriteTask implements Runnable {
        List<String> list;
        int index;

        public WriteTask(List<String> list, int index) {
            this.list = list;
            this.index = index;
        }

        public void run() {
            list.remove(index);
            list.add(index, "write_" + index);
        }
    }

    public void run() {
        final int NUM = 5;
        List<String> list = new ArrayList<String>();
        //List<String> list=new CopyOnWriteArrayList<String>();
        for (int i = 0; i < NUM; i++) {
            list.add("main_" + i);
        }
        ExecutorService executorService = Executors.newFixedThreadPool(NUM);
        for (int i = 0; i < NUM; i++) {
            executorService.execute(new ReadTask(list));
            executorService.execute(new WriteTask(list, i));
        }
        executorService.shutdown();
    }
}

main_0
Exception in thread "pool-1-thread-2" Exception in thread "pool-1-thread-1" Exception in thread "pool-1-thread-5" Exception in thread "pool-1-thread-3" java.util.ConcurrentModificationException
main_1
write_0
main_1
write_0
write_0
write_0
write_1
write_2
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
write_3
    at java.util.ArrayList$Itr.next(ArrayList.java:851)
main_4
    at com.qhong.CopyOnWriteArrayListDemo$ReadTask.run(Main.java:28)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
    at java.lang.Thread.run(Thread.java:745)
java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
    at java.util.ArrayList$Itr.next(ArrayList.java:851)
    at com.qhong.CopyOnWriteArrayListDemo$ReadTask.run(Main.java:28)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
    at java.lang.Thread.run(Thread.java:745)
java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
    at java.util.ArrayList$Itr.next(ArrayList.java:851)
    at com.qhong.CopyOnWriteArrayListDemo$ReadTask.run(Main.java:28)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
    at java.lang.Thread.run(Thread.java:745)
java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
    at java.util.ArrayList$Itr.next(ArrayList.java:851)
    at com.qhong.CopyOnWriteArrayListDemo$ReadTask.run(Main.java:28)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
    at java.lang.Thread.run(Thread.java:745)

把注释的取消，换成CopyOnWriteArrayList

main_0
main_1
main_2
main_3
main_4
main_0
write_1
write_2
main_3
main_4
write_0
write_1
write_2
write_3
write_0
write_1
write_2
main_4
write_4
write_0
write_1
write_2
write_3
write_4

View Code

=============================================================================================

Array一边遍历，一边删除

foreach:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        String[] strArray={"111","222","333","444"};
        //System.out.println(Arrays.toString(strArray));
        List<String> list=new ArrayList<String>();
        list.addAll(Arrays.asList(strArray));
        System.out.println(list);
        for(String str:list){
            System.out.println(str);
            list.remove(str);
            System.out.println("移除后："+list);
        }
    }
}

[111, 222, 333, 444]
Exception in thread "main" java.util.ConcurrentModificationException
111
移除后：[222, 333, 444]
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
    at java.util.ArrayList$Itr.next(ArrayList.java:851)
    at com.qhong.Main.main(Main.java:15)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:498)
    at com.intellij.rt.execution.application.AppMain.main(AppMain.java:144)

发现报错

for:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        String[] strArray={"111","222","333","444"};
        //System.out.println(Arrays.toString(strArray));
        List<String> list=new ArrayList<String>();
        list.addAll(Arrays.asList(strArray));
        System.out.println(list);
        for(int i=0;i<list.size();i++){
            System.out.println(list.get(i));
            list.remove(i);
            //list.remove(list.get(i));
            System.out.println(list);
        }
    }
}

[111, 222, 333, 444]
111
[222, 333, 444]
333
[222, 444]

不报错，但是跟我们想要的不一样，删一个，漏一个

迭代器：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        String[] strArray={"111","222","333","444"};
        //System.out.println(Arrays.toString(strArray));
        List<String> list=new ArrayList<String>();
        list.addAll(Arrays.asList(strArray));
        System.out.println(list);
        Iterator<String> it = list.iterator();
        while(it.hasNext()){
            it.next();
            it.remove();
            System.out.println(list);
        }
    }
}

[111, 222, 333, 444]
[222, 333, 444]
[333, 444]
[444]
[]

可以使用。

CopyOnWriteArrayList:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class Main {
    public static void main(String[] args) {
        String[] strArray={"111","222","333","444"};
        List<String> list=new ArrayList<String>();
        list.addAll(Arrays.asList(strArray));
        System.out.println(list);
        CopyOnWriteArrayList<String> list2=new CopyOnWriteArrayList<String>(list);
        System.out.println(list2);
        for(String item:list2){
            list2.remove(item);
            System.out.println(list2);
        }
    }
}

[111, 222, 333, 444]
[111, 222, 333, 444]
[222, 333, 444]
[333, 444]
[444]
[]

可以正常使用

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class Main {
    public static void main(String[] args) {
        String[] strArray={"111","222","333","444"};
        List<String> list=new ArrayList<String>();
        list.addAll(Arrays.asList(strArray));
        System.out.println(list);
        CopyOnWriteArrayList<String> list2=new CopyOnWriteArrayList<String>(list);
        System.out.println(list2);
        for(int i=0;i<list2.size();i++)
        {
            String item=list2.get(i);
            list2.remove(item);
            System.out.println(list2);
        }
    }
}

[111, 222, 333, 444]
[111, 222, 333, 444]
[222, 333, 444]
[222, 444]

跟ArrayList结果一样。

理想的应该这样：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class Main {
    public static void main(String[] args) {
        String[] strArray={"111","222","333","444"};
        List<String> list=new ArrayList<String>();
        list.addAll(Arrays.asList(strArray));
        System.out.println(list);
        CopyOnWriteArrayList<String> list2=new CopyOnWriteArrayList<String>(list);
        System.out.println(list2);
        for(int i=0;i<list2.size();)
        {
            String item=list2.get(i);
            list2.remove(item);
            System.out.println(list2);
        }
    }
}

View Code

总的对于一边遍历一边remove来说，foreach这种的有问题。

==================================================================

CopyOnWriteArrayList一边遍历，一遍添加

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class Main {
    public static void main(String[] args) {
        String[] strArray={"111","222","333","444"};
        List<String> list=new ArrayList<String>();
        list.addAll(Arrays.asList(strArray));
        System.out.println(list);
        CopyOnWriteArrayList<String> list2=new CopyOnWriteArrayList<String>(list);
        System.out.println(list2);
        for(int i=0;i<list2.size();i++)
        {
            if(i<6) {
                String item = list2.get(i);
                list2.add("sss");
                System.out.println(list2);
            }
        }
    }
}

[111, 222, 333, 444]
[111, 222, 333, 444]
[111, 222, 333, 444, sss]
[111, 222, 333, 444, sss, sss]
[111, 222, 333, 444, sss, sss, sss]
[111, 222, 333, 444, sss, sss, sss, sss]
[111, 222, 333, 444, sss, sss, sss, sss, sss]
[111, 222, 333, 444, sss, sss, sss, sss, sss, sss]

foreach

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class Main {
    public static void main(String[] args) {
        String[] strArray={"111","222","333","444"};
        List<String> list=new ArrayList<String>();
        list.addAll(Arrays.asList(strArray));
        System.out.println(list);
        CopyOnWriteArrayList<String> list2=new CopyOnWriteArrayList<String>(list);
        System.out.println(list2);
        for(String item:list2) {
            list2.add("sss");
            System.out.println(list2);
        }
    }
}

[111, 222, 333, 444]
[111, 222, 333, 444]
[111, 222, 333, 444, sss]
[111, 222, 333, 444, sss, sss]
[111, 222, 333, 444, sss, sss, sss]
[111, 222, 333, 444, sss, sss, sss, sss]

发现没有对foreach遍历产生影响。

迭代器：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class Main {
    public static void main(String[] args) {
        String[] strArray={"111","222","333","444"};
        List<String> list=new ArrayList<String>();
        list.addAll(Arrays.asList(strArray));
        System.out.println(list);
        CopyOnWriteArrayList<String> list2=new CopyOnWriteArrayList<String>(list);
        System.out.println(list2);
        Iterator<String> it = list2.iterator();
        while(it.hasNext()){
            it.next();
            list2.add("sss");
            System.out.println(list2);
        }
    }
}

[111, 222, 333, 444]
[111, 222, 333, 444]
[111, 222, 333, 444, sss]
[111, 222, 333, 444, sss, sss]
[111, 222, 333, 444, sss, sss, sss]
[111, 222, 333, 444, sss, sss, sss, sss]

CopyOnWrite的缺点

　　CopyOnWrite容器有很多优点，但是同时也存在两个问题，即内存占用问题和数据一致性问题。所以在开发的时候需要注意一下。

　　内存占用问题。因为CopyOnWrite的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存，旧的对象和新写入的对象。

如果这些对象占用的内存比较大，比如说200M左右，那么再写入100M数据进去，内存就会占用300M，那么这个时候很有可能造成频繁的Yong GC和Full GC。

　　针对内存占用问题，可以通过压缩容器中的元素的方法来减少大对象的内存消耗，比如ConcurrentHashMap.

　　数据一致性问题。CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，请不要使用CopyOnWrite容器。

http://www.cnblogs.com/dolphin0520/p/3938914.html

http://www.cnblogs.com/alipayhutu/archive/2012/08/11/2634073.html

https://my.oschina.net/jielucky/blog/167198

http://ifeve.com/java-copy-on-write/