多线程篇（其它容器- ConcurrentSkipListSet）（持续更新迭代）

目录

一、简介

二、原理

1. 类继承图

2. 内部结构

3. 构造器

4. 核心方法

三、适用场景

四、ConcurrentSkipListSet和TreeSet对比

五、应用案例

---

一、简介

ConcurrentSkipListSet，是JUC新增的一个集合工具类，顾名思义，它是一种SET类型。

SET类型，在数学上称为“集合”，具有互异性、无序性的特点，也就是说SET中的任意两个元素均不相同（即不

包含重复元素），且元素是无序的。

JDK提供的默认SET实现——HashSet，其实就是采用“组合”的方式——内部引用了一个HashMap对象，以此

实现SET的功能。

ConcurrentSkipListSet与ConcurrentSkipListMap的关系，与SET与HashMap的关系类似，就是采用“组合”

的方式：ConcurrentSkipListSet组合了一个ConcurrentSkipListMap，将元素作为 ConcurrentSkipListMap的

key存放。

二、原理

1. 类继承图

我们来看下ConcurrentSkipListSet的类继承图：

2. 内部结构

ConcurrentSkipListSet的数据结构，如下图所示：

说明：

(01) ConcurrentSkipListSet继承于AbstractSet。因此，它本质上是一个集合。

(02) ConcurrentSkipListSet实现了NavigableSet接口。因此，ConcurrentSkipListSet是一个有序的集合。

(03) ConcurrentSkipListSet是通过组合ConcurrentSkipListMap实现的。它包含一个

ConcurrentNavigableMap对象m，而m对象实际上是ConcurrentNavigableMap的实现类

ConcurrentSkipListMap的实例。ConcurrentSkipListMap中的元素是key-value键值对；

而ConcurrentSkipListSet是集合，它只用到了ConcurrentSkipListMap中的key！

3. 构造器

ConcurrentSkipListSet的实现非常简单，其内部引用了一个ConcurrentSkipListMap对象，

所有API方法均委托ConcurrentSkipListMap对象完成：

public class ConcurrentSkipListSet<E> extends AbstractSet<E>implements NavigableSet<E>, Cloneable, java.io.Serializable {/*** The underlying map. Uses Boolean.TRUE as value for each* element.  This field is declared final for the sake of thread* safety, which entails some ugliness in 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);}public ConcurrentSkipListSet(SortedSet<E> s) {m = new ConcurrentSkipListMap<E, Object>(s.comparator());addAll(s);}ConcurrentSkipListSet(ConcurrentNavigableMap<E, Object> m) {this.m = m;}// ...
}

从上述代码可以看出，ConcurrentSkipListSet在构造时创建了一个ConcurrentSkipListMap对象，并由字段m

引用，所以其实ConcurrentSkipListSet就是一种跳表类型的数据结构，其平均增删改查的时间复杂度均为

O(logn)。

4. 核心方法

我们来看下ConcurrentSkipListSet是如何实现API方法的：

public int size() {return m.size();
}public boolean isEmpty() {return m.isEmpty();
}public boolean contains(Object o) {return m.containsKey(o);
}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();
}//...

从上述代码可以看出，所有操作均是委托ConcurrentSkipListMap对象完成的。重点看下add方法：

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

ConcurrentSkipListMap对键值对的要求是均不能为null，所以ConcurrentSkipListSet在插入元素的时候，用

一个Boolean.TRUE对象（相当于一个值为true的Boolean型对象）作为value，同时putIfAbsent可以保证不会

存在相同的Key。所以，最终跳表中的所有Node结点的Key均不会相同，且值都是Boolean.True。

三、适用场景

ConcurrentSkipListSet是线程安全的有序的集合，适用于高并发的场景。

四、ConcurrentSkipListSet和TreeSet对比

ConcurrentSkipListSet和TreeSet，它们虽然都是有序的集合。

但是，第一，它们的线程安全机制不同，TreeSet是非线程安全的，而ConcurrentSkipListSet是线程安全的。

第二，ConcurrentSkipListSet是通过ConcurrentSkipListMap实现的，而TreeSet是通过TreeMap实现的。

五、应用案例

import java.util.*;
import java.util.concurrent.*;/**   ConcurrentSkipListSet是“线程安全”的集合，而TreeSet是非线程安全的。**   下面是“多个线程同时操作并且遍历集合set”的示例*   (01) 当set是ConcurrentSkipListSet对象时，程序能正常运行。*   (02) 当set是TreeSet对象时，程序会产生ConcurrentModificationException异常。** @author skywang*/
public class ConcurrentSkipListSetDemo1 {// TODO: set是TreeSet对象时，程序会出错。//private static Set<String> set = new TreeSet<String>();private static Set<String> set = new ConcurrentSkipListSet<String>();public static void main(String[] args) {// 同时启动两个线程对set进行操作！new MyThread("a").start();new MyThread("b").start();}private static void printAll() {String value = null;Iterator iter = set.iterator();while(iter.hasNext()) {value = (String)iter.next();System.out.print(value+", ");}System.out.println();}private static class MyThread extends Thread {MyThread(String name) {super(name);}@Overridepublic void run() {int i = 0;while (i++ < 10) {// “线程名” + "序号"String val = Thread.currentThread().getName() + (i%6);set.add(val);// 通过“Iterator”遍历set。printAll();}}}
}

运行程序，结果如下：

a1, b1, 
a1, a1, a2, b1, 
b1, a1, a2, a3, b1,a1, a2, a3, a1, a4, b1, b2, 
a2, a1, a2, a3, a4, a5, b1, b2, 
a3, a0, a4, a5, a1, b1, a2, b2, 
a3, a0, a4, a1, a5, a2, b1, a3, b2, a4, b3, 
a5, a0, b1, a1, b2, a2, b3, 
a3, a0, a4, a1, a5, a2, b1, a3, b2, a4, b3, a5, b4, 
b1, a0, b2, a1, b3, a2, b4, 
a3, a0, a4, a1, a5, a2, b1, a3, b2, a4, b3, a5, b4, b1, b5, 
b2, a0, a1, a2, a3, a4, a5, b3, b1, b4, b2, b5, 
b3, a0, b4, a1, b5, 
a2, a0, a3, a1, a4, a2, a5, a3, b0, a4, b1, a5, b2, b0, b3, b1, b4, b2, b5, b3, 
b4, a0, b5, 
a1, a2, a3, a4, a5, b0, b1, b2, b3, b4, b5, 
a0, a1, a2, a3, a4, a5, b0, b1, b2, b3, b4, b5, 
a0, a1, a2, a3, a4, a5, b0, b1, b2, b3, b4, b5, 
a0, a1, a2, a3, a4, a5, b0, b1, b2, b3, b4, b5,