ConcurrentSkipListSet原理和數(shù)據(jù)結(jié)構(gòu)分析

ConcurrentSkipListSet是線程安全的有序的集合，適用于高并發(fā)的場景。
ConcurrentSkipListSet和TreeSet，它們雖然都是有序的集合。但是，第一，它們的線程安全機制不同，TreeSet是非線程安全的，而ConcurrentSkipListSet是線程安全的。第二，ConcurrentSkipListSet是通過ConcurrentSkipListMap實現(xiàn)的，而TreeSet是通過TreeMap實現(xiàn)的。

ConcurrentSkipListSet原理和數(shù)據(jù)結(jié)構(gòu)

ConcurrentSkipListSet的數(shù)據(jù)結(jié)構(gòu)，如下圖所示：

說明：
(01) ConcurrentSkipListSet繼承于AbstractSet。因此，它本質(zhì)上是一個集合。
(02) ConcurrentSkipListSet實現(xiàn)了NavigableSet接口。因此，ConcurrentSkipListSet是一個有序的集合。
(03) ConcurrentSkipListSet是通過ConcurrentSkipListMap實現(xiàn)的。它包含一個ConcurrentNavigableMap對象m，而m對象實際上是ConcurrentNavigableMap的實現(xiàn)類ConcurrentSkipListMap的實例。ConcurrentSkipListMap中的元素是key-value鍵值對；而ConcurrentSkipListSet是集合，它只用到了ConcurrentSkipListMap中的key！

ConcurrentSkipListSet函數(shù)列表

// 構(gòu)造一個新的空 set，該 set 按照元素的自然順序?qū)ζ溥M行排序。 ConcurrentSkipListSet() // 構(gòu)造一個包含指定 collection 中元素的新 set，這個新 set 按照元素的自然順序?qū)ζ溥M行排序。 ConcurrentSkipListSet(Collection<? extends E> c) // 構(gòu)造一個新的空 set，該 set 按照指定的比較器對其元素進行排序。 ConcurrentSkipListSet(Comparator<? super E> comparator) // 構(gòu)造一個新 set，該 set 所包含的元素與指定的有序 set 包含的元素相同，使用的順序也相同。 ConcurrentSkipListSet(SortedSet<E> s) // 如果此 set 中不包含指定元素，則添加指定元素。 boolean add(E e) // 返回此 set 中大于等于給定元素的最小元素；如果不存在這樣的元素，則返回 null。 E ceiling(E e) // 從此 set 中移除所有元素。 void clear() // 返回此 ConcurrentSkipListSet 實例的淺表副本。 ConcurrentSkipListSet<E> clone() // 返回對此 set 中的元素進行排序的比較器；如果此 set 使用其元素的自然順序，則返回 null。 Comparator<? super E> comparator() // 如果此 set 包含指定的元素，則返回 true。 boolean contains(Object o) // 返回在此 set 的元素上以降序進行迭代的迭代器。 Iterator<E> descendingIterator() // 返回此 set 中所包含元素的逆序視圖。 NavigableSet<E> descendingSet() // 比較指定對象與此 set 的相等性。 boolean equals(Object o) // 返回此 set 中當(dāng)前第一個（最低）元素。 E first() // 返回此 set 中小于等于給定元素的最大元素；如果不存在這樣的元素，則返回 null。 E floor(E e) // 返回此 set 的部分視圖，其元素嚴(yán)格小于 toElement。 NavigableSet<E> headSet(E toElement) // 返回此 set 的部分視圖，其元素小于（或等于，如果 inclusive 為 true）toElement。 NavigableSet<E> headSet(E toElement, boolean inclusive) // 返回此 set 中嚴(yán)格大于給定元素的最小元素；如果不存在這樣的元素，則返回 null。 E higher(E e) // 如果此 set 不包含任何元素，則返回 true。 boolean isEmpty() // 返回在此 set 的元素上以升序進行迭代的迭代器。 Iterator<E> iterator() // 返回此 set 中當(dāng)前最后一個（最高）元素。 E last() // 返回此 set 中嚴(yán)格小于給定元素的最大元素；如果不存在這樣的元素，則返回 null。 E lower(E e) // 獲取并移除第一個（最低）元素；如果此 set 為空，則返回 null。 E pollFirst() // 獲取并移除最后一個（最高）元素；如果此 set 為空，則返回 null。 E pollLast() // 如果此 set 中存在指定的元素，則將其移除。 boolean remove(Object o) // 從此 set 中移除包含在指定 collection 中的所有元素。 boolean removeAll(Collection<?> c) // 返回此 set 中的元素數(shù)目。 int size() // 返回此 set 的部分視圖，其元素范圍從 fromElement 到 toElement。 NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) // 返回此 set 的部分視圖，其元素從 fromElement（包括）到 toElement（不包括）。 NavigableSet<E> subSet(E fromElement, E toElement) // 返回此 set 的部分視圖，其元素大于等于 fromElement。 NavigableSet<E> tailSet(E fromElement) // 返回此 set 的部分視圖，其元素大于（或等于，如果 inclusive 為 true）fromElement。 NavigableSet<E> tailSet(E fromElement, boolean inclusive)

ConcurrentSkipListSet源碼(JDK1.7.0_40版本)

ConcurrentSkipListSet.java的完整源碼如下：

 View Code

ConcurrentSkipListSet是通過ConcurrentSkipListMap實現(xiàn)的，它的接口基本上都是通過調(diào)用ConcurrentSkipListMap接口來實現(xiàn)的。這里就不再對它的源碼進行分析了。

ConcurrentSkipListSet示例

1 import java.util.*; 2 import java.util.concurrent.*; 3 4 /* 5  *   ConcurrentSkipListSet是“線程安全”的集合，而TreeSet是非線程安全的。 6  * 7  *   下面是“多個線程同時操作并且遍歷集合set”的示例 8  *   (01) 當(dāng)set是ConcurrentSkipListSet對象時，程序能正常運行。 9  *   (02) 當(dāng)set是TreeSet對象時，程序會產(chǎn)生ConcurrentModificationException異常。 10  * 11  * @author skywang 12  */ 13 public class ConcurrentSkipListSetDemo1 { 14 15     // TODO: set是TreeSet對象時，程序會出錯。 16     //private static Set<String> set = new TreeSet<String>(); 17     private static Set<String> set = new ConcurrentSkipListSet<String>(); 18     public static void main(String[] args) { 19     20         // 同時啟動兩個線程對set進行操作！ 21         new MyThread("a").start(); 22         new MyThread("b").start(); 23     } 24 25     private static void printAll() { 26         String value = null; 27         Iterator iter = set.iterator(); 28         while(iter.hasNext()) { 29             value = (String)iter.next(); 30             System.out.print(value+", "); 31         } 32         System.out.println(); 33     } 34 35     private static class MyThread extends Thread { 36         MyThread(String name) { 37             super(name); 38         } 39         @Override 40         public void run() { 41                 int i = 0; 42             while (i++ < 10) { 43                 // “線程名” + "序號" 44                 String val = Thread.currentThread().getName() + (i%6); 45                 set.add(val); 46                 // 通過“Iterator”遍歷set。 47                 printAll(); 48             } 49         } 50     } 51 }

(某一次)運行結(jié)果：

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,

結(jié)果說明：
示例程序中，啟動兩個線程(線程a和線程b)分別對ConcurrentSkipListSet進行操作。以線程a而言，它會先獲取“線程名”+“序號”，然后將該字符串添加到ConcurrentSkipListSet集合中；接著，遍歷并輸出集合中的全部元素。 線程b的操作和線程a一樣，只不過線程b的名字和線程a的名字不同。
當(dāng)set是ConcurrentSkipListSet對象時，程序能正常運行。如果將set改為TreeSet時，程序會產(chǎn)生ConcurrentModificationException異常。