如何实现一个线程安全的list

前言

开发过程中，较常使用非线程安全的list，但遇到特定场景需要使用线程安全的，该如何使用呢？

是使用Vector，还是说有更好的实现方式？

1. 为什么不推荐使用Vector

Vector的底层与ArrayList类似.都是以动态数组的方式进行对象的存储，Vector与ArrayList的区别在于Vector是线程同步操作安全的，因为官方在可能涉及到线程不安全的操作都进行了synchronized操作，相当于官方帮你加了一把同步锁

那为什么又说是线程不安全的呢？原因很简单，虽然官方帮你加上了同步锁，保证同一时间只会又一个线程操作同一个方法，但是他不能控制多个线程同时操作多个方法，也就是说，删除和添加是可以同时进行的，这就产生一个问题。

删除实际上是分为两步的，第一步，找到被删除的元素所在下标，第二步，根据下标删除这个元素；

添加也分为两步，第一步，找到添加的下标，第二步，将其设为传入的参数，也就是说存在添加时，找到了数组下标，但是在进行添加时，该数组下标已经被删除的问题，反之亦然

而关于同步这个问题，我们可以使用Collections这个工具类，将我们需要线程安全的集合转换一下，而不是直接使用Vector。在我们需要同步是时候就通过如下代码实现

List syncList = Collections.synchronizedList(list);

但是否这样就能够保证同步呢？

2. SynchronizedList的同步问题

在代码中，使用了SynchronizedList，初始代码如下：
List list = Collections.synchronizedList(new ArrayList());

在运用过程中，不对该List加锁处理。上线后，定时查看后台返回的crash信息，发现对该list的操作依然出现了ConcurrentModificationException。crash信息中显示该异常发生在执行for循环时：

错误的最后一句执行代码为：java.util.ArrayList$Itr.next(ArrayList.java:831)
看来SynchronizedList并不像想象的那样绝对保证线程安全，那问题如何出现的呢？

先从增强for循环的实现说起。 增强for循环是基于迭代器实现的，如原始代码为：

for (Integer i : list) {
       System.out.println(i); 
 }

反编译后

Integer i;
for(Iterator iterator = list.iterator(); iterator.hasNext(); System.out.println(i)){
        i = (Integer)iterator.next(); 
}

而我们的crash最后一句就是java.util.ArrayList$Itr.next(ArrayList.java:831)。
按照java的fail-fast机制中的介绍：

Iterator是工作在一个独立的线程中，并且拥有一个 mutex 锁。 Iterator被创建之后会建立一个指向原来对象的单链索引表，当原来的对象数量发生变化时，这个索引表的内容不会同步改变，所以当索引指针往后移动的时候就找不到要迭代的对象，所以按照 fail-fast 原则 Iterator 会马上抛出java.util.ConcurrentModificationException异常。

最终判断出使用的SynchronizedList在遍历过程中其List出现了内容的变更。

从源码中我们可以看到SynchronizedList是通过对mutex做同步来控制线程安全的，而mutex定义在其父类SynchronizedCollection中。

SynchronizedCollection(Collection<E> collection) {
            c = collection;
            mutex = this;
}

 SynchronizedCollection(Collection<E> collection, Object mutex) {
            c = collection;
            this.mutex = mutex;
}

从源码中，我们发现了add、remove等操作都是线程安全的，加锁的对象默认是this，也即是list本身。但是没有针对Iterator.next做同步处理。所以整个for循环是非线程安全的。
另外，需要注意的是add、remove等操作仅是方法安全，如果在使用过程中执行如下代码：
list.add(object1);
list.remove(object1);
此代码并非原子操作，任何线程都可能在add和remove之间抢夺mutex。

找到了问题，那如何解决呢？

3. 更好的实现方式

从Java5开始，在java.util.concurrent包下提供了大量支持高效并发访问的集合接口和实现类：

这些线程安全的集合类分为两大类：

(1)以Concurrent开头的集合类: 如 ConcurrentHashMap、ConcurrentLinkedQueue、ConcurrentLinkedDeque、ConcurrentSkipListMap和ConcurrentSkipListSet .

(2)**以CopyOnWrite开头的集合类:**如 CopyOnWriteArrayList、CopyOnWriteArraySet .

3.1 ConcurrentSkipListSet

ConcurrentSkipListSet与ConcurrentSkipListMap的关系，与SET与HashMap的关系类似，就是采用“组合”的方式: ConcurrentSkipListSet组合了一个ConcurrentSkipListMap，将元素作为 ConcurrentSkipListMap的key存放。

3.1.1数据结构

ConcurrentSkipListSet继承于AbstractSet。因此，它本质上是一个集合。

ConcurrentSkipListSet实现了NavigableSet接口。因此，ConcurrentSkipListSet是一个有序的集合。

ConcurrentSkipListSet是通过组合ConcurrentSkipListMap实现的。它包含一个ConcurrentNavigableMap对象m，而m对象实际上是ConcurrentNavigableMap的实现类ConcurrentSkipListMap的实例。ConcurrentSkipListMap中的元素是key-value键值对；而ConcurrentSkipListSet是集合，它只用到了ConcurrentSkipListMap中的key！

3.1.2 构造器

ConcurrentSkipListSet的实现非常简单，其内部引用了一个ConcurrentSkipListMap对象，所有API方法均委托ConcurrentSkipListMap对象完成：

ConcurrentSkipListSet在构造时创建了一个ConcurrentSkipListMap对象，并由字段m引用，所以其实ConcurrentSkipListSet就是一种跳表类型的数据结构，其平均增删改查的时间复杂度均为O(logn)。

重点看下add方法：

public boolean add(E e) {
  return m.putIfAbsent(e, Boolean.TRUE) == null;
}

ConcurrentSkipListMap对键值对的要求是均不能为null，所以ConcurrentSkipListSet在插入元素的时候，用一个Boolean.TRUE对象（相当于一个值为true的Boolean型对象）作为value，同时putIfAbsent可以保证不会存在相同的Key。

所以，最终跳表中的所有Node结点的Key均不会相同，且值都是Boolean.True。

3.2 CopyOnWrite

3.2.1CopyOnWriteArrayList

CopyOnWrite (简称:COw):即先复制再写入，就是在添加元素的时候，先把原List列表复制一份,再添加新的元素。

先来看下它的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();
        }
    }

添加元素时，先加锁，再进行复制替换操作，最后再释放锁。
再来看下它的get方法源码:

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

    public E get(int index) {
        return get(getArray(), index);
    }

3.2.2CopyOnWriteArraySet

CopyOnWriteArraySet中有两个构造函数，如下代码所示

public class CopyOnWriteArraySet<E> extends AbstractSet<E> implements java.io.Serializable {
    //序列号
    private static final long serialVersionUID = 5457747651344034263L;
    //CopyOnWriteArrayList对象引用，
    //其实CopyOnWriteArraySet直接引用了CopyOnWriteArrayList来实现Set这个数据结构
    private final CopyOnWriteArrayList<E> al;

    /**
     * 默认构造函数，创建一个大小为0的数组
     */
    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }

    /**
     * 通过集合类来创建CopyOnWriteArraySet对象
     */
    public CopyOnWriteArraySet(Collection<? extends E> c) {
        //先判断集合类是否是CopyOnWriteArraySet类，若是则取出其中的CopyOnWriteArrayList对象
        if (c.getClass() == CopyOnWriteArraySet.class) {
            @SuppressWarnings("unchecked")
            CopyOnWriteArraySet<E> cc = (CopyOnWriteArraySet<E>)c;
            al = new CopyOnWriteArrayList<E>(cc.al);
        }
        else {
            //若不是，则调用addAllAbsent方法添加元素
            al = new CopyOnWriteArrayList<E>();
            //直接调用CopyOnWriteArrayList中的方法来构建
            al.addAllAbsent(c);
        }
    }
}

从上面的源码可知，CopyOnWriteArraySet其实就是直接使用了CopyOnWriteArrayList来构建的，它的内部并没有添加较多的操作

3.2.3 CopyOnWriteArrayList 与 Vector 的区别

CopyOnWriteArrayList 读性能远高于 Vector，并发线程越多优势越明显

CopyOnWriteArrayList 占用更多的内存空间

Vector 不能避免 ConcurrentModificationException 问题，而 CopyOnWriteArrayList 不存在这个问题。

3.2.4 CopyOnWrite的缺点：

CopyOnWrite存在两个问题，即内存占用问题和数据一致性问题。所以在开发时需要注意一下。

***内存占用问题 ***

在为CopyOnWrite的写时复制机制，所以在进行与操作的时候，内存里会同时驻扎两个对象内存，旧的对象和新写入的对象(注意：在复制的时候只是复制容器里的引用，只是在写的时候会创建新对象添加容器里，而旧容器的对象还在使用，所以有两个对象内存)。

如果这些对象占用的内存比较大，比如说200M左右，那么再写入100M数据进去，内存就会占用300M，那么这个时候很有可能造成频繁的Yong GC和Full GC。之前我们系统中使用了一个服务由于每晚使用CopyOnWrite机制更新大对象，造成了每晚15秒的Full GC，就用响应时间也随这变长。

针对内存占用问题，可以通过压缩容器的元素的方法来减少大对象的内存消耗，比如，如果元素全是10进制的数字，可以考虑把它压缩成36进制或64进制。或者不使用CopyOnWrite容器，而使用其他的并发容器，如ConcurrentHashMap。

***数据一致性问题 ***

CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的数据，马上能读到，请不要使用CopyOnWrite容器。

CopyOnWriteArrayList读取时不加锁，只是写入、删除、修改时加锁，所以一个线程X读取的时候另一个线程Y可能执行remove操作。remove操作首先要获取独占锁，然后进行写时复制操作，就是复制一份当前的array数组，然后在复制的新数组里面删除线程X通过get访问的元素。

在线程x执行get操作的时候并不是直接通过全局array访问数组元素而是通过方法的形参a访问的，a指向的地址和array指向的地址在调用get方法的那一刻是一样的，都指向了堆内存的数组对象。之后改变array指向的地址并不影响get的访问，因为在调用get方法的那一刻形参a指向的内存地址就已经确定了，不会改变。所以读的仍然是旧数组。