- 类继承图（针对java8）
ConcurrentSkipListMap的结构：
属性和部分方法如图：
- 先看看类注释
1. part1:
1. `This class implements a tree-like two-dimensionally linked skip`
2. `* list in which the index levels are represented in separate`
3. `* nodes from the base nodes holding data. There are two reasons`
4. `* for taking this approach instead of the usual array-based`
5. `* structure: 1) Array based implementations seem to encounter`
6. `* more complexity and overhead 2) We can use cheaper algorithms`
7. `* for the heavily-traversed index lists than can be used for the`
8. `* base lists. Here's a picture of some of the basics for a`
9. `* possible list with 2 levels of index:`
10. `*`
11. `* Head nodes Index nodes`
12. `* +-+ right +-+ +-+`
13. `* |2|---------------->| |--------------------->| |->null`
14. `* +-+ +-+ +-+`
15. `* | down | |`
16. `* v v v`
17. `* +-+ +-+ +-+ +-+ +-+ +-+`
18. `* |1|----------->| |->| |------>| |----------->| |------>| |->null`
19. `* +-+ +-+ +-+ +-+ +-+ +-+`
20. `* v | | | | |`
21. `* Nodes next v v v v v`
22. `* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+`
23. `* | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null`
24. `* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+`
25. `* The base lists use a variant of the HM linked ordered set`
26. `* algorithm. See Tim Harris, "A pragmatic implementation of`
27. `* non-blocking linked lists"`
28. `* http://www.cl.cam.ac.uk/~tlh20/publications.html and Maged`
29. `* Michael "High Performance Dynamic Lock-Free Hash Tables and`
30. `* List-Based Sets"`
31. `* http://www.research.ibm.com/people/m/michael/pubs.htm. The`
32. `* basic idea in these lists is to mark the "next" pointers of`
33. `* deleted nodes when deleting to avoid conflicts with concurrent`
34. `* insertions, and when traversing to keep track of triples`
35. `* (predecessor, node, successor) in order to detect when and how`
36. `* to unlink these deleted nodes.`
这个类是实现了一个类似于树的二维连接的跳表，它的索引级别是放在分割开的节点里面的，基础节点拥有所有的数据。用这个便利的数据结构代替数组结构的原因主要有两点：
- 以数组为基础的实现看起来会更复杂和低效。
- 我们能够使用更简单的算法应用在频繁变动的索性上，而不是基础的数据列表上。
关于有着二级索引的的列表见图中所示，分为Index节点和基础列表节点，Index节点为索引节点。
基础列表使用HM链表有序算法的一个变种。具体算法讲述参考：http://www.cl.cam.ac.uk/~tlh20/publications.html,高性能无锁的hash表和以列表为基础的集合参考：http://www.research.ibm.com/people/m/michael/pubs.htm 一般用标识要删除节点的next指针的方式来避免删除时的并发插入和决定(predecessor, node, successor)这样的三元组该在什么时候以什么方式取消与已删除节点的联系。
2. part2:
1. `* Rather than using mark-bits to mark list deletions (which can`
2. `* be slow and space-intensive using AtomicMarkedReference), nodes`
3. `* use direct CAS'able next pointers. On deletion, instead of`
4. `* marking a pointer, they splice in another node that can be`
5. `* thought of as standing for a marked pointer (indicating this by`
6. `* using otherwise impossible field values). Using plain nodes`
7. `* acts roughly like "boxed" implementations of marked pointers,`
8. `* but uses new nodes only when nodes are deleted, not for every`
9. `* link. This requires less space and supports faster`
10. `* traversal. Even if marked references were better supported by`
11. `* JVMs, traversal using this technique might still be faster`
12. `* because any search need only read ahead one more node than`
13. `* otherwise required (to check for trailing marker) rather than`
14. `* unmasking mark bits or whatever on each read.`
15. `*`
16. `* This approach maintains the essential property needed in the HM`
17. `* algorithm of changing the next-pointer of a deleted node so`
18. `* that any other CAS of it will fail, but implements the idea by`
19. `* changing the pointer to point to a different node, not by`
20. `* marking it. While it would be possible to further squeeze`
21. `* space by defining marker nodes not to have key/value fields, it`
22. `* isn't worth the extra type-testing overhead. The deletion`
23. `* markers are rarely encountered during traversal and are`
24. `* normally quickly garbage collected. (Note that this technique`
25. `* would not work well in systems without garbage collection.)`
26. `*`
27. `* In addition to using deletion markers, the lists also use`
28. `* nullness of value fields to indicate deletion, in a style`
29. `* similar to typical lazy-deletion schemes. If a node's value is`
30. `* null, then it is considered logically deleted and ignored even`
31. `* though it is still reachable. This maintains proper control of`
32. `* concurrent replace vs delete operations -- an attempted replace`
33. `* must fail if a delete beat it by nulling field, and a delete`
34. `* must return the last non-null value held in the field. (Note:`
35. `* Null, rather than some special marker, is used for value fields`
36. `* here because it just so happens to mesh with the Map API`
37. `* requirement that method get returns null if there is no`
38. `* mapping, which allows nodes to remain concurrently readable`
39. `* even when deleted. Using any other marker value here would be`
40. `* messy at best.)`
节点直接使用cas处理next指针来代替低效地使用AtomicMarkedReference来实现的标识位来进行节点的删除。
3. part3
1. `Here's the sequence of events for a deletion of node n with`
2. `* predecessor b and successor f, initially:`
3. `*`
4. `* +------+ +------+ +------+`
5. `* ... | b |------>| n |----->| f | ...`
6. `* +------+ +------+ +------+`
7. `*`
8. `* 1. CAS n's value field from non-null to null.`
9. `* From this point on, no public operations encountering`
10. `* the node consider this mapping to exist. However, other`
11. `* ongoing insertions and deletions might still modify`
12. `* n's next pointer.`
13. `*`
14. `* 2. CAS n's next pointer to point to a new marker node.`
15. `* From this point on, no other nodes can be appended to n.`
16. `* which avoids deletion errors in CAS-based linked lists.`
17. `*`
18. `* +------+ +------+ +------+ +------+`
19. `* ... | b |------>| n |----->|marker|------>| f | ...`
20. `* +------+ +------+ +------+ +------+`
21. `*`
22. `* 3. CAS b's next pointer over both n and its marker.`
23. `* From this point on, no new traversals will encounter n,`
24. `* and it can eventually be GCed.`
25. `* +------+ +------+`
26. `* ... | b |----------------------------------->| f | ...`
27. `* +------+ +------+`
28. `*`
29. `* A failure at step 1 leads to simple retry due to a lost race`
30. `* with another operation. Steps 2-3 can fail because some other`
31. `* thread noticed during a traversal a node with null value and`
32. `* helped out by marking and/or unlinking. This helping-out`
33. `* ensures that no thread can become stuck waiting for progress of`
34. `* the deleting thread. The use of marker nodes slightly`
35. `* complicates helping-out code because traversals must track`
36. `* consistent reads of up to four nodes (b, n, marker, f), not`
37. `* just (b, n, f), although the next field of a marker is`
38. `* immutable, and once a next field is CAS'ed to point to a`
39. `* marker, it never again changes, so this requires less care.`
40. `*`
41. `* Skip lists add indexing to this scheme, so that the base-level`
42. `* traversals start close to the locations being found, inserted`
43. `* or deleted -- usually base level traversals only traverse a few`
44. `* nodes. This doesn't change the basic algorithm except for the`
45. `* need to make sure base traversals start at predecessors (here,`
46. `* b) that are not (structurally) deleted, otherwise retrying`
47. `* after processing the deletion.`
48. `*`
49. `* Index levels are maintained as lists with volatile next fields,`
50. `* using CAS to link and unlink. Races are allowed in index-list`
51. `* operations that can (rarely) fail to link in a new index node`
52. `* or delete one. (We can't do this of course for data nodes.)`
53. `* However, even when this happens, the index lists remain sorted,`
54. `* so correctly serve as indices. This can impact performance,`
55. `* but since skip lists are probabilistic anyway, the net result`
56. `* is that under contention, the effective "p" value may be lower`
57. `* than its nominal value. And race windows are kept small enough`
58. `* that in practice these failures are rare, even under a lot of`
59. `* contention.`
60. `*`
61. `* The fact that retries (for both base and index lists) are`
62. `* relatively cheap due to indexing allows some minor`
63. `* simplifications of retry logic. Traversal restarts are`
64. `* performed after most "helping-out" CASes. This isn't always`
65. `* strictly necessary, but the implicit backoffs tend to help`
66. `* reduce other downstream failed CAS's enough to outweigh restart`
67. `* cost. This worsens the worst case, but seems to improve even`
68. `* highly contended cases.`
69. `*`
70. `* Unlike most skip-list implementations, index insertion and`
71. `* deletion here require a separate traversal pass occurring after`
72. `* the base-level action, to add or remove index nodes. This adds`
73. `* to single-threaded overhead, but improves contended`
74. `* multithreaded performance by narrowing interference windows,`
75. `* and allows deletion to ensure that all index nodes will be made`
76. `* unreachable upon return from a public remove operation, thus`
77. `* avoiding unwanted garbage retention. This is more important`
78. `* here than in some other data structures because we cannot null`
79. `* out node fields referencing user keys since they might still be`
80. `* read by other ongoing traversals.`
81. `*`
82. `* Indexing uses skip list parameters that maintain good search`
83. `* performance while using sparser-than-usual indices: The`
84. `* hardwired parameters k=1, p=0.5 (see method doPut) mean`
85. `* that about one-quarter of the nodes have indices. Of those that`
86. `* do, half have one level, a quarter have two, and so on (see`
87. `* Pugh's Skip List Cookbook, sec 3.4). The expected total space`
88. `* requirement for a map is slightly less than for the current`
89. `* implementation of java.util.TreeMap.`
90. `*`
91. `* Changing the level of the index (i.e, the height of the`
92. `* tree-like structure) also uses CAS. The head index has initial`
93. `* level/height of one. Creation of an index with height greater`
94. `* than the current level adds a level to the head index by`
95. `* CAS'ing on a new top-most head. To maintain good performance`
96. `* after a lot of removals, deletion methods heuristically try to`
97. `* reduce the height if the topmost levels appear to be empty.`
98. `* This may encounter races in which it possible (but rare) to`
99. `* reduce and "lose" a level just as it is about to contain an`
100. `* index (that will then never be encountered). This does no`
101. `* structural harm, and in practice appears to be a better option`
102. `* than allowing unrestrained growth of levels.`
103. `*`
104. `* The code for all this is more verbose than you'd like. Most`
105. `* operations entail locating an element (or position to insert an`
106. `* element). The code to do this can't be nicely factored out`
107. `* because subsequent uses require a snapshot of predecessor`
108. `* and/or successor and/or value fields which can't be returned`
109. `* all at once, at least not without creating yet another object`
110. `* to hold them -- creating such little objects is an especially`
111. `* bad idea for basic internal search operations because it adds`
112. `* to GC overhead. (This is one of the few times I've wished Java`
113. `* had macros.) Instead, some traversal code is interleaved within`
114. `* insertion and removal operations. The control logic to handle`
115. `* all the retry conditions is sometimes twisty. Most search is`
116. `* broken into 2 parts. findPredecessor() searches index nodes`
117. `* only, returning a base-level predecessor of the key. findNode()`
118. `* finishes out the base-level search. Even with this factoring,`
119. `* there is a fair amount of near-duplication of code to handle`
120. `* variants.`
121. `*`
122. `* To produce random values without interference across threads,`
123. `* we use within-JDK thread local random support (via the`
124. `* "secondary seed", to avoid interference with user-level`
125. `* ThreadLocalRandom.)`
126. `*`
127. `* A previous version of this class wrapped non-comparable keys`
128. `* with their comparators to emulate Comparables when using`
129. `* comparators vs Comparables. However, JVMs now appear to better`
130. `* handle infusing comparator-vs-comparable choice into search`
131. `* loops. Static method cpr(comparator, x, y) is used for all`
132. `* comparisons, which works well as long as the comparator`
133. `* argument is set up outside of loops (thus sometimes passed as`
134. `* an argument to internal methods) to avoid field re-reads.`
135. `*`
136. `* For explanation of algorithms sharing at least a couple of`
137. `* features with this one, see Mikhail Fomitchev's thesis`
138. `* (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis`
139. `* (http://www.cl.cam.ac.uk/users/kaf24/), and Hakan Sundell's`
140. `* thesis (http://www.cs.chalmers.se/~phs/).`
141. `*`
142. `* Given the use of tree-like index nodes, you might wonder why`
143. `* this doesn't use some kind of search tree instead, which would`
144. `* support somewhat faster search operations. The reason is that`
145. `* there are no known efficient lock-free insertion and deletion`
146. `* algorithms for search trees. The immutability of the "down"`
147. `* links of index nodes (as opposed to mutable "left" fields in`
148. `* true trees) makes this tractable using only CAS operations.`
149. `*`
150. `* Notation guide for local variables`
151. `* Node: b, n, f for predecessor, node, successor`
152. `* Index: q, r, d for index node, right, down.`
153. `* t for another index node`
154. `* Head: h`
155. `* Levels: j`
156. `* Keys: k, key`
157. `* Values: v, value`
158. `* Comparisons: c`
一个b->n->f的列表，在删除节点n时需要经历如下几步:
- 使用CAS将n的值从非null设置为null。从这一点上面，如果设置不成功则证明有其它对n的操作存在。并且其它的插入和删除操作也会修改n的next指针;
- 使用CAS将n的next指针指向一个新的marker节点，这时候没有其他的节点能够添加到n的后面，这就避免了删除失败的问题；
- 使用CAS设置b的next指针从n和它的marker指向f，这样就越过了n直接指向f，n节点最终会被gc回收。
- CAS的具体操作....
其中的属性：
- 节点（Node）:b,n,f代表的是前置节点，当前节点，后续节点
- Index:q,r,d代表的是索引当前节点，右节点和下面的节点; t表示其它索引节点
- Head:h 表示头结点
- Levels: j 表示层级
- 源码
1. Node结构如图：
Node是单向的链表结构。
一个节点的属性有key值和value值，节点之间是有序连接的，头节点和一些marker节点有些不一样，因为它们经常被赋予特殊值。next用来指向下一个节点。
1. `/**`
2. `* Creates a new regular node. 创建普通节点`
3. `*/`
4. `Node(K key, Object value, Node<K,V> next) {`
5. `this.key = key;`
6. `this.value = value;`
7. `this.next = next;`
8. `}`
9.
10. `/**`
11. `创建marker节点`
12. `* Creates a new marker node. A marker is distinguished by`
13. `* having its value field point to itself. Marker nodes also`
14. `* have null keys, a fact that is exploited in a few places,`
15. `* but this doesn't distinguish markers from the base-level`
16. `* header node (head.node), which also has a null key.`
17. `*/`
18. `Node(Node<K,V> next) {`
19. `this.key = null;`
20. `this.value = this;`
21. `this.next = next;`
22. `}`
marker节点在删除元素时被使用
2. Index与HeadIndex结构如下图：
1. `/**`
2. `* Creates index node with given values.`
3. `*/`
4. `Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {`
5. `this.node = node;//当前节点`
6. `this.down = down;//下节点`
7. `this.right = right;//右节点`
8. `}`
9.
10. `/**`
11. `* compareAndSet right field`
12. `*/`
13. `final boolean casRight(Index<K,V> cmp, Index<K,V> val) {`
14. `return UNSAFE.compareAndSwapObject(this, rightOffset, cmp, val);`
15. `}`
16.
17. `/**`
18. `* Returns true if the node this indexes has been deleted.`
19. `* @return true if indexed node is known to be deleted`
20. `*/`
21. `final boolean indexesDeletedNode() {`
22. `return node.value == null;`
23. `}`
24.
25. `/**`
26. `* Tries to CAS newSucc as successor. To minimize races with`
27. `* unlink that may lose this index node, if the node being`
28. `* indexed is known to be deleted, it doesn't try to link in.`
29. `* @param succ the expected current successor`
30. `* @param newSucc the new successor`
31. `* @return true if successful`
32. `*/`
33. `final boolean link(Index<K,V> succ, Index<K,V> newSucc) {`
34. `Node<K,V> n = node;`
35. `//将新的后继节点的右节点设置为当前的后继节点`
36. `newSucc.right = succ;`
37. `//CAS设置当前的后继节点`
38. `return n.value != null && casRight(succ, newSucc);`
39. `}`
40.
41. `/**`
42. `* Tries to CAS right field to skip over apparent successor`
43. `* succ. Fails (forcing a retraversal by caller) if this node`
44. `* is known to be deleted.`
45. `* @param succ the expected current successor`
46. `* @return true if successful`
47. `*/`
48. `final boolean unlink(Index<K,V> succ) {`
49. `//CAS设置当前后继节点的右节点为当前的后继节点`
50. `return node.value != null && casRight(succ, succ.right);`
51. `}`
HeadIndex:
1. `final int level;`
2. `HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {`
3. `super(node, down, right);`
4. `this.level = level;`
5. `}`
在Index的基础上添加了一个表示节点层级的level。
3. ConcurrentSkipListMap:
最终图如下（懒得画，来源于网络）：
1. `public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>`
2. `implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable {`
3. `// 版本序列号`
4. `private static final long serialVersionUID = -8627078645895051609L;`
5. `// 基础层的头结点`
6. `private static final Object BASE_HEADER = new Object();`
7. `// 最顶层头结点的索引`
8. `private transient volatile HeadIndex<K,V> head;`
9. `// 比较器`
10. `final Comparator<? super K> comparator;`
11. `// 键集合`
12. `private transient KeySet<K> keySet;`
13. `// entry集合`
14. `private transient EntrySet<K,V> entrySet;`
15. `// 值集合`
16. `private transient Values<V> values;`
17. `// 降序键集合`
18. `private transient ConcurrentNavigableMap<K,V> descendingMap;`
19.
20. `// Unsafe mechanics`
21. `private static final sun.misc.Unsafe UNSAFE;`
22. `// head域的偏移量`
23. `private static final long headOffset;`
24. `// Thread类的threadLocalRandomSecondarySeed的偏移量`
25. `private static final long SECONDARY;`
26. `static {`
27. `try {`
28. `UNSAFE = sun.misc.Unsafe.getUnsafe();`
29. `Class<?> k = ConcurrentSkipListMap.class;`
30. `headOffset = UNSAFE.objectFieldOffset`
31. `(k.getDeclaredField("head"));`
32. `Class<?> tk = Thread.class;`
33. `SECONDARY = UNSAFE.objectFieldOffset`
34. `(tk.getDeclaredField("threadLocalRandomSecondarySeed"));`
35.
36. `} catch (Exception e) {`
37. `throw new Error(e);`
38. `}`
39. `}`
40. `}`
1. 查找方法:
1. `带标签break参考：https://blog.csdn.net/qwelkjzxc369/article/details/60479633`
2. `/**`
3. `* Gets value for key. Almost the same as findNode, but returns`
4. `* the found value (to avoid retries during re-reads)`
5. `*`
6. `* @param key the key`
7. `* @return the value, or null if absent`
8. `*/`
9. `private V doGet(Object key) {`
10. `if (key == null)`
11. `throw new NullPointerException();`
12. `Comparator<? super K> cmp = comparator;`
13. `outer: for (;;) {`
14. `for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {`
15. `Object v; int c;`
16. `if (n == null)`
17. `break outer;回到了标签位置，不重新进入外循环迭带，直接返回null`
18. `Node<K,V> f = n.next;`
19. `if (n != b.next) // inconsistent read 读不一致，有其他线程在操作`
20. `break;//重试 进入外循环迭带`
21. `if ((v = n.value) == null) { // n is deleted ，n已经被删除了`
22. `n.helpDelete(b, f);`
23. `break;//重试 进入外循环迭带`
24. `}`
25. `if (b.value == null || v == n) // b is deleted ，b被删除了`
26. `break;//重试 进入外循环迭带`
27. `if ((c = cpr(cmp, key, n.key)) == 0) {`
28. `@SuppressWarnings("unchecked") V vv = (V)v;`
29. `return vv;`
30. `}`
31. `if (c < 0)`
32. `break outer;回到了标签位置，不重新进入外循环迭带，直接返回null`
33. `b = n;`
34. `n = f;`
35. `}`
36. `}`
37. `return null;`
38. `}`
39.
40.
41. `/**`
42. `* Returns a base-level node with key strictly less than given key,`
43. `* or the base-level header if there is no such node. Also`
44. `* unlinks indexes to deleted nodes found along the way. Callers`
45. `* rely on this side-effect of clearing indices to deleted nodes.`
46. `* @param key the key`
47. `* @return a predecessor of key`
48. `*/`
49. `private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {`
50. `if (key == null)`
51. `throw new NullPointerException(); // don't postpone errors`
52. `for (;;) {`
53. `for (Index<K,V> q = head, r = q.right, d;;) {//从顶层索引开始查找`
54. `if (r != null) {`
55. `Node<K,V> n = r.node;`
56. `K k = n.key;`
57. `if (n.value == null) {//数据节点的值为null表示该数据标记为已删除`
58. `if (!q.unlink(r))//断开连接，如果断开连接失败，代表有其他线程在操作，则跳到外层循环重试`
59. `break; // restart 重试`
60. `r = q.right; // reread r 如果已经断开连接，则重新加载右节点`
61. `continue;`
62. `}`
63. `if (cpr(cmp, key, k) > 0) {//给定key大于当前key，继续往右查找`
64. `q = r;`
65. `r = r.right;`
66. `continue;`
67. `}`
68. `}`
69. `//两种情况：1.当前级别查找结束，未找到；2.给定key小于等于当前key，需要在下一级别中查找`
70. `if ((d = q.down) == null)//没有更低级别,直接返回`
71. `return q.node;`
72. `//有更低级别，在更低级别中继续查找`
73. `q = d;`
74. `r = d.right;`
75. `}`
76. `}`
77. `}`
主要分为以下几步：
- 找到要查找的key的前继节点b，然后找到b的后继节点n。
- 根据key的前继节点(b)和key的前继节点的后继节点(n),通过n的键值和key的大小来定位key对应的节点。
2. 插入:
1. `/**`
2. `* Main insertion method. Adds element if not present, or`
3. `* replaces value if present and onlyIfAbsent is false.`
4. `* @param key the key`
5. `* @param value the value that must be associated with key`
6. `* @param onlyIfAbsent if should not insert if already present`
7. `* @return the old value, or null if newly inserted`
8. `*/`
9. `private V doPut(K key, V value, boolean onlyIfAbsent) {`
10. `Node<K,V> z; // added node`
11. `if (key == null)`
12. `throw new NullPointerException();`
13. `Comparator<? super K> cmp = comparator;`
14. `outer: for (;;) {`
15. `// 找到“key的前继节点”，从前继节点开始遍历,设置n为“b的后继节点”(即若key存在于“跳表中”，n就是key对应的节点)`
16. `for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {//b为指定key的前驱节点，n为该前驱节点的下一个节点`
17. `if (n != null) {`
18. `Object v; int c;`
19. `// 设置n为“key的前继节点的后继节点”，即n应该是“插入节点”的“后继节点”`
20. `Node<K,V> f = n.next;`
21. `// 如果两次获得的b.next不是相同的Node，就跳转到”外层for循环“，重新获得b和n后再遍历。`
22. `if (n != b.next) // inconsistent read`
23. `break;//读取不一致，重试`
24. `// 当n的值为null(意味着其它线程删除了n)；此时删除b的下一个节点，然后跳转到”外层for循环“，重新获得b和n后再遍历。`
25. `if ((v = n.value) == null) { // n is deleted`
26. `n.helpDelete(b, f);//数据节点的值为null,表示该数据节点标记为已删除，移除该数据节点并重试。`
27. `break;`
28. `}`
29. `// 如果其它线程删除了b；则跳转到”外层for循环“，重新获得b和n后再遍历。`
30. `if (b.value == null || v == n) // b is deleted`
31. `break;//重试`
32. `if ((c = cpr(cmp, key, n.key)) > 0) {//给定key大于当前可以，继续寻找合适的插入点`
33. `b = n;`
34. `n = f;`
35. `continue;`
36. `}`
37. `if (c == 0) {//找到插入点`
38. `if (onlyIfAbsent || n.casValue(v, value)) {`
39. `@SuppressWarnings("unchecked") V vv = (V)v;`
40. `return vv;`
41. `}`
42. `break; // restart if lost race to replace value`
43. `}`
44. `// else c < 0; fall through`
45. `}`
46. `//没有找到，新建数据节点`
47. `z = new Node<K,V>(key, value, n);`
48. `if (!b.casNext(n, z))`
49. `break; // restart if lost race to append to b`
50. `break outer;`
51. `}`
52. `}`
53.
54. `int rnd = ThreadLocalRandom.nextSecondarySeed();//生成随机数`
55. `if ((rnd & 0x80000001) == 0) { // test highest and lowest bits //如果生成的随机数是低位则新建上层索引`
56. `int level = 1, max;`
57. `//直到变成偶数才中止循环，相当于随机获取一层level`
58. `while (((rnd >>>= 1) & 1) != 0)//移位操作并与1取&来判断奇偶，相当于%操作，如果为奇数则对level加1。获取跳表层级`
59. `++level;`
60. `//需要构建的节点`
61. `Index<K,V> idx = null;`
62. `//头节点`
63. `HeadIndex<K,V> h = head;`
64. `//如果获取到的层级小于最大层级`
65. `if (level <= (max = h.level)) {//如果获取的链表层级小于等于当前最大层级，则直接添加，并将它们组成一个上下的链表`
66. `//从第一屋到第level层的链表中都插入新建节点`
67. `for (int i = 1; i <= level; ++i)`
68. `idx = new Index<K,V>(z, idx, null);`
69. `}`
70. `else { // try to grow by one level 否则增加一层level，在这里体现为Index<K,V>数组`
71. `level = max + 1; // hold in array and later pick the one to use`
72. `//新建一层级的Index数组`
73. `@SuppressWarnings("unchecked")Index<K,V>[] idxs =`
74. `(Index<K,V>[])new Index<?,?>[level+1];`
75. `for (int i = 1; i <= level; ++i)`
76. `idxs[i] = idx = new Index<K,V>(z, idx, null);//数组里面放的是这一层的所有Index<K,V>`
77. `for (;;) {`
78. `h = head;`
79. `int oldLevel = h.level;`
80. `if (level <= oldLevel) // lost race to add level`
81. `break;`
82. `HeadIndex<K,V> newh = h;//更新head`
83. `Node<K,V> oldbase = h.node;`
84. `for (int j = oldLevel+1; j <= level; ++j)//新添加的level层的数据`
85. `newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);`
86. `if (casHead(h, newh)) {`
87. `h = newh;`
88. `idx = idxs[level = oldLevel];`
89. `break;`
90. `}`
91. `}`
92. `}`
93. `// find insertion points and splice in //逐层插入数据`
94. `splice: for (int insertionLevel = level;;) {`
95. `int j = h.level;`
96. `//遍历h=>HeadIndex对应的链表，从左向右遍历`
97. `for (Index<K,V> q = h, r = q.right, t = idx;;) {`
98. `if (q == null || t == null)`
99. `break splice;`
100. `if (r != null) {`
101. `Node<K,V> n = r.node;`
102. `// compare before deletion check avoids needing recheck`
103. `//比较n的值与key是否相同`
104. `int c = cpr(cmp, key, n.key);`
105. `if (n.value == null) {//如果n的值为null`
106. `if (!q.unlink(r))//试着与右节点unlink，如果失败（有其他线程操作）则重试`
107. `break;`
108. `r = q.right;//如果上面n的值为null，则让r指向q的下一个右节点`
109. `continue;`
110. `}`
111. `if (c > 0) {`
112. `q = r;`
113. `r = r.right;`
114. `continue;`
115. `}`
116. `}`
117.
118. `if (j == insertionLevel) {//j表示层级位于要插入层`
119. `if (!q.link(r, t))//如果有其他线程在操作则重试`
120. `break; // restart`
121. `if (t.node.value == null) {`
122. `findNode(key);`
123. `break splice;`
124. `}`
125. `if (--insertionLevel == 0)`
126. `break splice;`
127. `}`
128.
129. `if (--j >= insertionLevel && j < level)`
130. `t = t.down;`
131. `q = q.down;`
132. `r = q.right;`
133. `}`
134. `}`
135. `}`
136. `return null;`
137. `}`
主要有以下几步：
- 找到插入位置,找到“key的前继节点(b)”和“key的后继节点(n)”；key是要插入节点的键。
- 新建并插入节点，新建节点z(key对应的节点)，并将新节点z插入到“跳表”中(设置“b的后继节点为z”，“z的后继节点为n”)。
- 更新跳表，随机获取一个level，然后在“跳表”的第1层～第level层之间，每一层都插入节点z；在第level层之上就不再插入节点了。若level数值大于“跳表的层次”，则新建一层。
3. 删除
1. `/* ---------------- Deletion -------------- */`
2.
3. `/**`
4. `* Main deletion method. Locates node, nulls value, appends a`
5. `* deletion marker, unlinks predecessor, removes associated index`
6. `* nodes, and possibly reduces head index level.`
7. `*`
8. `* Index nodes are cleared out simply by calling findPredecessor.`
9. `* which unlinks indexes to deleted nodes found along path to key,`
10. `* which will include the indexes to this node. This is done`
11. `* unconditionally. We can't check beforehand whether there are`
12. `* index nodes because it might be the case that some or all`
13. `* indexes hadn't been inserted yet for this node during initial`
14. `* search for it, and we'd like to ensure lack of garbage`
15. `* retention, so must call to be sure.`
16. `*`
17. `* @param key the key`
18. `* @param value if non-null, the value that must be`
19. `* associated with key`
20. `* @return the node, or null if not found`
21. `*/`
22. `final V doRemove(Object key, Object value) {`
23. `if (key == null)`
24. `throw new NullPointerException();`
25. `Comparator<? super K> cmp = comparator;`
26. `outer: for (;;) {`
27. `// 找到“key的前继节点”，从前继节点开始遍历,设置n为“b的后继节点”(即若key存在于“跳表中”，n就是key对应的节点)`
28. `for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {`
29. `Object v; int c;`
30. `if (n == null)`
31. `break outer;`
32. `// f是“当前节点n的后继节点”`
33. `Node<K,V> f = n.next;`
34. `// 如果两次读取到的“b的后继节点”不同(其它线程操作了该跳表)，则返回到外层循环重新遍历。`
35. `if (n != b.next) // inconsistent read`
36. `break;`
37. `// 如果“当前节点n的值”变为null(其它线程操作了该跳表)，则返回到外层循环重新遍历。`
38. `if ((v = n.value) == null) { // n is deleted`
39. `n.helpDelete(b, f);`
40. `break;`
41. `}`
42. `//如果“后继节点b”被删除(其它线程操作了该跳表)，则返回到外层for循环重新遍历`
43. `if (b.value == null || v == n) // b is deleted`
44. `break;`
45. `if ((c = cpr(cmp, key, n.key)) < 0)`
46. `break outer;`
47. `if (c > 0) {`
48. `b = n;`
49. `n = f;`
50. `continue;`
51. `}`
52. `if (value != null && !value.equals(v))`
53. `break outer;`
54. `if (!n.casValue(v, null))`
55. `break;`
56. `//尝试着将n指向marker节点,marker节点指向f节点,将b与f建立link,n节点会被gc`
57. `if (!n.appendMarker(f) || !b.casNext(n, f))`
58. `//如果上面的尝试失败，则通过findNode进行重试`
59. `findNode(key); // retry via findNode`
60. `else {`
61. `findPredecessor(key, cmp); // clean index`
62. `if (head.right == null)`
63. `//如果头节点的右节点的null，则删除一个层级`
64. `tryReduceLevel();`
65. `}`
66. `@SuppressWarnings("unchecked") V vv = (V)v;`
67. `return vv;`
68. `}`
69. `}`
70. `return null;`
71. `}`
主要步骤为：
- 找到“key的前继节点(b)”，“key所对应的节点(n)”，“n的后继节点f”,找到被删除节点的位置。
- 找到key所对应的节点n，并将n从跳表中移除，将b指向f,n会被gc。
- 遍历跳表，如果存在的则删除每一层的“key节点”。如果删除“key节点”之后，跳表的层次需要-1。