线程安全的List

- Vector
- - 类的架构
  - 基本属性
  - 构造方法
  - 基本方法
- SynchronizedList和SynchronizedRandomAccessList
- - Collections.synchronizedList
  - 构造方法
  - 具体方法
  - 具体使用
- CopyOnWriteArrayList(**)
- - 简介
  - 结构
  - 成员变量
  - 常见方法
  - - add (***)
    - remove
    - get
  - CopyOnWriteArrayList总结
- 总结

在我们开发的时候用的最多的就是无序的ArrayList 和有序的LinkedList，但这两个List都是线程不安全的；那如果我们需要一款线程安全的List该如何选择呢

Vector

首先是Vector ，这是一个比较老旧的集合类，它与ArrayList 非常相似，都是基于数组实现。

类的架构

public class Vector<E>extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Vector
由于实现了RandomAccess接口，所以使用for循环可以更快捷的遍历。
很多与ArrayList类似的地方可以参考我的另一篇文章- ArrayList解析

基本属性

// 底层存储 由数组实现
protected Object[] elementData;
// 实际存储大小
protected int elementCount;
// 扩容参数** 在扩容时会根据这个参数(不为0)去扩容大小
protected int capacityIncrement;private static final long serialVersionUID = -2767605614048989439L;

这里需要注意capacityIncrement这个参数是ArrayList中没有的，用于扩容。

构造方法

public Vector() {// 默认容量为10this(10);
}
public Vector(int initialCapacity) {// 默认扩容因子为0this(initialCapacity, 0);
}
// 初始容量 扩容因子
public Vector(int initialCapacity, int capacityIncrement) {super();if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);this.elementData = new Object[initialCapacity];this.capacityIncrement = capacityIncrement;
}
public Vector(Collection<? extends E> c) {elementData = c.toArray();elementCount = elementData.length;// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}

基本方法

它几乎所有的方法都加上了 synchronized 关键词来实现线程安全，这里特别关注下扩容算法

public synchronized void copyInto(Object[] anArray) {System.arraycopy(elementData, 0, anArray, 0, elementCount);
}public synchronized void trimToSize() {modCount++;int oldCapacity = elementData.length;if (elementCount < oldCapacity) {elementData = Arrays.copyOf(elementData, elementCount);}
}public synchronized void ensureCapacity(int minCapacity) {if (minCapacity > 0) {modCount++;ensureCapacityHelper(minCapacity);}
}private void ensureCapacityHelper(int minCapacity) {// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);
}private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;// 扩容 ***
private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;// 如果扩容因子(capacityIncrement) 大于0，那么 新长度 = 旧长度 + 扩容因子// 否则 新长度 = 2 * 旧长度// 扩容算法是与ArrayList不同的点int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);
}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}public synchronized void setSize(int newSize) {modCount++;if (newSize > elementCount) {ensureCapacityHelper(newSize);} else {for (int i = newSize ; i < elementCount ; i++) {elementData[i] = null;}}elementCount = newSize;
}

大致上所有的方法都与ArrayList一致，不过都加上了synchronized关键字，这里不过多累述；具体方法可以查看我另一篇博客介绍 - ArrayList源码解析。

SynchronizedList和SynchronizedRandomAccessList

它比Vector更为强大，它可以把所有的List接口实现类(包括ArrayList LinkedList等)，都转为线程安全的list。

他有两种类型，都为Collections的静态内部类

SynchronizedList : (LinkedList等)
SynchronizedRandomAccessList : 实现了RandomAccess的list(ArrayList,Vector等)

Collections.synchronizedList

public static <T> List<T> synchronizedList(List<T> list) {// 判断list是否实现了 RandomAccess 接口(ArrayList实现了，LinkedList未实现)return (list instanceof RandomAccess ?new SynchronizedRandomAccessList<>(list) :new SynchronizedList<>(list));
}
// mutex 对象锁
static <T> List<T> synchronizedList(List<T> list, Object mutex) {return (list instanceof RandomAccess ?new SynchronizedRandomAccessList<>(list, mutex) :new SynchronizedList<>(list, mutex));
}

static class SynchronizedRandomAccessList<E>extends SynchronizedList<E>implements RandomAccessstatic class SynchronizedList<E>extends SynchronizedCollection<E>implements List<E>

构造方法

SynchronizedList(List<E> list) {super(list);this.list = list;
}
// mutex 为同步锁
SynchronizedList(List<E> list, Object mutex) {super(list, mutex);this.list = list;
}

具体方法

static class SynchronizedList<E>extends SynchronizedCollection<E>implements List<E> {private static final long serialVersionUID = -7754090372962971524L;final List<E> list;SynchronizedList(List<E> list) {super(list);this.list = list;}SynchronizedList(List<E> list, Object mutex) {super(list, mutex);this.list = list;}public boolean equals(Object o) {if (this == o)return true;synchronized (mutex) {return list.equals(o);}}public int hashCode() {synchronized (mutex) {return list.hashCode();}}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);}}public int indexOf(Object o) {synchronized (mutex) {return list.indexOf(o);}}public int lastIndexOf(Object o) {synchronized (mutex) {return list.lastIndexOf(o);}}public boolean addAll(int index, Collection<? extends E> c) {synchronized (mutex) {return list.addAll(index, c);}}public ListIterator<E> listIterator() {return list.listIterator(); // Must be manually synched by user}public ListIterator<E> listIterator(int index) {return list.listIterator(index); // Must be manually synched by user}public List<E> subList(int fromIndex, int toIndex) {synchronized (mutex) {return new SynchronizedList<>(list.subList(fromIndex, toIndex),mutex);}}@Overridepublic void replaceAll(UnaryOperator<E> operator) {synchronized (mutex) {list.replaceAll(operator);}}@Overridepublic void sort(Comparator<? super E> c) {synchronized (mutex) {list.sort(c);}}private Object readResolve() {return (list instanceof RandomAccess? new SynchronizedRandomAccessList<>(list): this);}
}

可以看到他几乎对所有的方法都加上了synchronized (mutex)同步对象锁，以此来实现list线程安全。

所以他不是性能的最优选，至少在读多写少的情况下，性能非常糟糕。

具体使用

ArrayList<String> arrayList = new ArrayList();
// 通过Collections静态方法，把list转为线程安全的list
List syncList = Collections.synchronizedList(arrayList);

CopyOnWriteArrayList(**)

简介

从字面意思上来看基于复制在写的ArrayList ，也就是在写的操作时把原数组复制一份在添加新元素。
支持高效率且是线程安全的，读操作无锁，写操作有锁(基于底层复制)
适合读多写少的场景。
他还有个兄弟叫 CopyOnWriteArraySet,这里不涉及set，所以不展开。

结构

public class CopyOnWriteArrayList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable

CopyOnWriteArrayList

成员变量

private static final long serialVersionUID = 8673264195747942595L;
// 将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会被序列化
final transient ReentrantLock lock = new ReentrantLock();
// volatile：线程对volatile变量的修改会立刻被其他线程所感知，即不会出现数据脏读的现象，从而保证数据的“可见性”
private transient volatile Object[] array;

常见方法

add (***)

public boolean add(E e) {// 首先加锁final ReentrantLock lock = this.lock;lock.lock();try {Object[] elements = getArray();int len = elements.length;// 核心：复制底层数组，且长度+1Object[] 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 {// 新建数组 并使得长度+1newElements = 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();}
}// 把c中存在 但原数组中不存在的值 添加到原数组中
public int addAllAbsent(Collection<? extends E> c) {Object[] cs = c.toArray();if (cs.length == 0)return 0;final ReentrantLock lock = this.lock;lock.lock();try {Object[] elements = getArray();int len = elements.length;int added = 0;// uniquify and compact elements in csfor (int i = 0; i < cs.length; ++i) {Object e = cs[i];if (indexOf(e, elements, 0, len) < 0 &&indexOf(e, cs, 0, added) < 0)cs[added++] = e;}if (added > 0) {Object[] newElements = Arrays.copyOf(elements, len + added);System.arraycopy(cs, 0, newElements, len, added);setArray(newElements);}return added;} finally {lock.unlock();}
}final void setArray(Object[] a) {array = a;
}

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();// 获取o所在的索引int index = indexOf(o, snapshot, 0, snapshot.length);return (index < 0) ? false : remove(o, snapshot, index);
}// 获取o所在的索引
// [查询对象o，数组，起始索引，数组长度]
private static int indexOf(Object o, Object[] elements, int index, int fence) {if (o == null) {for (int i = index; i < fence; i++)if (elements[i] == null)return i;} else {for (int i = index; i < fence; i++)if (o.equals(elements[i]))return i;}return -1;
}

remove 和 add 等方法都加上了锁

get

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