资讯专栏INFORMATION COLUMN

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

yunhao / 2680人阅读

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

介绍

ConcurrentSkipListSet底层是通过ConcurrentNavigableMap来实现的,它是一个有序的线程安全的集合。

源码分析

它的源码比较简单,跟通过Map实现的Set基本是一致,只是多了一些取最近的元素的方法。

// 实现了NavigableSet接口,并没有所谓的ConcurrentNavigableSet接口
public class ConcurrentSkipListSet
    extends AbstractSet
    implements NavigableSet, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2479143111061671589L;

    // 存储使用的map
    private final ConcurrentNavigableMap m;

    // 初始化
    public ConcurrentSkipListSet() {
        m = new ConcurrentSkipListMap();
    }

    // 传入比较器
    public ConcurrentSkipListSet(Comparator comparator) {
        m = new ConcurrentSkipListMap(comparator);
    }

    // 使用ConcurrentSkipListMap初始化map
    // 并将集合c中所有元素放入到map中
    public ConcurrentSkipListSet(Collection c) {
        m = new ConcurrentSkipListMap();
        addAll(c);
    }

    // 使用ConcurrentSkipListMap初始化map
    // 并将有序Set中所有元素放入到map中
    public ConcurrentSkipListSet(SortedSet s) {
        m = new ConcurrentSkipListMap(s.comparator());
        addAll(s);
    }

    // ConcurrentSkipListSet类内部返回子set时使用的
    ConcurrentSkipListSet(ConcurrentNavigableMap m) {
        this.m = m;
    }

    // 克隆方法
    public ConcurrentSkipListSet clone() {
        try {
            @SuppressWarnings("unchecked")
            ConcurrentSkipListSet clone =
                (ConcurrentSkipListSet) super.clone();
            clone.setMap(new ConcurrentSkipListMap(m));
            return clone;
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
    }

    /* ---------------- Set operations -------------- */
    // 返回元素个数
    public int size() {
        return m.size();
    }

    // 检查是否为空
    public boolean isEmpty() {
        return m.isEmpty();
    }

    // 检查是否包含某个元素
    public boolean contains(Object o) {
        return m.containsKey(o);
    }

    // 添加一个元素
    // 调用map的putIfAbsent()方法
    public boolean add(E e) {
        return m.putIfAbsent(e, Boolean.TRUE) == null;
    }

    // 移除一个元素
    public boolean remove(Object o) {
        return m.remove(o, Boolean.TRUE);
    }

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

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

    // 降序迭代器
    public Iterator descendingIterator() {
        return m.descendingKeySet().iterator();
    }


    /* ---------------- AbstractSet Overrides -------------- */
    // 比较相等方法
    public boolean equals(Object o) {
        // Override AbstractSet version to avoid calling size()
        if (o == this)
            return true;
        if (!(o instanceof Set))
            return false;
        Collection c = (Collection) o;
        try {
            // 这里是通过两次两层for循环来比较
            // 这里是有很大优化空间的,参考上篇文章CopyOnWriteArraySet中的彩蛋
            return containsAll(c) && c.containsAll(this);
        } catch (ClassCastException unused) {
            return false;
        } catch (NullPointerException unused) {
            return false;
        }
    }

    // 移除集合c中所有元素
    public boolean removeAll(Collection c) {
        // Override AbstractSet version to avoid unnecessary call to size()
        boolean modified = false;
        for (Object e : c)
            if (remove(e))
                modified = true;
        return modified;
    }

    /* ---------------- Relational operations -------------- */

    // 小于e的最大元素
    public E lower(E e) {
        return m.lowerKey(e);
    }

    // 小于等于e的最大元素
    public E floor(E e) {
        return m.floorKey(e);
    }

    // 大于等于e的最小元素
    public E ceiling(E e) {
        return m.ceilingKey(e);
    }

    // 大于e的最小元素
    public E higher(E e) {
        return m.higherKey(e);
    }

    // 弹出最小的元素
    public E pollFirst() {
        Map.Entry e = m.pollFirstEntry();
        return (e == null) ? null : e.getKey();
    }

    // 弹出最大的元素
    public E pollLast() {
        Map.Entry e = m.pollLastEntry();
        return (e == null) ? null : e.getKey();
    }


    /* ---------------- SortedSet operations -------------- */

    // 取比较器
    public Comparator comparator() {
        return m.comparator();
    }

    // 最小的元素
    public E first() {
        return m.firstKey();
    }

    // 最大的元素
    public E last() {
        return m.lastKey();
    }

    // 取两个元素之间的子set
    public NavigableSet subSet(E fromElement,
                                  boolean fromInclusive,
                                  E toElement,
                                  boolean toInclusive) {
        return new ConcurrentSkipListSet
            (m.subMap(fromElement, fromInclusive,
                      toElement,   toInclusive));
    }

    // 取头子set
    public NavigableSet headSet(E toElement, boolean inclusive) {
        return new ConcurrentSkipListSet(m.headMap(toElement, inclusive));
    }

    // 取尾子set
    public NavigableSet tailSet(E fromElement, boolean inclusive) {
        return new ConcurrentSkipListSet(m.tailMap(fromElement, inclusive));
    }

    // 取子set,包含from,不包含to
    public NavigableSet subSet(E fromElement, E toElement) {
        return subSet(fromElement, true, toElement, false);
    }

    // 取头子set,不包含to
    public NavigableSet headSet(E toElement) {
        return headSet(toElement, false);
    }

    // 取尾子set,包含from
    public NavigableSet tailSet(E fromElement) {
        return tailSet(fromElement, true);
    }

    // 降序set
    public NavigableSet descendingSet() {
        return new ConcurrentSkipListSet(m.descendingMap());
    }

    // 可分割的迭代器
    @SuppressWarnings("unchecked")
    public Spliterator spliterator() {
        if (m instanceof ConcurrentSkipListMap)
            return ((ConcurrentSkipListMap)m).keySpliterator();
        else
            return (Spliterator)((ConcurrentSkipListMap.SubMap)m).keyIterator();
    }

    // 原子更新map,给clone方法使用
    private void setMap(ConcurrentNavigableMap map) {
        UNSAFE.putObjectVolatile(this, mapOffset, map);
    }

    // 原子操作相关内容
    private static final sun.misc.Unsafe UNSAFE;
    private static final long mapOffset;
    static {
        try {
            UNSAFE = sun.misc.Unsafe.getUnsafe();
            Class k = ConcurrentSkipListSet.class;
            mapOffset = UNSAFE.objectFieldOffset
                (k.getDeclaredField("m"));
        } catch (Exception e) {
            throw new Error(e);
        }
    }
}

可以看到,ConcurrentSkipListSet基本上都是使用ConcurrentSkipListMap实现的,虽然取子set部分是使用ConcurrentSkipListMap中的内部类,但是这些内部类其实也是和ConcurrentSkipListMap相关的,它们返回ConcurrentSkipListMap的一部分数据。

总结

(1)ConcurrentSkipListSet底层是使用ConcurrentNavigableMap实现的;

(2)ConcurrentSkipListSet有序的,基于元素的自然排序或者通过比较器确定的顺序;

(3)ConcurrentSkipListSet是线程安全的;

Set大汇总
Set 有序性 线程安全 底层实现 关键接口 特点
HashSet HashMap 简单
LinkedHashSet LinkedHashMap 插入顺序
TreeSet NavigableMap NavigableSet 自然顺序
CopyOnWriteArraySet CopyOnWriteArrayList 插入顺序,读写分离
ConcurrentSkipListSet ConcurrentNavigableMap NavigableSet 自然顺序

从中我们可以发现一些规律:

除了HashSet其它Set都是有序的;

实现了NavigableSet或者SortedSet接口的都是自然顺序的;

使用并发安全的集合实现的Set也是并发安全的;

TreeSet虽然不是全部都是使用的TreeMap实现的,但其实都是跟TreeMap相关的(TreeMap的子Map中组合了TreeMap);

ConcurrentSkipListSet虽然不是全部都是使用的ConcurrentSkipListMap实现的,但其实都是跟ConcurrentSkipListMap相关的(ConcurrentSkipListeMap的子Map中组合了ConcurrentSkipListMap);

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

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

相关文章

  • Java多线程进阶(二六)—— J.U.C之collections框架:ConcurrentSkip

    摘要:我们来看下的类继承图可以看到,实现了接口,在多线程进阶二五之框架中,我们提到过实现了接口,以提供和排序相关的功能,维持元素的有序性,所以就是一种为并发环境设计的有序工具类。唯一的区别是针对的仅仅是键值,针对键值对进行操作。 showImg(https://segmentfault.com/img/bVbggic?w=960&h=600); 本文首发于一世流云专栏:https://seg...

    levius 评论0 收藏0
  • [学习笔记-Java集合-12] Set - CopyOnWriteArraySet源码分析

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

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

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

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

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

    不知名网友 评论0 收藏0
  • [学习笔记-Java集合-10] Set - LinkedHashSet源码分析

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

    ThreeWords 评论0 收藏0

发表评论

0条评论

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