Java并发容器之CopyOnWriteArraySet源码分析(Source code analysis of copyonwritearrayset of Java concurrency container)

一、简介

底层是使用存储元素的,所以它并不是使用来存储元素的。

CopyOnWriteArraySet
CopyOnWriteArrayList
Map

但是,底层其实是一个数组,它是允许元素重复的,那么用它来实现怎么保证元素不重复呢?

CopyOnWriteArrayList
CopyOnWriteArraySet

二、源码分析

类的源码一般都比较短,所以我们直接贴源码上来一行一行分析吧。

Set

之类的简单源码适合泛读,主要是掌握一些不常见的用法。

Set

像、之类的比较长的我们还是倾向分析主要的方法,适合精读,主要是掌握实现原理以及一些不错的思想,可能需要一两个小时才能看完一整篇文章。

ConcurrentHashMap
ConcurrentSkipListMap
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>();
    }
    
    // 将集合c中的元素初始化到CopyOnWriteArraySet中
    public CopyOnWriteArraySet(Collection<? extends E> c) {
        if (c.getClass() == CopyOnWriteArraySet.class) {
            // 如果c是CopyOnWriteArraySet类型,说明没有重复元素,
            // 直接调用CopyOnWriteArrayList的构造方法初始化
            @SuppressWarnings("unchecked") CopyOnWriteArraySet<E> cc =
                (CopyOnWriteArraySet<E>)c;
            al = new CopyOnWriteArrayList<E>(cc.al);
        }
        else {
            // 如果c不是CopyOnWriteArraySet类型,说明有重复元素
            // 调用CopyOnWriteArrayList的addAllAbsent()方法初始化
            // 它会把重复元素排除掉
            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的,详情见ArrayList中分析
    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()方法
    // 它会检测元素不存在的时候才添加
    // 还记得这个方法吗?当时有分析过的,建议把CopyOnWriteArrayList拿出来再看看
    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) {
        // 如果两者是同一个对象,返回true
        if (o == this)
            return true;
        // 如果o不是Set对象,返回false
        if (!(o instanceof Set))
            return false;
        Set<?> set = (Set<?>)(o);
        Iterator<?> it = set.iterator();

        // 集合元素数组的快照
        Object[] elements = al.getArray();
        int len = elements.length;
        
        // 我觉得这里的设计不太好
        // 首先,Set中的元素本来就是不重复的,所以不需要再用个matched[]数组记录有没有出现过
        // 其次,两个集合的元素个数如果不相等,那肯定不相等了,这个是不是应该作为第一要素先检查
        boolean[] matched = new boolean[len];
        int k = 0;
        // 从o这个集合开始遍历
        outer: while (it.hasNext()) {
            // 如果k>len了,说明o中元素多了
            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;
                }
            }
            // 如果不在当前集合中,返回false
            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);
    }

    // 分割的迭代器
    public Spliterator<E> spliterator() {
        return Spliterators.spliterator
            (al.getArray(), Spliterator.IMMUTABLE | Spliterator.DISTINCT);
    }
    
    // 比较两个元素是否相等
    private static boolean eq(Object o1, Object o2) {
        return (o1 == null) ? o2 == null : o1.equals(o2);
    }
}

可以看到,在添加元素时调用了的方法来保证元素不重复。

CopyOnWriteArrayList
addIfAbsent()

三、总结

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

四、拓展

4.1 如何比较两个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;
    }
}

4.2 如何比较两个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;
    }
}
————————

1、 Introduction

The underlying layer uses storage elements, so it does not use to store elements.

CopyOnWriteArraySet
CopyOnWriteArrayList
Map

However, the bottom layer is actually an array, which allows elements to be repeated. How to ensure that elements are not repeated?

CopyOnWriteArrayList
CopyOnWriteArraySet

2、 Source code analysis

Class source code is generally relatively short, so let’s directly post the source code and analyze it line by line.

Set

Such simple source code is suitable for extensive reading, mainly to master some uncommon usages.

Set

For the long ones like, we prefer the main method of analysis, which is suitable for intensive reading. It is mainly to master the implementation principle and some good ideas. It may take an hour or two to finish reading a whole article.

ConcurrentHashMap
ConcurrentSkipListMap
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>();
    }
    
    // 将集合c中的元素初始化到CopyOnWriteArraySet中
    public CopyOnWriteArraySet(Collection<? extends E> c) {
        if (c.getClass() == CopyOnWriteArraySet.class) {
            // 如果c是CopyOnWriteArraySet类型,说明没有重复元素,
            // 直接调用CopyOnWriteArrayList的构造方法初始化
            @SuppressWarnings("unchecked") CopyOnWriteArraySet<E> cc =
                (CopyOnWriteArraySet<E>)c;
            al = new CopyOnWriteArrayList<E>(cc.al);
        }
        else {
            // 如果c不是CopyOnWriteArraySet类型,说明有重复元素
            // 调用CopyOnWriteArrayList的addAllAbsent()方法初始化
            // 它会把重复元素排除掉
            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的,详情见ArrayList中分析
    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()方法
    // 它会检测元素不存在的时候才添加
    // 还记得这个方法吗?当时有分析过的,建议把CopyOnWriteArrayList拿出来再看看
    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) {
        // 如果两者是同一个对象,返回true
        if (o == this)
            return true;
        // 如果o不是Set对象,返回false
        if (!(o instanceof Set))
            return false;
        Set<?> set = (Set<?>)(o);
        Iterator<?> it = set.iterator();

        // 集合元素数组的快照
        Object[] elements = al.getArray();
        int len = elements.length;
        
        // 我觉得这里的设计不太好
        // 首先,Set中的元素本来就是不重复的,所以不需要再用个matched[]数组记录有没有出现过
        // 其次,两个集合的元素个数如果不相等,那肯定不相等了,这个是不是应该作为第一要素先检查
        boolean[] matched = new boolean[len];
        int k = 0;
        // 从o这个集合开始遍历
        outer: while (it.hasNext()) {
            // 如果k>len了,说明o中元素多了
            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;
                }
            }
            // 如果不在当前集合中,返回false
            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);
    }

    // 分割的迭代器
    public Spliterator<E> spliterator() {
        return Spliterators.spliterator
            (al.getArray(), Spliterator.IMMUTABLE | Spliterator.DISTINCT);
    }
    
    // 比较两个元素是否相等
    private static boolean eq(Object o1, Object o2) {
        return (o1 == null) ? o2 == null : o1.equals(o2);
    }
}

As you can see, the method is called when adding elements to ensure that the elements are not repeated.

CopyOnWriteArrayList
addIfAbsent()

3、 Summary

  • CopyOnWriteArraySet是用CopyOnWriteArrayList实现的;
  • Copyonwritearrayset is ordered, because the bottom layer is actually an array. Is the array ordered?!
  • CopyOnWriteArraySet是并发安全的,而且实现了读写分离;
  • CopyOnWriteArraySet通过调用CopyOnWriteArrayList的addIfAbsent()方法来保证元素不重复;

4、 Expand

4.1 how to compare whether the elements in two sets are completely equal?

Suppose there are two, one is, one is.

Set
A
B

The simplest way is to judge whether all the elements in are in and whether all the elements in are in, that is, two two-level loops.

A
B
B
A

In fact, it’s not necessary.

Because the elements in are not repeated, just compare whether the number of two elements is equal, and then make a two-layer cycle. You need to taste it carefully. The code is as follows:

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;
    }
}

4.2 how to compare whether the elements in two lists are completely equal?

We know that the elements in can be repeated. Do we have to do two two-level cycles?

List

In fact, you don’t need to do two-level traversal twice. You can do it once. Set a tag array to mark whether the element at a certain position has been found. Please taste it carefully. The code is as follows:

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;
    }
}