/** node是数据节点，内部存放了key和value，node节点能构成有序链表 * Nodes hold keys and values, and are singly linked in sorted * order, possibly with some intervening marker nodes. The list is * headed by a dummy node accessible as head.node. The value field * is declared only as Object because it takes special non-V * values for marker and header nodes. */ staticfinalclassNode<K,V> { final K key; // 注意final修饰 volatile Object value; // 注意volatile修饰，因为cas会操作它 volatile Node<K,V> next;// 注意volatile修饰，因为cas会操作它
/** * Creates a new marker node. A marker is distinguished by * having its value field point to itself. Marker nodes also * have null keys, a fact that is exploited in a few places, * but this doesn't distinguish markers from the base-level * header node (head.node), which also has a null key. */ // 使用Node类型创建marker节点（在删除操作会被使用），和数据节点的区别：无key，且value指向自己。 Node(Node<K,V> next) { this.key = null; this.value = this; this.next = next; }
/** 使用cas更改当前节点value的值 * compareAndSet value field */ booleancasValue(Object cmp, Object val){ return UNSAFE.compareAndSwapObject(this, valueOffset, cmp, val); }
/** 使用cas更改当前节点的next指向 * compareAndSet next field */ booleancasNext(Node<K,V> cmp, Node<K,V> val){ return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val); }
/** * Returns true if this node is a marker. This method isn't * actually called in any current code checking for markers * because callers will have already read value field and need * to use that read (not another done here) and so directly * test if value points to node. * * @return true if this node is a marker node */ //因为HeadIndex的key也null，因此使用value==this才能唯一区别出这是marker节点 booleanisMarker(){ return value == this; }
/** 用于判断node节点是否就是base-level的HeadIndex节点 * Returns true if this node is the header of base-level list. * @return true if this node is header node */ booleanisBaseHeader(){ return value == BASE_HEADER; }
/** 使用cas将一个marker节点放在当前节点的后面,其中f节点是当前节点的后继节点 将： node->f->... 变成： node->marker->f->... * Tries to append a deletion marker to this node. * @param f the assumed current successor of this node * @return true if successful */ booleanappendMarker(Node<K,V> f){ return casNext(f, new Node<K,V>(f)); }
/** 当前节点通过添加marker节点来帮助删除操作或者用于将当前节点脱离前驱节点。 * Helps out a deletion by appending marker or unlinking from * predecessor. This is called during traversals when value * field seen to be null. * @param b predecessor * @param f successor */ // 如果在这里不能理解其含义，可在后面的删除操作中关于(b,n,f)三个节点调整解析中得到回答。 voidhelpDelete(Node<K,V> b, Node<K,V> f){ /* * Rechecking links and then doing only one of the * help-out stages per call tends to minimize CAS * interference among helping threads. */ if (f == next && this == b.next) { if (f == null || f.value != f) // not already marked casNext(f, new Node<K,V>(f)); else b.casNext(this, f.next); } }
/** 返回数据节点key对应的value，如果当前节点value字段指向自己说明是一个mark节点，则返回null，如果当前节点value字段BASE_HEADER，说明是底层的HeadIndex节点也是返回null * Returns value if this node contains a valid key-value pair, * else null. * @return this node's value if it isn't a marker or header or * is deleted, else null */ V getValidValue(){ Object v = value; if (v == this || v == BASE_HEADER) returnnull; @SuppressWarnings("unchecked") V vv = (V)v; return vv; }
/** * Index nodes represent the levels of the skip list. Note that * even though both Nodes and Indexes have forward-pointing * fields, they have different types and are handled in different * ways, that can't nicely be captured by placing field in a * shared abstract class. */ // 可以看到Index索引节点的下一个节点指针不是next字段而是right字段，但他们作用都是指向后继节点，取用不同的名称是为了区别Node的next字段、方便理解和阅读。 staticclassIndex<K,V> { /* 相关指针的局部指向示意图： this → right → indexNode → indexNode → null ↓ down (Index<K,V>类型) ↓ node (最底层的数据节点) */ final Node<K,V> node; //索引节点在垂直方向上指向的最底层的对应数据节点，Node类型 final Index<K,V> down; //注意 down指针是Index索引节点类型，不是数据节点Node类型 volatile Index<K,V> right;//注意 right指针是Index索引节点类型，不是数据节点类型
/** * Creates index node with given values. */ // Index位于索引层的链表，那么它的down字段指向下层的Index节点（或者最底层的node数据节点），right字段指向后继索引节点 Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) { this.node = node; this.down = down; this.right = right; }
/** 使用cas设置Index节点的right节点：在插入操作和删除操作使用 * compareAndSet right field */ finalbooleancasRight(Index<K,V> cmp, Index<K,V> val){ return UNSAFE.compareAndSwapObject(this, rightOffset, cmp, val); }
/** * Returns true if the node this indexes has been deleted. * @return true if indexed node is known to be deleted */ finalbooleanindexesDeletedNode(){ return node.value == null; }
/** 参考后文 * Tries to CAS newSucc as successor. To minimize races with * unlink that may lose this index node, if the node being * indexed is known to be deleted, it doesn't try to link in. * @param succ the expected current successor * @param newSucc the new successor * @return true if successful */ finalbooleanlink(Index<K,V> succ, Index<K,V> newSucc){ Node<K,V> n = node; newSucc.right = succ; return n.value != null && casRight(succ, newSucc); }
/** 参考后文 * Tries to CAS right field to skip over apparent successor * succ. Fails (forcing a retraversal by caller) if this node * is known to be deleted. * @param succ the expected current successor * @return true if successful */ finalbooleanunlink(Index<K,V> succ){ return node.value != null && casRight(succ, succ.right); }
/** * Returns a base-level node with key strictly less than given key, * or the base-level header if there is no such node. Also * unlinks indexes to deleted nodes found along the way. Callers * rely on this side-effect of clearing indices to deleted nodes. * @param key the key * @return a predecessor of key */ private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp){ if (key == null) thrownew NullPointerException(); // don't postpone errors // 两层循环，若当前线程在遍历索引节点过程中，当前遍历节点被修改，说明读不一致，那么当前线程必须回到外层循环重新遍历 for (;;) { /* 注意q、r、d的指向方向，如下所示 q → r → indexNode → indexNode → null ↓ d 先将q指向head节点，那么r和d自然就出来了，如下所示 q(head) → r (q.right) → indexNode → indexNode → null ↓ d(q.down) */ // 这里很关键：q、r、d三个指针都是Index索引节点类型，说明findPredecessor方法只会在索引层去找key的前驱节点，而不会去到最底层的数据节点链表去找。 for (Index<K,V> q = head, r = q.right, d;;) { //①分支：从上面的q、r位置关系可知，q、r都在同一层索引层移动，如果r节点不为空，说明可以继续向右遍历索引链表，若r来到索引链表尾部null位置，那么执行流跳过①分支来到④分支 if (r != null) { //取出索引节点指向的数据节点node，此节点的key将和给定key比较 Node<K,V> n = r.node; K k = n.key; /*② 此分支建议深度理解了doRemove方法后，再回来理解它则简单很多。 在remove方法中有其他写线程使用n.casValue(v, null)将目标删除节点n的value字段设为null，因此只要读线程进入此分支，说明r索引节点指向的数据节点node已经被其他写线程标记为删除状态，此时要将q节点和r节点断开链接，也即将q → r → r.right 变成q → r.right */ if (n.value == null) { if (!q.unlink(r)) break; // 若unlink内部的cas失败，则继续重试 // 如果上面unlink成功，旧r节点断开q节点，此时重新读取q的right节点，然后继续下一轮循环。 r = q.right; // reread r continue; } //③分支：给定的key比r.key大，说明只好向右继续查找：q、r指针同时右边移动一个节点 if (cpr(cmp, key, k) > 0) { q = r; r = r.right; continue; } } /*④分支：findPredecessor结束点：找到了key的前驱节点。注意这里q已经是第一层的目标索引节点，q.down指向null，q.node指向数据节点node，所以不要误解为q.down指向node，而node不为空，参考后面图文解释！ q (索引层leve=1的索引节点) ↓ d (最底层数据节点)，显然此时d是Node节点类型， */ if ((d = q.down) == null) return q.node; //⑤分支：遍历到当前索引层链表尾部r=null也没找到key的前驱节点，那么只能垂直在向下移动，在下一层索引层的链表头部继续重复以上逻辑。务必记住：此“向下移动一层”的操作只在索引层操作，不会“下移到数据链表层”！ q = d; r = d.right; } } }
/** * Tries to CAS right field to skip over apparent successor 若调用此方法时，q恰好被标记为删除状态，那么cas会失败，要求unlink调用者再次循环重试，这就是findPredecessor方法里面的②分支设计为重试的原因。 * succ. Fails (forcing a retraversal by caller) if this node * is known to be deleted. * @param succ the expected current successor * @return true if successful */ finalbooleanunlink(Index<K,V> succ){ // 这里node.value是指q.node.value，不是r.node.value！要求q指向的数据节点node还没被删除才能进行cas return node.value != null && casRight(succ, succ.right); }
findPredecessor方法最关键的一个设计点——返回逻辑：
1 2 3 4 5 6 7
/*④分支：findPredecessor结束点：找到了key的前驱节点 q (索引层leve=1的索引节点) ↓ d (最底层数据节点)，显然此时d是Node节点类型， */ if ((d = q.down) == null) return q.node;
private V doPut(K key, V value, boolean onlyIfAbsent){ Node<K,V> z; // added node if (key == null) thrownew NullPointerException(); Comparator<? super K> cmp = comparator; outer: for (;;) { // 注意：以下内层循环所有逻辑（除了findPredecessor）只发生在最底层的数据链表层中进行遍历 for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) { // 1.1 若不是在数据链表尾部，则可以继续遍历，否则也即来到链表尾部就跳到1.2分支 if (n != null) { Object v; int c; // f暂存n节点之后子链，用于后续遍历 Node<K,V> f = n.next; //1.1.1 单线程情况下，n还是b的next节点，若高并发写情况下，n节点可能被其他线程更改，那么当前线程第一次读取的b.next和现在读取的b.next显然不一致，也即“inconsistent read” if (n != b.next) // inconsistent read break; //1.1.2 n的值为null，说明被其他线程标记位删除状态，只能先去helpDelete，然后再回到内层循环重试。 if ((v = n.value) == null) { // n is deleted n.helpDelete(b, f); break; } //1.1.3 前驱节点b被删除或者n节点value是指向自己（说明n是一个mark节点），前驱节点都被其他线程删除，只能退出本轮回到内层for循环继续重试。 if (b.value == null || v == n) // b is deleted break; //1.1.4 给定的key比n节点还大，那么只能继续向右比较 if ((c = cpr(cmp, key, n.key)) > 0) { // 更新b、n指针向后移动一步 b = n; n = f; continue; } //1.1.5 如果key==n.key,说明已找到该key。 if (c == 0) { if (onlyIfAbsent || n.casValue(v, value)) { @SuppressWarnings("unchecked") V vv = (V)v; return vv; } break; // restart if lost race to replace value } // else c < 0; fall through } /* 1.2 第一种情况：根据1.1 n不为空，那么在 b → n 之间插入 b → z → n 第二种情况：如果1.1 的n节点为空说明来到链表尾部，也即b前驱节点后面就是null，那么b → null 变成b → z → null */ z = new Node<K,V>(key, value, n); //创建key这个插入节点，然后有 z → n // 1.3 if (!b.casNext(n, z)) // cas: 在n节点前、后时刻读一致性时，z节点才能成功CAS插入b前驱节点后面 break; // restart if lost race to append to b若cas失败，只能回到内循环重试 break outer; }
/* 这里随机数的生成考虑很细致：ThreadLocalRandom.nextInt也可以实现线程自己本地随机数，而nextSecondarySeed能做到生成和“当前线程业务代码调用的ThreadLocalRandom.nextInt”不冲突的随机数。 * To produce random values without interference across threads, * we use within-JDK thread local random support (via the * "secondary seed", to avoid interference with user-level * ThreadLocalRandom.) */ int rnd = ThreadLocalRandom.nextSecondarySeed();
返回一个null（如果给定的key不在数据链表里面）或者一个持有key的node（node的value当然是null）,清除沿途遍历到的所有已标记“node.value=null”的数据层节点（注意这里的nodes是数据层链表中的节点，不是指清除索引层节点） Returns node holding key or null if no such, clearing out any deleted nodes seen along the way. 从key的前驱节点b开始遍历base-level的数据层链表（如有必要则需要重复遍历），向右移动过程中遇到标记位删除的节点就处理它 Repeatedly traverses at base-level looking for key starting at predecessor returned from findPredecessor, processing base-level deletions as encountered. 调用者可以使用findNode方法获得额外收益即沿途过程中能清除被标记为删除状态的数据节点。 Some callers rely on this side-effect of clearing deleted nodes.
出现以下三种情况之一，都会使得执行流再次回到b节点重新遍历 Restarts occur, at traversal step centered on node n, （1）考察(b,n,f)三个节点，若n节点已发生改变，不再是b.next执行的原n节点，因此本轮遍历无法处理这种删除操作（cannot unlink），需重试 if: (1) After reading n's next field, n is no longer assumed predecessor b's current successor, which means that we don't have a consistent 3-node snapshot and so cannot unlink any subsequent deleted nodes encountered.
（2）考察(b,n,f)三个节点，若n.value=null，说明n被标记为删除状态，这种情况下，先去n.helpDelete(b, f)删除n节点本身，然后重新遍历 (2) n's value field is null, indicating n is deleted, in which case we help out an ongoing structural deletion before retrying. Even though there are cases where such unlinking doesn't require restart, they aren't sorted out here because doing so would not usually outweigh cost of restarting.
（3）考察(b,n,f)三个节点，若n是marker节点（说明b被标记）或者b.value=null,说明findPredecessor方法返回的是一个被标记删除的数据节点，此时无法正确获得predecessor节点就不能继续执行unlink操作。只能重新回到for循环继续调用findPredecessor，找到新的(b,n,f) (3) n is a marker or n's predecessor's value field is null, indicating (among other possibilities) that findPredecessor returned a deleted node. We can't unlink the node because we don't know its predecessor, so rely on another call to findPredecessor to notice and return some earlier predecessor, which it will do. 第3种check只会在循环的开始才会严格执行检查，但每次迭代都会执行此检查，以帮助调用方避免和其他线程发生竞争，如果调用方cas失败，只能retry。 This check is only strictly needed at beginning of loop, (and the b.value check isn't strictly needed at all) but is done each iteration to help avoid contention with other threads by callers that will fail to be able to change links, and so will retry anyway.
doPut, doRemove, and findNear方法中loop设计都会有以上三种情况的检查逻辑。findFirst、findLast也有类似的检查逻辑 The traversal loops in doPut, doRemove, and findNear all include the same three kinds of checks. And specialized versions appear in findFirst, and findLast and their variants. They can't easily share code because each uses the reads of fields held in locals occurring in the orders they were performed. Params: key – the key Returns: node holding key, or null if no suc
