一次面试，要求设计一个CopyOnWriteArrayList ？

前言

一次面试，被面试官要求设计一个CopyOnWriteArrayList的查询和添加方法，有点纳闷，居然没考算法要我设计一个List确实是没想到。

什么是CopyOnWriteArrayList？

ArrayList是线程不安全的集合，而CopyOnWriteArrayList就是ArrayList的线程安全版，那具体怎么实现线程安全？

具体到底怎么做的，可以接着往下看

CopyOnWriteArrayList是怎么设计的？

听到要我写一个CopyOnWriteArraylist的时候有点懵，毕竟没有手写过，但是大体思路是有的。

写的时候确实会要考虑很多问题：

1. 手写一个CopyOnWriteArrayList需要设置的初始容量是多少？
2. 手写一个CopyOnWriteArrayList要怎么样进行扩容？
3. 手写一个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这样弱一致性的，读不加锁，写才加锁