摘要：我們來看下的類繼承圖可以看到，實現了接口，在多線程進階二五之框架中，我們提到過實現了接口，以提供和排序相關的功能，維持元素的有序性，所以就是一種為并發環境設計的有序工具類。唯一的區別是針對的僅僅是鍵值，針對鍵值對進行操作。
本文首發于一世流云專欄：https://segmentfault.com/blog...
一、ConcurrentSkipListSet簡介
ConcurrentSkipListSet，是JDK1.6時J.U.C新增的一個集合工具類，顧名思義，它是一種SET類型。
SET類型，在數學上稱為“集合”，具有互異性、無序性的特點，也就是說SET中的任意兩個元素均不相同（即不包含重復元素），且元素是無序的。
是不是感覺和HashMap有點類似？HashMap中的Key也是不能重復，且是無序的。
事實上，JDK提供的默認SET實現——HashSet，其實就是采用“組合”的方式——內部引用了一個HashMap對象，以此實現SET的功能。
我們來看下ConcurrentSkipListSet的類繼承圖：
可以看到，ConcurrentSkipListSet實現了NavigableSet接口，在Java多線程進階（二五）—— J.U.C之collections框架：ConcurrentSkipListMap中，我們提到過ConcurrentSkipListMap實現了NavigableMap接口，以提供和排序相關的功能，維持元素的有序性，所以ConcurrentSkipListSet就是一種為并發環境設計的有序SET工具類。
NavigableSet的功能和NavigableMap幾乎是完全一樣的，提供了根據指定Key返回最接近項、按升序/降序返回所有鍵的視圖等功能。唯一的區別是NavigableSet針對的僅僅是鍵值，NavigableMap針對鍵值對進行操作。
二、ConcurrentSkipListSet原理
內部結構
ConcurrentSkipListSet的實現非常簡單，其內部引用了一個ConcurrentSkipListMap對象，所有API方法均委托ConcurrentSkipListMap對象完成：
public class ConcurrentSkipListSet extends AbstractSet
implements NavigableSet, 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 m;
public ConcurrentSkipListSet() {
m = new ConcurrentSkipListMap();
}
public ConcurrentSkipListSet(Comparator comparator) {
m = new ConcurrentSkipListMap(comparator);
}
public ConcurrentSkipListSet(Collection c) {
m = new ConcurrentSkipListMap();
addAll(c);
}
public ConcurrentSkipListSet(SortedSet s) {
m = new ConcurrentSkipListMap(s.comparator());
addAll(s);
}
ConcurrentSkipListSet(ConcurrentNavigableMap m) {
this.m = m;
}
// ...
}
從上述代碼可以看出，ConcurrentSkipListSet在構造時創建了一個ConcurrentSkipListMap對象，并由字段m引用，所以其實ConcurrentSkipListSet就是一種跳表類型的數據結構，其平均增刪改查的時間復雜度均為O(logn)。
核心方法
我們來看下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。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76941.html
