java集合之ConcurrentSkipListSet源码分析——Set大汇总

问题（1）ConcurrentSkipListSet的底层是ConcurrentSkipListMap吗？

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

（3）ConcurrentSkipListSet是有序的吗？

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

简介

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

源码分析

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

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

// 实现了NavigableSet接口，并没有所谓的ConcurrentNavigableSet接口

public class ConcurrentSkipListSet

extends AbstractSet
    
     implements NavigableSet
     
      , Cloneable, java.io.Serializable {private static final long serialVersionUID = -2479143111061671589L;// 存储使用的mapprivate 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();}// 取两个元素之间的子setpublic NavigableSet
    
      subSet(E fromElement,                              boolean fromInclusive,                              E toElement,                              boolean toInclusive) {    return new ConcurrentSkipListSet
     
              (m.subMap(fromElement, fromInclusive,                  toElement,   toInclusive));}// 取头子setpublic NavigableSet
      
        headSet(E toElement, boolean inclusive) {    return new ConcurrentSkipListSet
       
        (m.headMap(toElement, inclusive));}// 取尾子setpublic NavigableSet
        
          tailSet(E fromElement, boolean inclusive) {    return new ConcurrentSkipListSet
         
          (m.tailMap(fromElement, inclusive));}// 取子set，包含from，不包含topublic NavigableSet
          
            subSet(E fromElement, E toElement) { return subSet(fromElement, true, toElement, false);}// 取头子set，不包含topublic NavigableSet
           
             headSet(E toElement) { return headSet(toElement, false);}// 取尾子set，包含frompublic NavigableSet
            
              tailSet(E fromElement) { return tailSet(fromElement, true);}// 降序setpublic 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的一部分数据。

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

总结

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

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

（3）ConcurrentSkipListSet是线程安全的；

彩蛋

Set大汇总：

Set 有序性 线程安全 底层实现 关键接口 特点

HashSet 无 否 HashMap 无 简单LinkedHashSet 有 否 LinkedHashMap 无 插入顺序TreeSet 有 否 NavigableMap NavigableSet 自然顺序CopyOnWriteArraySet 有 是 CopyOnWriteArrayList 无 插入顺序，读写分离ConcurrentSkipListSet 有 是 ConcurrentNavigableMap NavigableSet 自然顺序从中我们可以发现一些规律：

（1）除了HashSet其它Set都是有序的；

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

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

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

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

原文地址