Java源码系列(16) -- ConcurrentSkipListSet

一、类签名

ConcurrentSkipListSet是一个基于ConcurrentSkipListMap的可伸缩并发(NavigableSet)实现。所有元素根据其可比较的自然次序，或构造时提供的Comparator决定排列顺序，具体由所使用的构造方法决定。

public class ConcurrentSkipListSet<E>
    extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable

此实现在contains、add、remove等操作上预计平均时间开销为log(n)。插入、移除、访问操作在多线程下操作都是线程安全的。

递增排序视图和其迭代器都比递减方式的速度要快。

需要注意的是，不像大多数集合，size()并不是一个常数时间操作。由于集合的异步特性，当前数量需遍历元素后确定。若遍历过程中集合元素在改变，会返回一个不准确的元素数量值。

批量操作如添加、移除、检查多个元素，譬如addAll、removeIf、forEach等都不保证其原子性。就像forEach遍历和另一个线程的addAll并发执行，可能会导致只有一部分新元素能被forEach察觉。

本类和其迭代器实现了Set和Iterator接口的可选方法。像其他多数并发集合实现，此类不允许使用为null的元素。因为数据值null和返回值，不能与缺失元素的null做出区分。（备注：返回值为null表示元素不存在，而不表示元素的值为null）

源码基于JDK10。

二、数据成员

ConcurrentSkipListSet基于ConcurrentNavigableMap实现集合去重特性。由于ConcurrentNavigableMap是<K, V>的，所以使用Boolean.TRUE表示该元素已存在。此变量被修饰为final是为了线程安全，但同时也导致clone()方法实现的一点丑陋。

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

指定数据集构造新集合，元素顺序由其可比较自然次序决定。

public ConcurrentSkipListSet(Collection<? extends E> c) {
    m = new ConcurrentSkipListMap<E,Object>();
    addAll(c);
}

构造一个全新的集合，元素顺序由SortedSet的comparator决定。存入元素顺序和SortedSet元素顺序一致。

public ConcurrentSkipListSet(SortedSet<E> s) {
    m = new ConcurrentSkipListMap<E,Object>(s.comparator());
    addAll(s);
}

此构造方法由submaps使用。

ConcurrentSkipListSet(ConcurrentNavigableMap<E,Object> m) {
    this.m = m;
}

四、集合操作

返回集合元素数量，如果集合元素数量超过Integer.MAX_VALUE，则返回Integer.MAX_VALUE。

需要注意的是，不像其他多数集合的实现，此方法不是常数时间的操作。因其异步特性，统计元素数量需要遍历集合所有元素。而且，集合元素实际数量有可能在遍历过程中发生变化，这会导致最终返回值不准确。因此，此方法在并发应用中的实用性并不高。由于每次获取总数需要遍历所有元素，即使在多线程操作下，也应尽量减少调用此方法。

public int size() {
    return m.size();
}

检查集合是否为空。

public boolean isEmpty() {
    return m.isEmpty();
}

检查指定元素是否已包含在集合中，元素o为空抛出NullPointerException。从集合获取的元素类型转换失败抛出ClassCastException。

public boolean contains(Object o) {
    return m.containsKey(o);
}

把指定元素添加到集合中。元素不存在于集合，添加成功后返回true。如果元素已经存在于原集合，原集合将保持不变且返回false。

public boolean add(E e) {
    return m.putIfAbsent(e, Boolean.TRUE) == null;
}

在指定元素存在于本集合的时候，移除集合匹配元素。移除成功返回true，否则返回false。

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重载

检查两个集合元素是否完全一致。重写此方法，避免父类实现调用此类的size()方法。上文已经提到，size()方法在并发的场景下返回的数值不一定准确。

public boolean equals(Object o) {
    // 两者是相同实例，返回true
    if (o == this)
        return true;
    // o不是集合类，返回false
    if (!(o instanceof Set))
        return false;
    // 检查两个集合的元素是否完全一致
    Collection<?> c = (Collection<?>) o;
    try {
        return containsAll(c) && c.containsAll(this);
    } catch (ClassCastException unused) {
        return false;
    } catch (NullPointerException unused) {
        return false;
    }
}

移除所有集合c存在于原集合的元素。重写此方法，避免父类实现调用此类的size()方法。上文已经提到，size()方法在并发的场景下返回的数值不一定准确。

public boolean removeAll(Collection<?> c) {
    boolean modified = false;
    for (Object e : c)
        if (remove(e))
            modified = true;
    return modified;
}

六、相关操作

// 类型转换失败抛出ClassCastException
// 元素e为空抛出NullPointerException
public E lower(E e) {
    return m.lowerKey(e);
}

// 类型转换失败抛出ClassCastException
// 元素e为空抛出NullPointerException
public E floor(E e) {
    return m.floorKey(e);
}

// 类型转换失败抛出ClassCastException
// 元素e为空抛出NullPointerException
public E ceiling(E e) {
    return m.ceilingKey(e);
}

// 类型转换失败抛出ClassCastException
// 元素e为空抛出NullPointerException
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操作

返回集合的比较器。

public Comparator<? super E> comparator() {
    return m.comparator();
}

没有此元素抛出NoSuchElementException。

public E first() {
    return m.firstKey();
}

没有此元素抛出NoSuchElementException。

public E last() {
    return m.lastKey();
}