死磕-java集合之ConcurrentSkipListSet源码分析

问题

（1）ConcurrentSkipListSet 的底层是 ConcurrentSkipListMap 吗？

（2）ConcurrentSkipListSet 是线程安全的吗？

（3）ConcurrentSkipListSet 是有序的吗？

（4）ConcurrentSkipListSet 和之前讲的 Set 有何不同？

简介

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

源码分析

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

为了保持专栏的完整性，我还是贴一下源码，最后会对 Set 的整个家族作一个对比，有兴趣的可以直接拉到最下面。

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

    private static final long serialVersionUID = -2479143111061671589L;

    // 存储使用的 map
    private final ConcurrentNavigableMap<E,Object> m;

    // 初始化
    public ConcurrentSkipListSet() {m = new ConcurrentSkipListMap<E,Object>();
    }

    // 传入比较器【本篇文章由公众号“彤哥读源码”原创】public ConcurrentSkipListSet(Comparator<? super E> comparator) {m = new ConcurrentSkipListMap<E,Object>(comparator);
    }
    
    // 使用 ConcurrentSkipListMap 初始化 map
    // 并将集合 c 中所有元素放入到 map 中
    public ConcurrentSkipListSet(Collection<? extends E> c) {m = new ConcurrentSkipListMap<E,Object>();
        addAll(c);
    }
    
    // 使用 ConcurrentSkipListMap 初始化 map
    // 并将有序 Set 中所有元素放入到 map 中
    public ConcurrentSkipListSet(SortedSet<E> s) {m = new ConcurrentSkipListMap<E,Object>(s.comparator());
        addAll(s);
    }
    
    // ConcurrentSkipListSet 类内部返回子 set 时使用的
    ConcurrentSkipListSet(ConcurrentNavigableMap<E,Object> m) {this.m = m;}
    
    // 克隆方法
    public ConcurrentSkipListSet<E> clone() {
        try {@SuppressWarnings("unchecked")
            ConcurrentSkipListSet<E> clone =
                (ConcurrentSkipListSet<E>) super.clone();
            clone.setMap(new ConcurrentSkipListMap<E,Object>(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<E> iterator() {return m.navigableKeySet().iterator();}

    // 降序迭代器
    public Iterator<E> 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,Object> e = m.pollFirstEntry();
        return (e == null) ? null : e.getKey();}

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


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

    // 取比较器
    public Comparator<? super E> comparator() {return m.comparator();
    }

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

    // 最大的元素
    public E last() {return m.lastKey();
    }
    
    // 取两个元素之间的子 set【本篇文章由公众号“彤哥读源码”原创】public NavigableSet<E> subSet(E fromElement,
                                  boolean fromInclusive,
                                  E toElement,
                                  boolean toInclusive) {
        return new ConcurrentSkipListSet<E>
            (m.subMap(fromElement, fromInclusive,
                      toElement,   toInclusive));
    }
    
    // 取头子 set
    public NavigableSet<E> headSet(E toElement, boolean inclusive) {return new ConcurrentSkipListSet<E>(m.headMap(toElement, inclusive));
    }

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

    // 取子 set，包含 from，不包含 to
    public NavigableSet<E> subSet(E fromElement, E toElement) {return subSet(fromElement, true, toElement, false);
    }
    
    // 取头子 set，不包含 to
    public NavigableSet<E> headSet(E toElement) {return headSet(toElement, false);
    }
    
    // 取尾子 set，包含 from
    public NavigableSet<E> tailSet(E fromElement) {return tailSet(fromElement, true);
    }
    
    // 降序 set
    public NavigableSet<E> descendingSet() {return new ConcurrentSkipListSet<E>(m.descendingMap());
    }

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

    // 原子更新 map，给 clone 方法使用
    private void setMap(ConcurrentNavigableMap<E,Object> 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 的一部分数据。

另外，这里的 equals() 方法实现的相当敷衍，有很大的优化空间，作者这样实现，应该也是知道几乎没有人来调用 equals() 方法吧。

总结

（1）ConcurrentSkipListSet 底层是使用 ConcurrentNavigableMap 实现的；

（2）ConcurrentSkipListSet 有序的，基于元素的自然排序或者通过比较器确定的顺序；

（3）ConcurrentSkipListSet 是线程安全的；

彩蛋

Set 大汇总：

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

（1）除了 HashSet 其它 Set 都是有序的【本篇文章由公众号“彤哥读源码”原创】；

（2）实现了 NavigableSet 或者 SortedSet 接口的都是自然顺序的；

（3）使用并发安全的集合实现的 Set 也是并发安全的；

（4）TreeSet 虽然不是全部都是使用的 TreeMap 实现的，但其实都是跟 TreeMap 相关的（TreeMap 的子 Map 中组合了 TreeMap）；

（5）ConcurrentSkipListSet 虽然不是全部都是使用的 ConcurrentSkipListMap 实现的，但其实都是跟 ConcurrentSkipListMap 相关的（ConcurrentSkipListeMap 的子 Map 中组合了 ConcurrentSkipListMap）；

欢迎关注我的公众号“彤哥读源码”，查看更多源码系列文章, 与彤哥一起畅游源码的海洋。