摘要：介紹底層是使用存儲(chǔ)元素的，所以它并不是使用來存儲(chǔ)元素的。最簡(jiǎn)單的方式就是判斷是否中的元素都在中，中的元素是否都在中，也就是兩次兩層循環(huán)。其實(shí)，并不需要。標(biāo)記某個(gè)元素是否找到過，防止重復(fù)這個(gè)位置沒找到過才比較大小

CopyOnWriteArraySet底層是使用CopyOnWriteArrayList存儲(chǔ)元素的，所以它并不是使用Map來存儲(chǔ)元素的。

但是，我們知道CopyOnWriteArrayList底層其實(shí)是一個(gè)數(shù)組，它是允許元素重復(fù)的，那么用它來實(shí)現(xiàn)CopyOnWriteArraySet怎么保證元素不重復(fù)呢？

Set類的源碼一般都比較短，所以我們直接貼源碼上來一行一行分析吧。

public class CopyOnWriteArraySet extends AbstractSet
        implements java.io.Serializable {
    private static final long serialVersionUID = 5457747651344034263L;

    // 內(nèi)部使用CopyOnWriteArrayList存儲(chǔ)元素
    private final CopyOnWriteArrayList al;

    // 構(gòu)造方法
    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList();
    }

    // 將集合c中的元素初始化到CopyOnWriteArraySet中
    public CopyOnWriteArraySet(Collection c) {
        if (c.getClass() == CopyOnWriteArraySet.class) {
            // 如果c是CopyOnWriteArraySet類型，說明沒有重復(fù)元素，
            // 直接調(diào)用CopyOnWriteArrayList的構(gòu)造方法初始化
            @SuppressWarnings("unchecked") CopyOnWriteArraySet cc =
                (CopyOnWriteArraySet)c;
            al = new CopyOnWriteArrayList(cc.al);
        }
        else {
            // 如果c不是CopyOnWriteArraySet類型，說明有重復(fù)元素
            // 調(diào)用CopyOnWriteArrayList的addAllAbsent()方法初始化
            // 它會(huì)把重復(fù)元素排除掉
            al = new CopyOnWriteArrayList();
            al.addAllAbsent(c);
        }
    }

    // 獲取元素個(gè)數(shù)
    public int size() {
        return al.size();
    }

    // 檢查集合是否為空
    public boolean isEmpty() {
        return al.isEmpty();
    }

    // 檢查是否包含某個(gè)元素
    public boolean contains(Object o) {
        return al.contains(o);
    }

    // 集合轉(zhuǎn)數(shù)組
    public Object[] toArray() {
        return al.toArray();
    }

    // 集合轉(zhuǎn)數(shù)組，這里是可能有bug的，詳情見ArrayList中分析
    public  T[] toArray(T[] a) {
        return al.toArray(a);
    }

    // 清空所有元素
    public void clear() {
        al.clear();
    }

    // 刪除元素
    public boolean remove(Object o) {
        return al.remove(o);
    }

    // 添加元素
    // 這里是調(diào)用CopyOnWriteArrayList的addIfAbsent()方法
    // 它會(huì)檢測(cè)元素不存在的時(shí)候才添加
    // 還記得這個(gè)方法嗎？當(dāng)時(shí)有分析過的，建議把CopyOnWriteArrayList拿出來再看看
    public boolean add(E e) {
        return al.addIfAbsent(e);
    }

    // 是否包含c中的所有元素
    public boolean containsAll(Collection c) {
        return al.containsAll(c);
    }

    // 并集
    public boolean addAll(Collection c) {
        return al.addAllAbsent(c) > 0;
    }

    // 單方向差集
    public boolean removeAll(Collection c) {
        return al.removeAll(c);
    }

    // 交集
    public boolean retainAll(Collection c) {
        return al.retainAll(c);
    }

    // 迭代器
    public Iterator iterator() {
        return al.iterator();
    }

    // equals()方法
    public boolean equals(Object o) {
        // 如果兩者是同一個(gè)對(duì)象，返回true
        if (o == this)
            return true;
        // 如果o不是Set對(duì)象，返回false
        if (!(o instanceof Set))
            return false;
        Set set = (Set)(o);
        Iterator it = set.iterator();

        // 集合元素?cái)?shù)組的快照
        Object[] elements = al.getArray();
        int len = elements.length;

        // 我覺得這里的設(shè)計(jì)不太好
        // 首先，Set中的元素本來就是不重復(fù)的，所以不需要再用個(gè)matched[]數(shù)組記錄有沒有出現(xiàn)過
        // 其次，兩個(gè)集合的元素個(gè)數(shù)如果不相等，那肯定不相等了，這個(gè)是不是應(yīng)該作為第一要素先檢查
        boolean[] matched = new boolean[len];
        int k = 0;
        // 從o這個(gè)集合開始遍歷
        outer: while (it.hasNext()) {
            // 如果k>len了，說明o中元素多了
            if (++k > len)
                return false;
            // 取值
            Object x = it.next();
            // 遍歷檢查是否在當(dāng)前集合中
            for (int i = 0; i < len; ++i) {
                if (!matched[i] && eq(x, elements[i])) {
                    matched[i] = true;
                    continue outer;
                }
            }
            // 如果不在當(dāng)前集合中，返回false
            return false;
        }
        return k == len;
    }

    // 移除滿足過濾條件的元素
    public boolean removeIf(Predicate filter) {
        return al.removeIf(filter);
    }

    // 遍歷元素
    public void forEach(Consumer action) {
        al.forEach(action);
    }

    // 分割的迭代器
    public Spliterator spliterator() {
        return Spliterators.spliterator
            (al.getArray(), Spliterator.IMMUTABLE | Spliterator.DISTINCT);
    }

    // 比較兩個(gè)元素是否相等
    private static boolean eq(Object o1, Object o2) {
        return (o1 == null) ? o2 == null : o1.equals(o2);
    }
}

可以看到，在添加元素時(shí)調(diào)用了CopyOnWriteArrayList的addIfAbsent()方法來保證元素不重復(fù)。

（1）CopyOnWriteArraySet是用CopyOnWriteArrayList實(shí)現(xiàn)的；

（2）CopyOnWriteArraySet是有序的，因?yàn)榈讓悠鋵?shí)是數(shù)組，數(shù)組是有序的

（3）CopyOnWriteArraySet是并發(fā)安全的，而且實(shí)現(xiàn)了讀寫分離；

（4）CopyOnWriteArraySet通過調(diào)用CopyOnWriteArrayList的addIfAbsent()方法來保證元素不重復(fù)；

假設(shè)有兩個(gè)Set，一個(gè)是A，一個(gè)是B。

最簡(jiǎn)單的方式就是判斷是否A中的元素都在B中，B中的元素是否都在A中，也就是兩次兩層循環(huán)。

其實(shí)，并不需要。

因?yàn)镾et中的元素并不重復(fù)，所以只要先比較兩個(gè)Set的元素個(gè)數(shù)是否相等，再作一次兩層循環(huán)就可以了，需要仔細(xì)體味。代碼如下：

public class CopyOnWriteArraySetTest {

    public static void main(String[] args) {
        Set set1 = new CopyOnWriteArraySet<>();
        set1.add(1);
        set1.add(5);
        set1.add(2);
        set1.add(7);
//        set1.add(3);
        set1.add(4);

        Set set2 = new HashSet<>();
        set2.add(1);
        set2.add(5);
        set2.add(2);
        set2.add(7);
        set2.add(3);

        System.out.println(eq(set1, set2));

        System.out.println(eq(set2, set1));
    }

    private static  boolean eq(Set set1, Set set2) {
        if (set1.size() != set2.size()) {
            return false;
        }

        for (T t : set1) {
            // contains相當(dāng)于一層for循環(huán)
            if (!set2.contains(t)) {
                return false;
            }
        }

        return true;
    }
}

（2）那么，如何比較兩個(gè)List中的元素是否完全相等呢？

我們知道，List中元素是可以重復(fù)的，一次也可以搞定，設(shè)定一個(gè)標(biāo)記數(shù)組，標(biāo)記某個(gè)位置的元素是否找到過，請(qǐng)仔細(xì)體味。

public class ListEqTest {
    public static void main(String[] args) {
        List list1 = new ArrayList<>();
        list1.add(1);
        list1.add(3);
        list1.add(6);
        list1.add(3);
        list1.add(8);
        list1.add(5);

        List list2 = new ArrayList<>();
        list2.add(3);
        list2.add(1);
        list2.add(3);
        list2.add(8);
        list2.add(5);
        list2.add(6);

        System.out.println(eq(list1, list2));
        System.out.println(eq(list2, list1));
    }

    private static  boolean eq(List list1, List list2) {
        if (list1.size() != list2.size()) {
            return false;
        }

        // 標(biāo)記某個(gè)元素是否找到過，防止重復(fù)
        boolean matched[] = new boolean[list2.size()];

        outer: for (T t : list1) {
            for (int i = 0; i < list2.size(); i++) {
                // i這個(gè)位置沒找到過才比較大小
                if (!matched[i] && list2.get(i).equals(t)) {
                    matched[i] = true;
                    continue outer;
                }
            }
            return false;
        }

        return true;
    }
}