ConcurrentSkipListMap介紹
ConcurrentSkipListMap是線程安全的有序的哈希表，適用于高并發的場景。
ConcurrentSkipListMap和TreeMap，它們雖然都是有序的哈希表。但是，第一，它們的線程安全機制不同，TreeMap是非線程安全的，而ConcurrentSkipListMap是線程安全的。第二，ConcurrentSkipListMap是通過跳表實現的，而TreeMap是通過紅黑樹實現的。
關于跳表(Skip List)，它是平衡樹的一種替代的數據結構，但是和紅黑樹不相同的是，跳表對于樹的平衡的實現是基于一種隨機化的算法的，這樣也就是說跳表的插入和刪除的工作是比較簡單的。
ConcurrentSkipListMap原理和數據結構
ConcurrentSkipListMap的數據結構，如下圖所示：
說明：
先以數據“7,14,21,32,37,71,85”序列為例，來對跳表進行簡單說明。
跳表分為許多層(level)，每一層都可以看作是數據的索引，這些索引的意義就是加快跳表查找數據速度。每一層的數據都是有序的，上一層數據是下一層數據的子集，并且第一層(level 1)包含了全部的數據；層次越高，跳躍性越大，包含的數據越少。
跳表包含一個表頭，它查找數據時，是從上往下，從左往右進行查找。現在“需要找出值為32的節點”為例，來對比說明跳表和普遍的鏈表。
情況1：鏈表中查找“32”節點
路徑如下圖1-02所示：
需要4步(紅色部分表示路徑)。
情況2：跳表中查找“32”節點
路徑如下圖1-03所示：
忽略索引垂直線路上路徑的情況下，只需要2步(紅色部分表示路徑)。
下面說說Java中ConcurrentSkipListMap的數據結構。
(01) ConcurrentSkipListMap繼承于AbstractMap類，也就意味著它是一個哈希表。
(02) Index是ConcurrentSkipListMap的內部類，它與“跳表中的索引相對應”。HeadIndex繼承于Index，ConcurrentSkipListMap中含有一個HeadIndex的對象head，head是“跳表的表頭”。
(03) Index是跳表中的索引，它包含“右索引的指針(right)”，“下索引的指針(down)”和“哈希表節點node”。node是Node的對象，Node也是ConcurrentSkipListMap中的內部類。
ConcurrentSkipListMap函數列表
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
// 構造一個新的空映射，該映射按照鍵的自然順序進行排序。ConcurrentSkipListMap()// 構造一個新的空映射，該映射按照指定的比較器進行排序。ConcurrentSkipListMap(Comparator<? super K> comparator)// 構造一個新映射，該映射所包含的映射關系與給定映射包含的映射關系相同，并按照鍵的自然順序進行排序。ConcurrentSkipListMap(Map<? extends K,? extends V> m)// 構造一個新映射，該映射所包含的映射關系與指定的有序映射包含的映射關系相同，使用的順序也相同。ConcurrentSkipListMap(SortedMap<K,? extends V> m)// 返回與大于等于給定鍵的最小鍵關聯的鍵-值映射關系；如果不存在這樣的條目，則返回 null。Map.Entry<K,V> ceilingEntry(K key)// 返回大于等于給定鍵的最小鍵；如果不存在這樣的鍵，則返回 null。K ceilingKey(K key)// 從此映射中移除所有映射關系。void clear()// 返回此 ConcurrentSkipListMap 實例的淺表副本。ConcurrentSkipListMap<K,V> clone()// 返回對此映射中的鍵進行排序的比較器；如果此映射使用鍵的自然順序，則返回 null。Comparator<? super K> comparator()// 如果此映射包含指定鍵的映射關系，則返回 true。boolean containsKey(Object key)// 如果此映射為指定值映射一個或多個鍵，則返回 true。boolean containsValue(Object value)// 返回此映射中所包含鍵的逆序 NavigableSet 視圖。NavigableSet<K> descendingKeySet()// 返回此映射中所包含映射關系的逆序視圖。ConcurrentNavigableMap<K,V> descendingMap()// 返回此映射中所包含的映射關系的 Set 視圖。Set<Map.Entry<K,V>> entrySet()// 比較指定對象與此映射的相等性。boolean equals(Object o)// 返回與此映射中的最小鍵關聯的鍵-值映射關系；如果該映射為空，則返回 null。Map.Entry<K,V> firstEntry()// 返回此映射中當前第一個（最低）鍵。K firstKey()// 返回與小于等于給定鍵的最大鍵關聯的鍵-值映射關系；如果不存在這樣的鍵，則返回 null。Map.Entry<K,V> floorEntry(K key)// 返回小于等于給定鍵的最大鍵；如果不存在這樣的鍵，則返回 null。K floorKey(K key)// 返回指定鍵所映射到的值；如果此映射不包含該鍵的映射關系，則返回 null。V get(Object key)// 返回此映射的部分視圖，其鍵值嚴格小于 toKey。ConcurrentNavigableMap<K,V> headMap(K toKey)// 返回此映射的部分視圖，其鍵小于（或等于，如果 inclusive 為 true）toKey。ConcurrentNavigableMap<K,V> headMap(K toKey, boolean inclusive)// 返回與嚴格大于給定鍵的最小鍵關聯的鍵-值映射關系；如果不存在這樣的鍵，則返回 null。Map.Entry<K,V> higherEntry(K key)// 返回嚴格大于給定鍵的最小鍵；如果不存在這樣的鍵，則返回 null。K higherKey(K key)// 如果此映射未包含鍵-值映射關系，則返回 true。boolean isEmpty()// 返回此映射中所包含鍵的 NavigableSet 視圖。NavigableSet<K> keySet()// 返回與此映射中的最大鍵關聯的鍵-值映射關系；如果該映射為空，則返回 null。Map.Entry<K,V> lastEntry()// 返回映射中當前最后一個（最高）鍵。K lastKey()// 返回與嚴格小于給定鍵的最大鍵關聯的鍵-值映射關系；如果不存在這樣的鍵，則返回 null。Map.Entry<K,V> lowerEntry(K key)// 返回嚴格小于給定鍵的最大鍵；如果不存在這樣的鍵，則返回 null。K lowerKey(K key)// 返回此映射中所包含鍵的 NavigableSet 視圖。NavigableSet<K> navigableKeySet()// 移除并返回與此映射中的最小鍵關聯的鍵-值映射關系；如果該映射為空，則返回 null。Map.Entry<K,V> pollFirstEntry()// 移除并返回與此映射中的最大鍵關聯的鍵-值映射關系；如果該映射為空，則返回 null。Map.Entry<K,V> pollLastEntry()// 將指定值與此映射中的指定鍵關聯。V put(K key, V value)// 如果指定鍵已經不再與某個值相關聯，則將它與給定值關聯。V putIfAbsent(K key, V value)// 從此映射中移除指定鍵的映射關系（如果存在）。V remove(Object key)// 只有目前將鍵的條目映射到給定值時，才移除該鍵的條目。boolean remove(Object key, Object value)// 只有目前將鍵的條目映射到某一值時，才替換該鍵的條目。V replace(K key, V value)// 只有目前將鍵的條目映射到給定值時，才替換該鍵的條目。boolean replace(K key, V oldValue, V newValue)// 返回此映射中的鍵-值映射關系數。int size()// 返回此映射的部分視圖，其鍵的范圍從 fromKey 到 toKey。ConcurrentNavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)// 返回此映射的部分視圖，其鍵值的范圍從 fromKey（包括）到 toKey（不包括）。ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey)// 返回此映射的部分視圖，其鍵大于等于 fromKey。ConcurrentNavigableMap<K,V> tailMap(K fromKey)// 返回此映射的部分視圖，其鍵大于（或等于，如果 inclusive 為 true）fromKey。ConcurrentNavigableMap<K,V> tailMap(K fromKey, boolean inclusive)// 返回此映射中所包含值的 Collection 視圖。Collection<V> values() |
下面從ConcurrentSkipListMap的添加，刪除，獲取這3個方面對它進行分析。
1. 添加
下面以put(K key, V value)為例，對ConcurrentSkipListMap的添加方法進行說明。
|
1
2
3
4
5
|
public V put(K key, V value) { if (value == null) throw new NullPointerException(); return doPut(key, value, false);} |
實際上，put()是通過doPut()將key-value鍵值對添加到ConcurrentSkipListMap中的。
doPut()的源碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
private V doPut(K kkey, V value, boolean onlyIfAbsent) { Comparable<? super K> key = comparable(kkey); for (;;) { // 找到key的前繼節點 Node<K,V> b = findPredecessor(key); // 設置n為“key的前繼節點的后繼節點”，即n應該是“插入節點”的“后繼節點” Node<K,V> n = b.next; for (;;) { if (n != null) { Node<K,V> f = n.next; // 如果兩次獲得的b.next不是相同的Node，就跳轉到”外層for循環“，重新獲得b和n后再遍歷。 if (n != b.next) break; // v是“n的值” Object v = n.value; // 當n的值為null(意味著其它線程刪除了n)；此時刪除b的下一個節點，然后跳轉到”外層for循環“，重新獲得b和n后再遍歷。 if (v == null) { // n is deleted n.helpDelete(b, f); break; } // 如果其它線程刪除了b；則跳轉到”外層for循環“，重新獲得b和n后再遍歷。 if (v == n || b.value == null) // b is deleted break; // 比較key和n.key int c = key.compareTo(n.key); if (c > 0) { b = n; n = f; continue; } if (c == 0) { if (onlyIfAbsent || n.casValue(v, value)) return (V)v; else break; // restart if lost race to replace value } // else c < 0; fall through } // 新建節點(對應是“要插入的鍵值對”) Node<K,V> z = new Node<K,V>(kkey, value, n); // 設置“b的后繼節點”為z if (!b.casNext(n, z)) break; // 多線程情況下，break才可能發生(其它線程對b進行了操作) // 隨機獲取一個level // 然后在“第1層”到“第level層”的鏈表中都插入新建節點 int level = randomLevel(); if (level > 0) insertIndex(z, level); return null; } }} |
說明：doPut() 的作用就是將鍵值對添加到“跳表”中。
要想搞清doPut()，首先要弄清楚它的主干部分 —— 我們先單純的只考慮“單線程的情況下，將key-value添加到跳表中”，即忽略“多線程相關的內容”。它的流程如下：
第1步：找到“插入位置”。
即，找到“key的前繼節點(b)”和“key的后繼節點(n)”；key是要插入節點的鍵。
第2步：新建并插入節點。
即，新建節點z(key對應的節點)，并將新節點z插入到“跳表”中(設置“b的后繼節點為z”，“z的后繼節點為n”)。
第3步：更新跳表。
即，隨機獲取一個level，然后在“跳表”的第1層～第level層之間，每一層都插入節點z；在第level層之上就不再插入節點了。若level數值大于“跳表的層次”，則新建一層。
主干部分“對應的精簡后的doPut()的代碼”如下(僅供參考)：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
private V doPut(K kkey, V value, boolean onlyIfAbsent) { Comparable<? super K> key = comparable(kkey); for (;;) { // 找到key的前繼節點 Node<K,V> b = findPredecessor(key); // 設置n為key的后繼節點 Node<K,V> n = b.next; for (;;) { // 新建節點(對應是“要被插入的鍵值對”) Node<K,V> z = new Node<K,V>(kkey, value, n); // 設置“b的后繼節點”為z b.casNext(n, z); // 隨機獲取一個level // 然后在“第1層”到“第level層”的鏈表中都插入新建節點 int level = randomLevel(); if (level > 0) insertIndex(z, level); return null; } }} |
理清主干之后，剩余的工作就相對簡單了。主要是上面幾步的對應算法的具體實現，以及多線程相關情況的處理！
2. 刪除
下面以remove(Object key)為例，對ConcurrentSkipListMap的刪除方法進行說明。
|
1
2
3
|
public V remove(Object key) { return doRemove(key, null);} |
實際上，remove()是通過doRemove()將ConcurrentSkipListMap中的key對應的鍵值對刪除的。
doRemove()的源碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
final V doRemove(Object okey, Object value) { Comparable<? super K> key = comparable(okey); for (;;) { // 找到“key的前繼節點” Node<K,V> b = findPredecessor(key); // 設置n為“b的后繼節點”(即若key存在于“跳表中”，n就是key對應的節點) Node<K,V> n = b.next; for (;;) { if (n == null) return null; // f是“當前節點n的后繼節點” Node<K,V> f = n.next; // 如果兩次讀取到的“b的后繼節點”不同(其它線程操作了該跳表)，則返回到“外層for循環”重新遍歷。 if (n != b.next) // inconsistent read break; // 如果“當前節點n的值”變為null(其它線程操作了該跳表)，則返回到“外層for循環”重新遍歷。 Object v = n.value; if (v == null) { // n is deleted n.helpDelete(b, f); break; } // 如果“前繼節點b”被刪除(其它線程操作了該跳表)，則返回到“外層for循環”重新遍歷。 if (v == n || b.value == null) // b is deleted break; int c = key.compareTo(n.key); if (c < 0) return null; if (c > 0) { b = n; n = f; continue; } // 以下是c=0的情況 if (value != null && !value.equals(v)) return null; // 設置“當前節點n”的值為null if (!n.casValue(v, null)) break; // 設置“b的后繼節點”為f if (!n.appendMarker(f) || !b.casNext(n, f)) findNode(key); // Retry via findNode else { // 清除“跳表”中每一層的key節點 findPredecessor(key); // Clean index // 如果“表頭的右索引為空”，則將“跳表的層次”-1。 if (head.right == null) tryReduceLevel(); } return (V)v; } }} |
說明：doRemove()的作用是刪除跳表中的節點。
和doPut()一樣，我們重點看doRemove()的主干部分，了解主干部分之后，其余部分就非常容易理解了。下面是“單線程的情況下，刪除跳表中鍵值對的步驟”：
第1步：找到“被刪除節點的位置”。
即，找到“key的前繼節點(b)”，“key所對應的節點(n)”，“n的后繼節點f”；key是要刪除節點的鍵。
第2步：刪除節點。
即，將“key所對應的節點n”從跳表中移除 -- 將“b的后繼節點”設為“f”！
第3步：更新跳表。
即，遍歷跳表，刪除每一層的“key節點”(如果存在的話)。如果刪除“key節點”之后，跳表的層次需要-1；則執行相應的操作！
主干部分“對應的精簡后的doRemove()的代碼”如下(僅供參考)：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
final V doRemove(Object okey, Object value) { Comparable<? super K> key = comparable(okey); for (;;) { // 找到“key的前繼節點” Node<K,V> b = findPredecessor(key); // 設置n為“b的后繼節點”(即若key存在于“跳表中”，n就是key對應的節點) Node<K,V> n = b.next; for (;;) { // f是“當前節點n的后繼節點” Node<K,V> f = n.next; // 設置“當前節點n”的值為null n.casValue(v, null); // 設置“b的后繼節點”為f b.casNext(n, f); // 清除“跳表”中每一層的key節點 findPredecessor(key); // 如果“表頭的右索引為空”，則將“跳表的層次”-1。 if (head.right == null) tryReduceLevel(); return (V)v; } }} |
3. 獲取
下面以get(Object key)為例，對ConcurrentSkipListMap的獲取方法進行說明。
|
1
2
3
|
public V get(Object key) { return doGet(key);} |
doGet的源碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
private V doGet(Object okey) { Comparable<? super K> key = comparable(okey); for (;;) { // 找到“key對應的節點” Node<K,V> n = findNode(key); if (n == null) return null; Object v = n.value; if (v != null) return (V)v; }} |
說明：doGet()是通過findNode()找到并返回節點的。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
private Node<K,V> findNode(Comparable<? super K> key) { for (;;) { // 找到key的前繼節點 Node<K,V> b = findPredecessor(key); // 設置n為“b的后繼節點”(即若key存在于“跳表中”，n就是key對應的節點) Node<K,V> n = b.next; for (;;) { // 如果“n為null”，則跳轉中不存在key對應的節點，直接返回null。 if (n == null) return null; Node<K,V> f = n.next; // 如果兩次讀取到的“b的后繼節點”不同(其它線程操作了該跳表)，則返回到“外層for循環”重新遍歷。 if (n != b.next) // inconsistent read break; Object v = n.value; // 如果“當前節點n的值”變為null(其它線程操作了該跳表)，則返回到“外層for循環”重新遍歷。 if (v == null) { // n is deleted n.helpDelete(b, f); break; } if (v == n || b.value == null) // b is deleted break; // 若n是當前節點，則返回n。 int c = key.compareTo(n.key); if (c == 0) return n; // 若“節點n的key”小于“key”，則說明跳表中不存在key對應的節點，返回null if (c < 0) return null; // 若“節點n的key”大于“key”，則更新b和n，繼續查找。 b = n; n = f; } }} |
說明：findNode(key)的作用是在返回跳表中key對應的節點；存在則返回節點，不存在則返回null。
先弄清函數的主干部分，即拋開“多線程相關內容”，單純的考慮單線程情況下，從跳表獲取節點的算法。
第1步：找到“被刪除節點的位置”。
根據findPredecessor()定位key所在的層次以及找到key的前繼節點(b)，然后找到b的后繼節點n。
第2步：根據“key的前繼節點(b)”和“key的前繼節點的后繼節點(n)”來定位“key對應的節點”。
具體是通過比較“n的鍵值”和“key”的大小。如果相等，則n就是所要查找的鍵。
ConcurrentSkipListMap示例
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
import java.util.*;import java.util.concurrent.*;/* * ConcurrentSkipListMap是“線程安全”的哈希表，而TreeMap是非線程安全的。 * * 下面是“多個線程同時操作并且遍歷map”的示例 * (01) 當map是ConcurrentSkipListMap對象時，程序能正常運行。 * (02) 當map是TreeMap對象時，程序會產生ConcurrentModificationException異常。 * * @author skywang */public class ConcurrentSkipListMapDemo1 { // TODO: map是TreeMap對象時，程序會出錯。 //private static Map<String, String> map = new TreeMap<String, String>(); private static Map<String, String> map = new ConcurrentSkipListMap<String, String>(); public static void main(String[] args) { // 同時啟動兩個線程對map進行操作！ new MyThread("a").start(); new MyThread("b").start(); } private static void printAll() { String key, value; Iterator iter = map.entrySet().iterator(); while(iter.hasNext()) { Map.Entry entry = (Map.Entry)iter.next(); key = (String)entry.getKey(); value = (String)entry.getValue(); System.out.print("("+key+", "+value+"), "); } System.out.println(); } private static class MyThread extends Thread { MyThread(String name) { super(name); } @Override public void run() { int i = 0; while (i++ < 6) { // “線程名” + "序號" String val = Thread.currentThread().getName()+i; map.put(val, "0"); // 通過“Iterator”遍歷map。 printAll(); } } }} |
(某一次)運行結果：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
(a1, 0), (a1, 0), (b1, 0), (b1, 0),(a1, 0), (b1, 0), (b2, 0), (a1, 0), (a1, 0), (a2, 0), (a2, 0), (b1, 0), (b1, 0), (b2, 0), (b2, 0), (b3, 0), (b3, 0), (a1, 0), (a2, 0), (a3, 0), (a1, 0), (b1, 0), (a2, 0), (b2, 0), (a3, 0), (b3, 0), (b1, 0), (b4, 0), (b2, 0), (a1, 0), (b3, 0), (a2, 0), (b4, 0), (a3, 0), (a1, 0), (a4, 0), (a2, 0), (b1, 0), (a3, 0), (b2, 0), (a4, 0), (b3, 0), (b1, 0), (b4, 0), (b2, 0), (b5, 0), (b3, 0), (a1, 0), (b4, 0), (a2, 0), (b5, 0), (a3, 0), (a1, 0), (a4, 0), (a2, 0), (a5, 0), (a3, 0), (b1, 0), (a4, 0), (b2, 0), (a5, 0), (b3, 0), (b1, 0), (b4, 0), (b2, 0), (b5, 0), (b3, 0), (b6, 0), (b4, 0), (a1, 0), (b5, 0), (a2, 0), (b6, 0), (a3, 0), (a4, 0), (a5, 0), (a6, 0), (b1, 0), (b2, 0), (b3, 0), (b4, 0), (b5, 0), (b6, 0), |
結果說明：
示例程序中，啟動兩個線程(線程a和線程b)分別對ConcurrentSkipListMap進行操作。以線程a而言，它會先獲取“線程名”+“序號”，然后將該字符串作為key，將“0”作為value，插入到ConcurrentSkipListMap中；接著，遍歷并輸出ConcurrentSkipListMap中的全部元素。 線程b的操作和線程a一樣，只不過線程b的名字和線程a的名字不同。
當map是ConcurrentSkipListMap對象時，程序能正常運行。如果將map改為TreeMap時，程序會產生ConcurrentModificationException異常。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
