CopyOnWriteArraySet源码分析

王守钰 2020-03-05 10:03:26

CopyOnWriteArraySet的继承体系

image

全部代码

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

    // 用来存储元素的CopyOnWriteArrayList
    private final CopyOnWriteArrayList<E> al;

    /**
     * 无参构造方法
     */
    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }

    /**
     * 有参构造方法
     */
    public CopyOnWriteArraySet(Collection<? extends E> c) {
        // 判断添加的集合是否是CopyOnWriteArraySet
        if (c.getClass() == CopyOnWriteArraySet.class) {
            @SuppressWarnings("unchecked") CopyOnWriteArraySet<E> cc =
                (CopyOnWriteArraySet<E>)c;
            al = new CopyOnWriteArrayList<E>(cc.al);
        }
        else {
            al = new CopyOnWriteArrayList<E>();
            al.addAllAbsent(c);
        }
    }

    /**
     * 元素的个数
     */
    public int size() {
        return al.size();
    }

    /**
     * 是否为空
     */
    public boolean isEmpty() {
        return al.isEmpty();
    }

    /**
     * 判断是否包含某个元素
     */
    public boolean contains(Object o) {
        return al.contains(o);
    }

    /**
     * 集合转数组
     */
    public Object[] toArray() {
        return al.toArray();
    }

    /**
     * 集合转数组
     * 这里是可能有bug的
     */
    public <T> T[] toArray(T[] a) {
        return al.toArray(a);
    }

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

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

    /**
     * 添加元素
     * 这里是调用CopyOnWriteArrayList的addIfAbsent()方法
     * 它会检测元素不存在的时候才添加
     */
    public boolean add(E e) {
        return al.addIfAbsent(e);
    }

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

    /**
     * 并集
     */
    public boolean addAll(Collection<? extends E> 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<E> iterator() {
        return al.iterator();
    }

    /**
     * equals()方法
     */
    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof Set))
            return false;
        Set<?> set = (Set<?>)(o);
        Iterator<?> it = set.iterator();

        // Uses O(n^2) algorithm that is only appropriate
        // for small sets, which CopyOnWriteArraySets should be.

        //  Use a single snapshot of underlying array
        Object[] elements = al.getArray();
        int len = elements.length;
        // Mark matched elements to avoid re-checking
        boolean[] matched = new boolean[len];
        int k = 0;
        outer: while (it.hasNext()) {
            if (++k > len)
                return false;
            Object x = it.next();
            for (int i = 0; i < len; ++i) {
                if (!matched[i] && eq(x, elements[i])) {
                    matched[i] = true;
                    continue outer;
                }
            }
            return false;
        }
        return k == len;
    }

    public boolean removeIf(Predicate<? super E> filter) {
        return al.removeIf(filter);
    }

    public void forEach(Consumer<? super E> action) {
        al.forEach(action);
    }

    /**
     * Returns a {@link Spliterator} over the elements in this set in the order
     * in which these elements were added.
     *
     * <p>The {@code Spliterator} reports {@link Spliterator#IMMUTABLE},
     * {@link Spliterator#DISTINCT}, {@link Spliterator#SIZED}, and
     * {@link Spliterator#SUBSIZED}.
     *
     * <p>The spliterator provides a snapshot of the state of the set
     * when the spliterator was constructed. No synchronization is needed while
     * operating on the spliterator.
     *
     * @return a {@code Spliterator} over the elements in this set
     * @since 1.8
     */
    public Spliterator<E> spliterator() {
        return Spliterators.spliterator
            (al.getArray(), Spliterator.IMMUTABLE | Spliterator.DISTINCT);
    }

    /**
     * Tests for equality, coping with nulls.
     */
    private static boolean eq(Object o1, Object o2) {
        return (o1 == null) ? o2 == null : o1.equals(o2);
    }
}

总结

  • CopyOnWriteArraySet是用CopyOnWriteArrayList实现的;
  • CopyOnWriteArraySet是有序的,因为底层其实是数组。
  • CopyOnWriteArraySet是并发安全的,而且实现了读写分离;
  • CopyOnWriteArraySet通过调用CopyOnWriteArrayList的addIfAbsent()方法来保证元素不重复;

如何比较两个Set中的元素是否完全相等?

假设有两个Set,一个是A,一个是B。最简单的方式就是判断是否A中的元素都在B中,B中的元素是否都在A中,也就是两次两层循环。其实,并不需要。因为Set中的元素并不重复,所以只要先比较两个Set的元素个数是否相等,再作一次两层循环就可以了,需要仔细体味。代码如下:

public class CopyOnWriteArraySetTest {

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

        Set<Integer> 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 <T> boolean eq(Set<T> set1, Set<T> set2) {
        if (set1.size() != set2.size()) {
            return false;
        }

        for (T t : set1) {
            // contains相当于一层for循环
            if (!set2.contains(t)) {
                return false;
            }
        }

        return true;
    }
}

如何比较两个List中的元素是否完全相等呢?

我们知道,List中元素是可以重复的,那是不是要做两次两层循环呢?其实,也不需要做两次两层遍历,一次也可以搞定,设定一个标记数组,标记某个位置的元素是否找到过,请仔细体味。代码如下:

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

        List<Integer> 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 <T> boolean eq(List<T> list1, List<T> list2) {
        if (list1.size() != list2.size()) {
            return false;
        }

        // 标记某个元素是否找到过,防止重复
        boolean matched[] = new boolean[list2.size()];

        outer: for (T t : list1) {
            for (int i = 0; i < list2.size(); i++) {
                // i这个位置没找到过才比较大小
                if (!matched[i] && list2.get(i).equals(t)) {
                    matched[i] = true;
                    continue outer;
                }
            }
            return false;
        }

        return true;
    }
}