Java（Android）数据结构汇总（二）-- Set（下）

传送门：Java（Android）数据结构汇总 -- 总纲

简介

Set在java.util.concurrent包下的主要有CopyOnWriteArraySet和ConcurrentSkipListSet两个实现类。

一、CopyOnWriteArraySet

上一章讲了HashSet是一个无序的、元素不重复的、线程不安全的集合，CopyOnWriteArraySet在此基础上实现了线程安全。也就是说它是一个无序的、元素不重复的、线程安全的集合。

CopyOnWriteArraySet内部使用的是CopyOnWriteArrayList来实现的（HashSet内部是使用HashMap来实现的），对CopyOnWriteArrayList不熟悉的可以看前面的章节。源码如下：

public class CopyOnWriteArraySet<E> extends AbstractSet<E>
        implements java.io.Serializable {

    // 使用一个CopyOnWriteArrayList来存放元素
    private final CopyOnWriteArrayList<E> al;

    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }

    public boolean add(E e) {
        // 注意这里调用的是CopyOnWriteArrayList的addIfAbsent方法，这个方法保证了元素的唯一性，
        // 从而保证了CopyOnWriteArraySet的元素不重复
        return al.addIfAbsent(e);
    }
}

我们再来看看CopyOnWriteArrayList的addIfAbsent()方法：

public boolean addIfAbsent(E e) {
    // 内部数组
    Object[] snapshot = getArray();

    // indexOf方法用于在这个数组中查找要插入的元素，
    // 如果找到了就返回false，否则调用addIfAbsent(e, snapshot)来进行插入操作
    return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false : addIfAbsent(e, snapshot);
}

private boolean addIfAbsent(E e, Object[] snapshot) {
    // 前面我们讲了，CopyOnWriteArrayList在修改数据的时候要加锁同步
    synchronized (lock) {
        Object[] current = getArray();
        int len = current.length;
        // 判断数组长度是否发生了变化
        if (snapshot != current) {
            // Optimize for lost race to another addXXX operation
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++)
                if (current[i] != snapshot[i] && Objects.equals(e, current[i]))
                    return false;
            if (indexOf(e, current, common, len) >= 0)
                    return false;
        }
        Object[] newElements = Arrays.copyOf(current, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    }
}

可见，CopyOnWriteArraySet还是非常简单的，这里就不多讲。

二、ConcurrentSkipListSet

上一章讲了TreeSet，它是一个有序的、元素不重复的、线程不安全的集合。ConcurrentSkipListSet在此基础上增加了线程安全。也就是说它是一个有序的、元素不重复的、线程安全的集合。

ConcurrentSkipListSet内部使用的是ConcurrentSkipListMap来实现的（TreeSet内部使用的TreeMap实现）。对ConcurrentSkipListMap不清楚的可以看第四章对Map的介绍。除了上面这些特点之外，其他的和TreeSet一样。

总结