资讯专栏INFORMATION COLUMN

[学习笔记-Java集合-12] Set - CopyOnWriteArraySet源码分析

Lin_YT / 1181人阅读

摘要:介绍底层是使用存储元素的,所以它并不是使用来存储元素的。最简单的方式就是判断是否中的元素都在中,中的元素是否都在中,也就是两次两层循环。其实,并不需要。标记某个元素是否找到过,防止重复这个位置没找到过才比较大小

介绍

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

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

源码分析

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

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

    // 内部使用CopyOnWriteArrayList存储元素
    private final CopyOnWriteArrayList al;

    // 构造方法
    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList();
    }

    // 将集合c中的元素初始化到CopyOnWriteArraySet中
    public CopyOnWriteArraySet(Collection c) {
        if (c.getClass() == CopyOnWriteArraySet.class) {
            // 如果c是CopyOnWriteArraySet类型,说明没有重复元素,
            // 直接调用CopyOnWriteArrayList的构造方法初始化
            @SuppressWarnings("unchecked") CopyOnWriteArraySet cc =
                (CopyOnWriteArraySet)c;
            al = new CopyOnWriteArrayList(cc.al);
        }
        else {
            // 如果c不是CopyOnWriteArraySet类型,说明有重复元素
            // 调用CopyOnWriteArrayList的addAllAbsent()方法初始化
            // 它会把重复元素排除掉
            al = new CopyOnWriteArrayList();
            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[] 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 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) {
        // 如果两者是同一个对象,返回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 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);
    }

    // 比较两个元素是否相等
    private static boolean eq(Object o1, Object o2) {
        return (o1 == null) ? o2 == null : o1.equals(o2);
    }
}

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

总结

(1)CopyOnWriteArraySet是用CopyOnWriteArrayList实现的;

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

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

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

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

假设有两个Set,一个是A,一个是B。

最简单的方式就是判断是否A中的元素都在B中,B中的元素是否都在A中,也就是两次两层循环。

其实,并不需要。

因为Set中的元素并不重复,所以只要先比较两个Set的元素个数是否相等,再作一次两层循环就可以了,需要仔细体味。代码如下:

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相当于一层for循环
            if (!set2.contains(t)) {
                return false;
            }
        }

        return true;
    }
}

(2)那么,如何比较两个List中的元素是否完全相等呢?

我们知道,List中元素是可以重复的,一次也可以搞定,设定一个标记数组,标记某个位置的元素是否找到过,请仔细体味。

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

        // 标记某个元素是否找到过,防止重复
        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;
    }
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/76267.html

相关文章

  • [学习笔记-Java集合-13] Set - ConcurrentSkipListSet源码分析

    摘要:介绍底层是通过来实现的,它是一个有序的线程安全的集合。源码分析它的源码比较简单,跟通过实现的基本是一致,只是多了一些取最近的元素的方法。 介绍 ConcurrentSkipListSet底层是通过ConcurrentNavigableMap来实现的,它是一个有序的线程安全的集合。 源码分析 它的源码比较简单,跟通过Map实现的Set基本是一致,只是多了一些取最近的元素的方法。 // ...

    yunhao 评论0 收藏0
  • [学习笔记-Java集合-9] Set - HashSet源码分析

    摘要:源码分析属性内部使用虚拟对象,用来作为放到中构造方法非,主要是给使用的构造方法都是调用对应的构造方法。遍历元素直接调用的的迭代器。什么是机制是集合中的一种错误机制。当使用迭代器迭代时,如果发现集合有修改,则快速失败做出响应,抛出异常。 简介 集合,这个概念有点模糊。 广义上来讲,java中的集合是指java.util包下面的容器类,包括和Collection及Map相关的所有类。 中...

    kohoh_ 评论0 收藏0
  • [学习笔记-Java集合-10] Set - LinkedHashSet源码分析

    摘要:就有这个功能,它是怎么实现有序的呢源码分析继承自,让我们直接上源码来看看它们有什么不同。是有序的,它是按照插入的顺序排序的。所以,是不支持按访问顺序对元素排序的,只能按插入顺序排序。 介绍 上一节我们说HashSet中的元素是无序的,那么有没有什么办法保证Set中的元素是有序的呢? 答案是当然可以。 LinkedHashSet就有这个功能,它是怎么实现有序的呢? 源码分析 Linked...

    ThreeWords 评论0 收藏0
  • CopyOnWriteArrayList你都不知道,怎么拿offer?

    摘要:今天主要讲解的是本文力求简单讲清每个知识点,希望大家看完能有所收获一和回顾线程安全的和我们知道是用于替代的,是线程安全的容器。使用迭代器遍历时不需要显示加锁,看看与方法的实现可能就有点眉目了。 前言 只有光头才能变强 showImg(https://segmentfault.com/img/remote/1460000016931828?w=1120&h=640); 前一阵子写过一篇C...

    noONE 评论0 收藏0
  • 阿里 2021 版最全 Java 并发编程笔记,看完我才懂了“内卷”的真正意义

    摘要:纯分享直接上干货操作系统并发支持进程管理内存管理文件系统系统进程间通信网络通信阻塞队列数组有界队列链表无界队列优先级有限无界队列延时无界队列同步队列队列内存模型线程通信机制内存共享消息传递内存模型顺序一致性指令重排序原则内存语义线程 纯分享 , 直接上干货! 操作系统并发支持 进程管理内存管...

    不知名网友 评论0 收藏0

发表评论

0条评论

Lin_YT

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<