Collecrtion 集合中的ArrayList、LinkedList
比较简单粗暴的实现方式,直接方法上增加 synchronized
关键字实现的,而且不管增删改查,即使是 get 方法都加上。
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
public boolean remove(Object o) {
return removeElement(o);
}
public synchronized boolean removeElement(Object obj) {
modCount++;
int i = indexOf(obj);
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}
public synchronized E set(int index, E element) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
}
static class SynchronizedList<E>
extends SynchronizedCollection<E>
implements List<E> {
public E get(int index) {
synchronized (mutex) {return list.get(index);}
}
public E set(int index, E element) {
synchronized (mutex) {return list.set(index, element);}
}
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
public E remove(int index) {
synchronized (mutex) {return list.remove(index);}
}
}
**get()上加同步的好处:**在 get 方法上添加同步机制也是有原因的,虽然降低了效率,但是可以让写入的数据立即可以被查询到,这也保证了数据的强一致性。
在 JDK 并发包中,目前关于 List 的并发集合,只有 CopyOnWriteArrayList 一个
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private transient volatile Object[] array;
final Object[] getArray() {
return array;
}
final void setArray(Object[] a) {
array = a;
}
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 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 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();
}
}
public E get(int index) {
return get(getArray(), index);
}
static final class COWIterator<E> implements ListIterator<E> {
/** 快照 */
private final Object[] snapshot;
/** Index of element to be returned by subsequent call to next. */
private int cursor;
private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
snapshot = elements;
}
}
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
}
CopyOnWriteArrayList 类的实现思路:Copy-On-Write, 也就是写时复制策略;末尾的 ArrayList 表示数据存放在一个数组里。在对元素进行增删改时,先把现有的数据数组拷贝一份,然后增删改都在这个拷贝数组上进行,操作完成后再把原有的数据数组替换成新数组。而原来数组不变,这样就完成了更新操作。
写时复制问题:因为每次更新都是用一个新数组替换掉老的数组,如果不巧在更新时有一个线程正在读取数据,那么读取到的就是老数组中的老数据。其实这也是读写分离的思想,放弃数据的强一致性来换取性能的提升。
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 8673264195747942595L;
final transient ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array;
final Object[] getArray() {
return array;
}
final void setArray(Object[] a) {
array = a;
}
}
可以看到CopyOnWriteArrayList源码中维护一个array对象数组用于存储集合的每个元素,并且array数组只能通过getArray和setArray方法来访问。
CopyOnWriteArrayList 的构造函数一共有三个,一个是无参构造,直接初始化数组长度为0;另外两个传入一个集合或者数组作为参数,然后会把集合或者数组中的元素直接提取出来赋值给 CopyOnWriteArrayList 内部维护的数组。
构造函数是实例创建时调用的,没有线程安全问题,所以构造方法都是简单的赋值操作,没有特殊的逻辑处理。
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
// 传入一个集合,提取集合中的元素赋值到 CopyOnWriteArrayList 数组
public CopyOnWriteArrayList(Collection<? extends E> c) {
Object[] es;
if (c.getClass() == CopyOnWriteArrayList.class)
es = ((CopyOnWriteArrayList<?>)c).getArray();
else {
es = c.toArray();
if (c.getClass() != java.util.ArrayList.class)
es = Arrays.copyOf(es, es.length, Object[].class);
}
setArray(es);
}
// 传入一个数组,数组元素提取后赋值到 CopyOnWriteArrayList 数组
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
元素新增根据入参的不同有好几个,但是原理都是一样的
通过一个 ReentrantLock 锁保证线程安全的。
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); // 拷贝一个数据数组,长度+1
newElements[len] = e; // 加入新元素
setArray(newElements); // 用新数组替换掉老数组
return true;
} finally {
lock.unlock();
}
}
分析:
由于每次 add 时容量只增加了1,所以每次增加时都要创建新的数组进行数据复制,操作完成后再替换掉老的数据,这必然会降低数据新增时候的性能。
通过 ReentrantLock 锁保证线程安全性。
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();
}
}
通过源码可以看到在修改元素前会先比较修改前后的值是否相等,**而在相等的情况下,依旧 setArray(elements);**为什么呢?想了解其中的原因需要了解下 volatile 的特殊作用,通过下面这个代码例子说明。
// initial conditions
int nonVolatileField = 0;
CopyOnWriteArrayList<String> list = /* a single String */
// Thread 1
nonVolatileField = 1; // (1)
list.set(0, "x"); // (2)
// Thread 2
String s = list.get(0); // (3)
if (s == "x") {
int localVar = nonVolatileField; // (4)
}
首先要知道 volatile 可以防止指令重排,其次要了解 happens-before 机制。说简单点就是它们可以保证代码的执行前后顺序。
比如上面例子中的代码,1 会在 2 之前执行,3 会在 4 之前执行,这都没有疑问。还有一条是 volatile 修饰的属性写会在读之前执行,所以 2会在 3 之前执行。而执行顺序还存在传递性。所以最终 1 会在 4 之前执行。这样 4 获取到的值就是步骤 1 为 nonVolatileField 赋的值。如果 CopyOnWriteArrayList 中的 set 方法内没有为相同的值进行 setArray,那么上面说的这些就都不存在了。
**个人理解:**如果源码中没有setArray(),那么多线程并发执行时,线程1可能读不到线程2在执行setArrays()方法之前做的修改,而线程1在执行setArrays()方法之前的修改对线程2有影响。
remove 删除元素方法一共有三个,这里只看public E remove(int index) 方法,原理类似。
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(); // 解锁
}
}
使用 ReentrantLock 独占锁保证操作的线程安全性,然后使用删除元素后的剩余数组元素拷贝到新数组,使用新数组替换老数组完成元素删除,最后释放锁返回。
获取下标为 index 的元素,如果元素不存在,会抛出IndexOutOfBoundsException 异常。
public E get(int index) {
return get(getArray(), index);
}
final Object[] getArray() {
return array;
}
private E get(Object[] a, int index) {
return (E) a[index];
}
这里是没有任何的加锁操作的,而获取指定位置的元素又分为了两个步骤:
很有可能在第一步执行完成之后,步骤二执行之前,有线程对数组进行了更新操作。通过上面的分析我们知道更新会生成一个新的数组,而我们第一步已经获取了老数组,所以我们在进行 get 时依旧在老数组上进行,也就是说另一个线程的更新结果没有对我们的本次 get 生效。这也是上面提到的弱一致性问题。
List<String> list = new CopyOnWriteArrayList<>();
list.add("aaaa");
list.add("bbbb");
Iterator<String> iterator = list.iterator();
list.add("cccc");
while (iterator.hasNext()) {
String next = iterator.next();
System.out.println(next);
}
aaaa
bbbb
现在 List 中添加了元素 aaaa 和 bbbb,在拿到迭代器对象后,又添加了新元素 cccc ,可以看到遍历的结果没有报错也没有输出 cccc 。也就是说拿到迭代器对象后,元素的更新不可见。
两个线程并发读取CopyOnWriteArrayList的情况,其中线程1需要通过iterator()方法读取数据,其中集合中的元素为元素1、元素2,但是这个时候线程2需要往集合中添加一个元素:元素3,这个时候线程2的操作是直接基于集合当前的数据进行复制一份到新的一个数组,最后将array变量指向新的一个数组。
注意思考这样的一个场景:假设线程1在遍历元素的时候,读到了元素1,但是还没有读到元素2的时候,线程2添加了元素3,这个时候线程1是无法读取到元素3的。这是因为线程1和线程2操作的数组不是同一个数组。 这也是CopyOnWriteArrayList的一个特点:弱一致性。意思就是说线程1看到的是某一时刻的一份“快照数据”,无法保证能读取到最新的数据。
提到fail-safe,会先提到fail-fast(快速失败),它是集合快速检测失败机制,防止集合不正确操作!
一般情况下,如果线程通过iterator方式循环集合时,另外一个线程也修改了这个集合,会报出java.util.ConcurrentModificationException,集合并发修改错误,
CopyOnWriteArrayList执行正常,原因是CopyOnWriteArrayList删除数据时会有集合快照。
所以他是fail-safe,而Vector是fail-fast!
上面的源码分析都是基于 JDK 8 进行的。新版本用了 synchronized 锁替换了老的 ReentrantLock 锁。
新增:
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;
}
}
修改:
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;
}
}
参考:https://blog.csdn.net/u013735734/article/details/109153872
CopyOnWriteArrayList 读写分离,弱一致性_duyabc的博客-CSDN博客
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/mingyuli/article/details/120384838
内容来源于网络,如有侵权,请联系作者删除!