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

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

简介

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

一、CopyOnWriteArraySet

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

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

public class CopyOnWriteArraySet extends AbstractSet        implements java.io.Serializable {    // 使用一个CopyOnWriteArrayList来存放元素    private final CopyOnWriteArrayList al;    public CopyOnWriteArraySet() {        al = new CopyOnWriteArrayList();    }    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一样。

总结

	内部实现	元素是否重复	元素是否有序	线程安全否	备注
HashSet	HashMap	不重复	无序	否	-
TreeSet	TreeMap	不重复	有序	否	-
ArraySet	数组	不重复	无序	否	HashSet的内存优化版本
CopyOnWriteArraySet	CopyOnWriteArrayList	不重复	无序	是	HashSet的线程安全版本
ConcurrentSkipListSet	ConcurrentSkipListMap	不重复	有序	是	TreeSet的线程安全版本

简介

一、CopyOnWriteArraySet

二、ConcurrentSkipListSet

总结

更多相关文章

随机推荐