摘要：介紹底層是通過來實現的，它是一個有序的線程安全的集合。源碼分析它的源碼比較簡單，跟通過實現的基本是一致，只是多了一些取最近的元素的方法。
介紹
ConcurrentSkipListSet底層是通過ConcurrentNavigableMap來實現的，它是一個有序的線程安全的集合。
源碼分析
它的源碼比較簡單，跟通過Map實現的Set基本是一致，只是多了一些取最近的元素的方法。
// 實現了NavigableSet接口，并沒有所謂的ConcurrentNavigableSet接口
public class ConcurrentSkipListSet
extends AbstractSet
implements NavigableSet, Cloneable, java.io.Serializable {
private static final long serialVersionUID = -2479143111061671589L;
// 存儲使用的map
private 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();
}
// 取兩個元素之間的子set
public NavigableSet subSet(E fromElement,
boolean fromInclusive,
E toElement,
boolean toInclusive) {
return new ConcurrentSkipListSet
(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
}
// 取頭子set
public NavigableSet headSet(E toElement, boolean inclusive) {
return new ConcurrentSkipListSet(m.headMap(toElement, inclusive));
}
// 取尾子set
public NavigableSet tailSet(E fromElement, boolean inclusive) {
return new ConcurrentSkipListSet(m.tailMap(fromElement, inclusive));
}
// 取子set，包含from，不包含to
public NavigableSet subSet(E fromElement, E toElement) {
return subSet(fromElement, true, toElement, false);
}
// 取頭子set，不包含to
public NavigableSet headSet(E toElement) {
return headSet(toElement, false);
}
// 取尾子set，包含from
public NavigableSet tailSet(E fromElement) {
return tailSet(fromElement, true);
}
// 降序set
public 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的一部分數據。
總結
（1）ConcurrentSkipListSet底層是使用ConcurrentNavigableMap實現的；
（2）ConcurrentSkipListSet有序的，基于元素的自然排序或者通過比較器確定的順序；
（3）ConcurrentSkipListSet是線程安全的；
Set大匯總
| Set |
有序性 |
線程安全 |
底層實現 |
關鍵接口 |
特點 |
| HashSet |
無 |
否 |
HashMap |
無 |
簡單 |
| LinkedHashSet |
有 |
否 |
LinkedHashMap |
無 |
插入順序 |
| TreeSet |
有 |
否 |
NavigableMap |
NavigableSet |
自然順序 |
| CopyOnWriteArraySet |
有 |
是 |
CopyOnWriteArrayList |
無 |
插入順序，讀寫分離 |
| ConcurrentSkipListSet |
有 |
是 |
ConcurrentNavigableMap |
NavigableSet |
自然順序 |
從中我們可以發現一些規律：
除了HashSet其它Set都是有序的；
實現了NavigableSet或者SortedSet接口的都是自然順序的；
使用并發安全的集合實現的Set也是并發安全的；
TreeSet雖然不是全部都是使用的TreeMap實現的，但其實都是跟TreeMap相關的（TreeMap的子Map中組合了TreeMap）；
ConcurrentSkipListSet雖然不是全部都是使用的ConcurrentSkipListMap實現的，但其實都是跟ConcurrentSkipListMap相關的（ConcurrentSkipListeMap的子Map中組合了ConcurrentSkipListMap）；
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76265.html
