一次面试，要求设计一个CopyOnWriteArrayList ？
前言
一次面试，被面试官要求设计一个CopyOnWriteArrayList的查询和添加方法，有点纳闷，居然没考算法要我设计一个List确实是没想到。
什么是CopyOnWriteArrayList？
ArrayList是线程不安全的集合，而CopyOnWriteArrayList就是ArrayList的线程安全版，那具体怎么实现线程安全？
具体到底怎么做的，可以接着往下看
CopyOnWriteArrayList是怎么设计的？
听到要我写一个CopyOnWriteArraylist的时候有点懵，毕竟没有手写过，但是大体思路是有的。
写的时候确实会要考虑很多问题：
- 手写一个CopyOnWriteArrayList需要设置的初始容量是多少？
- 手写一个CopyOnWriteArrayList要怎么样进行扩容？
- 手写一个CopyOnWriteArrayList如何保证线程安全？
那在手写之前，回顾一下CopyOnWriteArrayList的源码
可以看到比较关键的一点是这个Object[]数组是一定会用volatile关键字进行修饰的，处理多线程问题的时候volatile读的时候不会加锁
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
final transient ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array;
}
- CopyOnWriteArrayList的初始容量是多少？ --- 初始容量是0
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
-
怎样进行扩容？ --- 跟ArrayList的做法是差不多的，都是通过数组复制然后进行拷贝
ArrayList是一次性扩1.5倍，而且ArrayList的初始容量就是10
CopyOnWriteArrayList初始容量就是0，每添加一个元素，就将数组扩大1，从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();
}
}
-
如何保证线程安全？
通过上面展示的代码我们可以得到结论
CopyOnWriteArrayList是通过volatile关键字 + 锁 + 数组复制实现的线程安全
我是如何手写的？
只是让我get()和add()方法还可以，第一时间也记不起来是用ReentrantLock，就用的synchronized
public class CopyOnWriteArrayList<T> implements List<T>{
private volatile Object[] array;
private static final Object LOCK = new Object();
public CopyOnWriteArrayList() {
array = new Object[0];
}
public T get(int index) {
return (T)array[index];
}
public boolean add(T t) {
synchronized(LOCK){
int len = array.length;
Object[] newArray = Arrays.copyOf(array, len + 1);
newArray[len] = t;
array = newArray;
return true;
}
}
}
总结 --- 什么是实时一致性和什么是弱一致性？
实时一致性指的是不管什么时候读，得到的永远是最新的数据，举个例子，Java中的Hashtable就是实时一致性
我们可以通过源码来进行验证,读写操作全都直接加synchronized锁住Hashtable.Class，也就是读的时候不能写，写的时候不能读
所以读出来的数据永远都是最新的数据。
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
private transient Entry<?,?>[] table;
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
}
那什么是弱一致性？
就比如本文的CopyOnWriteArrayList就是弱一致性，在线程在读操作的时候有线程进行来写操作，在读操作的线程返回后，写操作完成了，即最新的数据不再是读线程读走了的那个数据了。
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
final transient ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array;
public E get(int index) {
return elementAt(getArray(), index);
}
static <E> E elementAt(Object[] a, int index) {
return (E) a[index];
}
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();
}
}
}
可以看到Hashtable这样实时一致性的是读写操作全部加锁，而像CopyOnWriteArrayList这样弱一致性的，读不加锁，写才加锁