2021-05-09 15:21  阅读(3850)
文章分类:死磕 Java 集合 文章标签:死磕 Java死磕 Java 集合Java 集合源码
©  原文作者:彤哥 原文地址:https://www.cnblogs.com/tong-yuan/

问题

(1)CopyOnWriteArraySet是用Map实现的吗?

(2)CopyOnWriteArraySet是有序的吗?

(3)CopyOnWriteArraySet是并发安全的吗?

(4)CopyOnWriteArraySet以何种方式保证元素不重复?

(5)如何比较两个Set中的元素是否完全一致?

简介

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

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

CopyOnWriteArrayList回顾请点击【死磕 java集合之CopyOnWriteArrayList源码分析】。

源码分析

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()方法来保证元素不重复。

还记得这个方法的实现原理吗?点击直达【死磕 java集合之CopyOnWriteArrayList源码分析】。

总结

(1)CopyOnWriteArraySet是用CopyOnWriteArrayList实现的;

(2)CopyOnWriteArraySet是有序的,因为底层其实是数组,数组是不是有序的?!

(3)CopyOnWriteArraySet是并发安全的,而且实现了读写分离;

(4)CopyOnWriteArraySet通过调用CopyOnWriteArrayList的addIfAbsent()方法来保证元素不重复;

彩蛋

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

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

这种设计是不是很巧妙?^^

点赞(2)
版权归原创作者所有,任何形式转载请联系作者; Java 技术驿站 >> [死磕 Java 集合] --- CopyOnWriteArraySet源码分析
上一篇
[死磕 Java 集合] --- TreeSet源码分析
下一篇
[死磕 Java 集合] --- ConcurrentSkipListSet源码分析