Java concurrency集合之 CopyOnWriteArrayList_动力节点Java学院整理
copyonwritearraylist介绍
它相当于线程安全的arraylist。和arraylist一样,它是个可变数组;但是和arraylist不同的时,它具有以下特性:
1. 它最适合于具有以下特征的应用程序:list 大小通常保持很小,只读操作远多于可变操作,需要在遍历期间防止线程间的冲突。
2. 它是线程安全的。
3. 因为通常需要复制整个基础数组,所以可变操作(add()、set() 和 remove() 等等)的开销很大。
4. 迭代器支持hasnext(), next()等不可变操作,但不支持可变 remove()等操作。
5. 使用迭代器进行遍历的速度很快,并且不会与其他线程发生冲突。在构造迭代器时,迭代器依赖于不变的数组快照。
copyonwritearraylist原理和数据结构
copyonwritearraylist的数据结构,如下图所示:
说明:
1. copyonwritearraylist实现了list接口,因此它是一个队列。
2. copyonwritearraylist包含了成员lock。每一个copyonwritearraylist都和一个互斥锁lock绑定,通过lock,实现了对copyonwritearraylist的互斥访问。
3. copyonwritearraylist包含了成员array数组,这说明copyonwritearraylist本质上通过数组实现的。
下面从“动态数组”和“线程安全”两个方面进一步对copyonwritearraylist的原理进行说明。
1. copyonwritearraylist的“动态数组”机制 -- 它内部有个“volatile数组”(array)来保持数据。在“添加/修改/删除”数据时,都会新建一个数组,并将更新后的数据拷贝到新建的数组中,最后再将该数组赋值给“volatile数组”。这就是它叫做copyonwritearraylist的原因!copyonwritearraylist就是通过这种方式实现的动态数组;不过正由于它在“添加/修改/删除”数据时,都会新建数组,所以涉及到修改数据的操作,copyonwritearraylist效率很
低;但是单单只是进行遍历查找的话,效率比较高。
2. copyonwritearraylist的“线程安全”机制 -- 是通过volatile和互斥锁来实现的。(01) copyonwritearraylist是通过“volatile数组”来保存数据的。一个线程读取volatile数组时,总能看到其它线程对该volatile变量最后的写入;就这样,通过volatile提供了“读取到的数据总是最新的”这个机制的
保证。(02) copyonwritearraylist通过互斥锁来保护数据。在“添加/修改/删除”数据时,会先“获取互斥锁”,再修改完毕之后,先将数据更新到“volatile数组”中,然后再“释放互斥锁”;这样,就达到了保护数据的目的。
copyonwritearraylist函数列表
// 创建一个空列表。 copyonwritearraylist() // 创建一个按 collection 的迭代器返回元素的顺序包含指定 collection 元素的列表。 copyonwritearraylist(collection<? extends e> c) // copyonwritearraylist(e[] tocopyin)
创建一个保存给定数组的副本的列表。
// 将指定元素添加到此列表的尾部。 boolean add(e e) // 在此列表的指定位置上插入指定元素。 void add(int index, e element) // 按照指定 collection 的迭代器返回元素的顺序,将指定 collection 中的所有元素添加此列表的尾部。 boolean addall(collection<? extends e> c) // 从指定位置开始,将指定 collection 的所有元素插入此列表。 boolean addall(int index, collection<? extends e> c) // 按照指定 collection 的迭代器返回元素的顺序,将指定 collection 中尚未包含在此列表中的所有元素添加列表的尾部。 int addallabsent(collection<? extends e> c) // 添加元素(如果不存在)。 boolean addifabsent(e e) // 从此列表移除所有元素。 void clear() // 返回此列表的浅表副本。 object clone() // 如果此列表包含指定的元素,则返回 true。 boolean contains(object o) // 如果此列表包含指定 collection 的所有元素,则返回 true。 boolean containsall(collection<?> c) // 比较指定对象与此列表的相等性。 boolean equals(object o) // 返回列表中指定位置的元素。 e get(int index) // 返回此列表的哈希码值。 int hashcode() // 返回第一次出现的指定元素在此列表中的索引,从 index 开始向前搜索,如果没有找到该元素,则返回 -1。 int indexof(e e, int index) // 返回此列表中第一次出现的指定元素的索引;如果此列表不包含该元素,则返回 -1。 int indexof(object o) // 如果此列表不包含任何元素,则返回 true。 boolean isempty() // 返回以恰当顺序在此列表元素上进行迭代的迭代器。 iterator<e> iterator() // 返回最后一次出现的指定元素在此列表中的索引,从 index 开始向后搜索,如果没有找到该元素,则返回 -1。 int lastindexof(e e, int index) // 返回此列表中最后出现的指定元素的索引;如果列表不包含此元素,则返回 -1。 int lastindexof(object o) // 返回此列表元素的列表迭代器(按适当顺序)。 listiterator<e> listiterator() // 返回列表中元素的列表迭代器(按适当顺序),从列表的指定位置开始。 listiterator<e> listiterator(int index) // 移除此列表指定位置上的元素。 e remove(int index) // 从此列表移除第一次出现的指定元素(如果存在)。 boolean remove(object o) // 从此列表移除所有包含在指定 collection 中的元素。 boolean removeall(collection<?> c) // 只保留此列表中包含在指定 collection 中的元素。 boolean retainall(collection<?> c) // 用指定的元素替代此列表指定位置上的元素。 e set(int index, e element) // 返回此列表中的元素数。 int size() // 返回此列表中 fromindex(包括)和 toindex(不包括)之间部分的视图。 list<e> sublist(int fromindex, int toindex) // 返回一个按恰当顺序(从第一个元素到最后一个元素)包含此列表中所有元素的数组。 object[] toarray() // 返回以恰当顺序(从第一个元素到最后一个元素)包含列表所有元素的数组;返回数组的运行时类型是指定数组的运行时类型。 <t> t[] toarray(t[] a) // 返回此列表的字符串表示形式。 string tostring()
下面我们从“创建,添加,删除,获取,遍历”这5个方面去分析copyonwritearraylist的原理。
1. 创建
copyonwritearraylist共3个构造函数。它们的源码如下:
public copyonwritearraylist() { setarray(new object[0]); } public copyonwritearraylist(collection<? extends e> c) { object[] elements = c.toarray(); if (elements.getclass() != object[].class) elements = arrays.copyof(elements, elements.length, object[].class); setarray(elements); } public copyonwritearraylist(e[] tocopyin) { setarray(arrays.copyof(tocopyin, tocopyin.length, object[].class)); } 说明:这3个构造函数都调用了setarray(),setarray()的源码如下: private volatile transient object[] array; final object[] getarray() { return array; } final void setarray(object[] a) { array = a; }
说明:setarray()的作用是给array赋值;其中,array是volatile transient object[]类型,即array是“volatile数组”。
关于volatile关键字,我们知道“volatile能让变量变得可见”,即对一个volatile变量的读,总是能看到(任意线程)对这个volatile变量最后的写入。正在由于这种特性,每次更新了“volatile数组”之后,其它线程都能看到对它所做的更新。
关于transient关键字,它是在序列化中才起作用,transient变量不会被自动序列化。transient不是本文关注的重点,了解即可。
2. 添加
以add(e e)为例,来对“copyonwritearraylist的添加操作”进行说明。下面是add(e e)的代码:
public boolean add(e e) { final reentrantlock lock = this.lock; // 获取“锁” lock.lock(); try { // 获取原始”volatile数组“中的数据和数据长度。 object[] elements = getarray(); int len = elements.length; // 新建一个数组newelements,并将原始数据拷贝到newelements中; // newelements数组的长度=“原始数组的长度”+1 object[] newelements = arrays.copyof(elements, len + 1); // 将“新增加的元素”保存到newelements中。 newelements[len] = e; // 将newelements赋值给”volatile数组“。 setarray(newelements); return true; } finally { // 释放“锁” lock.unlock(); } }
说明:add(e e)的作用就是将数据e添加到”volatile数组“中。它的实现方式是,新建一个数组,接着将原始的”volatile数组“的数据拷贝到新数组中,然后将新增数据也添加到新数组中;最后,将新数组赋值给”volatile数组“。
在add(e e)中有两点需要关注。
第一,在”添加操作“开始前,获取独占锁(lock),若此时有需要线程要获取锁,则必须等待;在操作完毕后,释放独占锁(lock),此时其它线程才能获取锁。通过独占锁,来防止多线程同时修改数据!lock的定义如下:
transient final reentrantlock lock = new reentrantlock();
第二,操作完毕时,会通过setarray()来更新”volatile数组“。而且,前面我们提过”即对一个volatile变量的读,总是能看到(任意线程)对这个volatile变量最后的写入“;这样,每次添加元素之后,其它线程都能看到新添加的元素。
3. 获取
以get(int index)为例,来对“copyonwritearraylist的删除操作”进行说明。下面是get(int index)的代码:
public e get(int index) { return get(getarray(), index); } private e get(object[] a, int index) { return (e) a[index]; }
说明:get(int index)的实现很简单,就是返回”volatile数组“中的第index个元素。
4. 删除
以remove(int index)为例,来对“copyonwritearraylist的删除操作”进行说明。下面是remove(int index)的代码:
public e remove(int index) { final reentrantlock lock = this.lock; // 获取“锁” lock.lock(); try { // 获取原始”volatile数组“中的数据和数据长度。 object[] elements = getarray(); int len = elements.length; // 获取elements数组中的第index个数据。 e oldvalue = get(elements, index); int nummoved = len - index - 1; // 如果被删除的是最后一个元素,则直接通过arrays.copyof()进行处理,而不需要新建数组。 // 否则,新建数组,然后将”volatile数组中被删除元素之外的其它元素“拷贝到新数组中;最后,将新数组赋值给”volatile数组“。 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(); } }
说明:remove(int index)的作用就是将”volatile数组“中第index个元素删除。它的实现方式是,如果被删除的是最后一个元素,则直接通过arrays.copyof()进行处理,而不需要新建数组。否则,新建数组,然后将”volatile数组中被删除元素之外的其它元素“拷贝到新数组中;最后,将新数组赋值给”volatile数组“。
和add(e e)一样,remove(int index)也是”在操作之前,获取独占锁;操作完成之后,释放独占是“;并且”在操作完成时,会通过将数据更新到volatile数组中“。
5. 遍历
以iterator()为例,来对“copyonwritearraylist的遍历操作”进行说明。下面是iterator()的代码:
public iterator<e> iterator() { return new cowiterator<e>(getarray(), 0); }
说明:iterator()会返回cowiterator对象。
cowiterator实现额listiterator接口,它的源码如下:
private static 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; } public boolean hasprevious() { return cursor > 0; } // 获取下一个元素 @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; } public void remove() { throw new unsupportedoperationexception(); } public void set(e e) { throw new unsupportedoperationexception(); } public void add(e e) { throw new unsupportedoperationexception(); } }
说明:cowiterator不支持修改元素的操作。例如,对于remove(),set(),add()等操作,cowiterator都会抛出异常!
另外,需要提到的一点是,copyonwritearraylist返回迭代器不会抛出concurrentmodificationexception异常,即它不是fail-fast机制的!
copyonwritearraylist示例
下面,我们通过一个例子去对比arraylist和copyonwritearraylist。
import java.util.*; import java.util.concurrent.*; /* * copyonwritearraylist是“线程安全”的动态数组,而arraylist是非线程安全的。 * * 下面是“多个线程同时操作并且遍历list”的示例 * (01) 当list是copyonwritearraylist对象时,程序能正常运行。 * (02) 当list是arraylist对象时,程序会产生concurrentmodificationexception异常。 * * */ public class copyonwritearraylisttest1 { // todo: list是arraylist对象时,程序会出错。 //private static list<string> list = new arraylist<string>(); private static list<string> list = new copyonwritearraylist<string>(); public static void main(string[] args) { // 同时启动两个线程对list进行操作! new mythread("ta").start(); new mythread("tb").start(); } private static void printall() { string value = null; iterator iter = list.iterator(); while(iter.hasnext()) { value = (string)iter.next(); system.out.print(value+", "); } system.out.println(); } private static class mythread extends thread { mythread(string name) { super(name); } @override public void run() { int i = 0; while (i++ < 6) { // “线程名” + "-" + "序号" string val = thread.currentthread().getname()+"-"+i; list.add(val); // 通过“iterator”遍历list。 printall(); } } } }
(某一次)运行结果:
ta-1, tb-1, ta-1, tb-1, ta-1, ta-1, tb-1, tb-1, tb-2, tb-2, ta-1, ta-2, tb-1, ta-1, tb-2, tb-1, ta-2, tb-2, tb-3, ta-2, ta-1, tb-3, tb-1, ta-3, tb-2, ta-1, ta-2, tb-1, tb-3, tb-2, ta-3, ta-2, tb-4, tb-3, ta-1, ta-3, tb-1, tb-4, tb-2, ta-4, ta-2, ta-1, tb-3, tb-1, ta-3, tb-2, tb-4, ta-2, ta-4, tb-3, tb-5, ta-3, ta-1, tb-4, tb-1, ta-4, tb-2, tb-5, ta-2, ta-5, tb-3, ta-1, ta-3, tb-1, tb-4, tb-2, ta-4, ta-2, tb-5, tb-3, ta-5, ta-3, tb-6, tb-4, ta-4, tb-5, ta-5, tb-6, ta-6,
结果说明:如果将源码中的list改成arraylist对象时,程序会产生concurrentmodificationexception异常。
推荐阅读
-
Java concurrency集合之 CopyOnWriteArrayList_动力节点Java学院整理
-
Java concurrency集合之ConcurrentHashMap_动力节点Java学院整理
-
Java concurrency集合之ConcurrentSkipListMap_动力节点Java学院整理
-
Java concurrency集合之ArrayBlockingQueue_动力节点Java学院整理
-
Java动态代理机制详解_动力节点Java学院整理
-
Java8新特性之lambda(动力节点Java学院整理)
-
Java中使用jaxp进行sax解析_动力节点Java学院整理
-
freemarker简介_动力节点Java学院整理
-
Java8之lambda最佳实践_动力节点Java学院整理
-
集群环境中使用ehcache_动力节点Java学院整理