JDK源码中的跳表实现类： ConcurrentSkipListMap和ConcurrentSkipListSet。其中ConcurrentSkipListSet的实现是基于ConcurrentSkipListMap。因此下面具体分析ConcurrentSkipListMap的实现：
//查找指定Key的前置节点
private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
if (key == null)
throw new NullPointerException(); // don't postpone errors
for (;;) {
for (Index<K,V> q = head, r = q.right, d;;) {
if (r != null) {
Node<K,V> n = r.node;
K k = n.key;
if (n.value == null) {
if (!q.unlink(r)) // 如果节点r=q.right为空，则删除该节点r，即把节点q.right指向r.right.
break; // restart 然后跳出本次循环，从头节点开始继续循环。
r = q.right; // reread r
continue;
}
if (cpr(cmp, key, k) > 0) {// 通过Key值于当前节点的right节点比较，如果Key值较大，则继续往右比较
q = r;
r = r.right;
continue;
}
}
if ((d = q.down) == null) // 如果当前节点的down为空，则当前链表为最底层链表，该节点的值<=key，此即为查询结果。
return q.node;
q = d; // 如果Key值不比当前节点的right节点大，则继续往下比较
r = d.right;
}
}
}
// 根据Key查找对应的节点
private Node<K,V> findNode(Object key) {
if (key == null)
throw new NullPointerException(); // don't postpone errors
Comparator<? super K> cmp = comparator;
outer: for (;;) {
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {//从key的前置节点开始查找
Object v; int c;
if (n == null)
break outer;
Node<K,V> f = n.next;
if (n != b.next) // inconsistent read 读写不一致，重新开始查找
break;
if ((v = n.value) == null) { // n is deleted 下一个节点为null,则删除该节点，重新开始查找
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) // b is deleted
break;
if ((c = cpr(cmp, key, n.key)) == 0) //查找到，则返回结果
return n;
if (c < 0)
break outer;
b = n;
n = f;
}
}
return null;
}
private V doGet(Object key) 方法的实现于findNode一致，只是返回值为Value的复制。
/**
*
* Main insertion method. Adds element if not present, or
* replaces value if present and onlyIfAbsent is false.
* @param key the key
* @param value the value that must be associated with key
* @param onlyIfAbsent if should not insert if already present
* @return the old value, or null if newly inserted
* 新增一个节点过程：
* 1，根据新增的节点key值，寻找其合适的插入位置b;
* 2，如果存在相等的key值，则根据onlyIfAbsent决定是否更新对应的Value值，然后返回;
* 3，如果不存在相等的key值，则创建一个新的节点，并插入到合适的位置b，此时操作的是跳表的最底层;
* 4，根据随机函数，决定是否添加上层节点，如果不需要添加，则直接返回null;
* 5，如果需要添加上层节点，则获取随机值level；
* 6，如果随机值level不大于当前最大层数，则创建一个从第一层到第level层的新的节点Index链表，其通过down指针连接，right指针都设置为null；
* 7，如果随机值level大于当前最大层数，则跳表的最大层数加1，然后创建一个从第一层到新的最大层的新的节点Index链表，其通过down指针连接，right指针都设置
* 为null；然后从旧的最大层数+1到新的最大层数间新增head节点链表，其通过down指针连接，right指针指向刚新增的对应层的Index节点；
* 8，从旧的最大层数开始往最底层，把新增的index节点插入到合适的位置，即更新其right指针(完善第6步的操作)。至此，完成新增节点的整个过程。
*/
private V doPut(K key, V value, boolean onlyIfAbsent) {
Node<K,V> z; // added node
if (key == null)
throw new NullPointerException();
Comparator<? super K> cmp = comparator;
outer: for (;;) {
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {// 根据Key找到前置节点，然后开始查找
if (n != null) {
Object v; int c;
Node<K,V> f = n.next;
if (n != b.next) // inconsistent read
break;
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) // b is deleted
break;
if ((c = cpr(cmp, key, n.key)) > 0) { //继续往右查找
b = n;
n = f;
continue;
}
if (c == 0) {
if (onlyIfAbsent || n.casValue(v, value)) {//如果存在key相等的节点，则如果onlyIfAbsent=false，则通过casValue更新Key对应的Value值。如果onlyIfAbsent=true，则不更新Key对应的Value值，然后返回oldValue。
@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
break; // restart if lost race to replace value
}
// else c < 0; fall through
}
z = new Node<K,V>(key, value, n); // 没有查找到对应的Key节点，则新增一个节点
if (!b.casNext(n, z)) // 把新增的节点z设为当前节点的next节点；原子操作，失败则不断的循环操作
break; // restart if lost race to append to b
break outer;
}
}
int rnd = ThreadLocalRandom.nextSecondarySeed();
if ((rnd & 0x80000001) == 0) { // test highest and lowest bits
//8000000001 = 1000 0000 0000 0000 0000 0000 0000 0001 测试最高位和最低位是否为0
int level = 1, max;
while (((rnd >>>= 1) & 1) != 0) //无符号右移1位， 随机获得level值
++level;
Index<K,V> idx = null;
HeadIndex<K,V> h = head;
if (level <= (max = h.level)) {
for (int i = 1; i <= level; ++i)
idx = new Index<K,V>(z, idx, null);
}
else { // try to grow by one level 使整个跳表的level增长1
level = max + 1; // hold in array and later pick the one to use
@SuppressWarnings("unchecked")Index<K,V>[] idxs =
(Index<K,V>[])new Index<?,?>[level+1];
for (int i = 1; i <= level; ++i)
idxs[i] = idx = new Index<K,V>(z, idx, null);
//idx = new Index<K,V>(z,idx,null); 设置idx值，并设置其down和right值
//idxs[i] = idx; 设置每一层中新增的Index节点，其right值都设为null,down值设置为其下一层的Index节点。
for (;;) {
h = head;
int oldLevel = h.level;
if (level <= oldLevel) // lost race to add level
break;
HeadIndex<K,V> newh = h;
Node<K,V> oldbase = h.node;
for (int j = oldLevel+1; j <= level; ++j) //设置新增的Head节点，设置其node,down,right和level值
newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
if (casHead(h, newh)) { //更新head值成功，则退出无限循环
h = newh; //h 为新的跳表的head节点
idx = idxs[level = oldLevel]; //新增的层中，包含Head和idxs[max]两个节点，其指向关系已经确定，而oldLevel中，还没有设置idxs[level]的前置节点，因此idx = idxs[level = oldLevel],说明需要从此层开始至最底层，设置好idxs[level]的前置节点，下面的代码splice完成该功能。
break;
}
}
}
// find insertion points and splice in
splice: for (int insertionLevel = level;;) {
int j = h.level;
for (Index<K,V> q = h, r = q.right, t = idx;;) {
if (q == null || t == null)
break splice;
if (r != null) {
Node<K,V> n = r.node;
// compare before deletion check avoids needing recheck
int c = cpr(cmp, key, n.key);//key 根当前node.key比较
if (n.value == null) {
if (!q.unlink(r))
break;
r = q.right;
continue;
}
if (c > 0) { //继续往右查找
q = r;
r = r.right;
continue;
}
}
if (j == insertionLevel) {
if (!q.link(r, t)) // 把节点t插入到q和r之间，t即新增的节点idx[level]
break; // restart
if (t.node.value == null) {
findNode(key);
break splice;
}
if (--insertionLevel == 0)//层数往下，如果已到最底层，则退出，最底层的节点值在之前的代码中已经完成插入。
break splice;
}
if (--j >= insertionLevel && j < level)
t = t.down; //t值更新，t即新增的节点idx[level]
q = q.down;
r = q.right;
}
}
}
return null;
}
/**
* Main deletion method. Locates node, nulls value, appends a
* deletion marker, unlinks predecessor, removes associated index
* nodes, and possibly reduces head index level.
*
* Index nodes are cleared out simply by calling findPredecessor.
* which unlinks indexes to deleted nodes found along path to key,
* which will include the indexes to this node. This is done
* unconditionally. We can't check beforehand whether there are
* index nodes because it might be the case that some or all
* indexes hadn't been inserted yet for this node during initial
* search for it, and we'd like to ensure lack of garbage
* retention, so must call to be sure.
*
* @param key the key
* @param value if non-null, the value that must be
* associated with key
* @return the node, or null if not found
*/
final V doRemove(Object key, Object value) {
if (key == null)
throw new NullPointerException();
Comparator<? super K> cmp = comparator;
outer: for (;;) {
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
Object v; int c;
if (n == null)
break outer;
Node<K,V> f = n.next;
if (n != b.next) // inconsistent read
break;
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) // b is deleted
break;
if ((c = cpr(cmp, key, n.key)) < 0)
break outer;
if (c > 0) {
b = n;
n = f;
continue;
}
if (value != null && !value.equals(v)) //如果value不相等，退出
break outer;
if (!n.casValue(v, null)) //无限循环，直至设置节点的值为null成功,
break;
//之前已经把当前节点值设为null,之后的删除操作分两步：1，在n和n.next间插入一个删除标记节点
//marker； 2，设置b.next为f；这是由两个原子操作共同完成，如果都正常完成，则直接返回；如果有其中一步失败，
//则调用findNode(key)来继续完成删除null节点的操作；
if (!n.appendMarker(f) || !b.casNext(n, f))
findNode(key); // retry via findNode
else { .
findPredecessor(key, cmp); // clean index
if (head.right == null)
tryReduceLevel(); //最上面三层都无索引节点，则把最上面一层的索引删除。
}
@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
}
return null;
}
/**
* 添加一个删除标记节点，设置当前节点的next节点为new Node(f),该新增节点的value值为当前节点f.value=f;
* Tries to append a deletion marker to this node.
* @param f the assumed current successor of this node
* @return true if successful
*/
boolean appendMarker(Node<K,V> f) {
return casNext(f, new Node<K,V>(f));
}
Node(Node<K,V> next) {
this.key = null;
this.value = this;
this.next = next;
}
/**
* compareAndSet next field
*/
boolean casNext(Node<K,V> cmp, Node<K,V> val) {
return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
}
/**
* 继续完成删除节点过程：
* 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
*/
void helpDelete(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 判断是否为marker节点(f.value=f)
casNext(f, new Node<K,V>(f));
else
b.casNext(this, f.next);
}
}
删除步骤：
1， 删除前，需要删除节点n：
2，删除时，先设置n.value= null; 无限循环，直至成功为止；
3，添加删除标记节点marker：
marker 节点的key=null, value=f, next=f;
4，删除该节点n以及标记节点marker:
其中步骤2，3，4分别由3个CAS原子操作完成。步骤2保证成功，步骤3或者4只要有一个失败，此时的n.value = null, 因此都可以由节点遍历的操作来继续推进删除过程。
为什么删除操作要分为3步，而不是由一个步骤(步骤4)来完成？因为CAS操作只能保证一个变量操作的原子性。
相关推荐
jdk6 源码jdk6 源码jdk6 源码jdk6 源码jdk6 源码jdk6 源码
总的来说，深入研究JDK 8u60的源码不仅能够提升我们的Java编程技能，还能让我们掌握更多的底层知识，比如JVM的工作原理、类加载机制、新的语言特性实现等。对于任何希望提升技术水平的Java开发者来说，这都是一次...
4. **多线程**：JDK 1.6支持多线程编程，源码中包括了`Thread`类和`synchronized`关键字的实现，以及线程同步机制如`wait()`, `notify()`, `notifyAll()`。 5. **I/O流**：在`java.io`包中，你可以看到文件读写、...
这份"JDK8完整源码包"包含了JavaFX、Sun私有实现等核心组件的源代码，为深入理解Java平台的工作原理提供了宝贵的资源。 首先，JavaFX是Java的图形用户界面（GUI）库，自JDK 8起成为标准部分，它提供了丰富的UI组件...
下载后直接去本机jdk目录里替换jdk中的src.zip 再打开idea就能看到中文版的源码注释 示例 https://blog.csdn.net/a7459/article/details/106495622
9. **多线程编程**：JDK11中的`java.util.concurrent`包提供了丰富的并发工具类，源码中可以看到这些类的实现细节，有助于理解并发原理。 10. **类加载机制**：JDK11的类加载机制仍然遵循“双亲委派模型”，源码中...
这个"jdk8源码包"就是用于查看和学习JDK8内部实现细节的重要资源。 首先，JDK8引入了Lambda表达式，这是一种简洁的函数式编程语法，使得处理集合和事件流变得更加简单。Lambda可以作为参数传递，也可以作为方法...
Java Development Kit (JDK) 源码是学习和理解Java平台核心机制的关键资源。它包含了许多关键组件的源代码，使开发者能够深入探索Java语言的底层实现，从而提升编程技巧，优化性能，并理解标准库的工作原理。在这个...
OpenJDK是JDK的一个开源实现，由全球开发者社区共同维护，其源码公开使得开发者能够深入理解Java平台的工作原理。 1. **Java核心库** - **javax**: 这个包主要包含Java扩展功能，如JavaBeans组件、JSP（JavaServer...
想看随时查看jdk源码的，访问官网不方便的，只需导入资源中source目录下的src.zip 压缩包到idea中（具体方法：项目结构-》SDK-》选中java-17-》源路径-》导入src.zip压缩包），点击java方法时，即可查看到方法对应的...
通过对JDK 1.8源码的学习，开发者可以深入了解这些新特性的实现原理，提升编程技巧，更好地利用Java平台进行软件开发。同时，源码阅读也能帮助理解Java的内部工作机制，如垃圾收集、类加载、内存管理等，对于优化...
本文将深入分析JDK动态代理的工作原理及其内部实现机制。 #### 二、为什么需要JDK动态代理？ 在实际开发中，经常会遇到需要为已有的类添加新功能的需求，但又不能直接修改这些类的源码。此时，动态代理技术就显得...
通过深入研究JDK 1.4的源码，初学者可以了解Java语言的基础结构、设计模式以及类库的实现原理，这将为后续的高级编程和框架学习打下坚实基础。同时，理解源码也能帮助开发者避免不必要的错误，提高问题排查效率。...
JDK1.7版本的源码提供了对Java语言核心库的深入洞察，而sun包下的源码更是其中的重要组成部分，因为它们包含了Java的核心实现和一些私有API。然而，标准的JDK1.7发行版并未包含完整的sun包源码，这给开发者带来了...
**JDK1.7源码包详解** JDK（Java Development Kit）是Oracle公司发布的Java编程语言的开发工具包，它是Java开发环境的基础。JDK1.7，也被称为Java SE 7（Java Standard Edition 7），是Java发展历程中的一个重要...
其中，"sun"包包含了Java的一些核心实现，如反射、网络、I/O等关键功能，这些源码对于理解Java的工作原理极其重要。 在JDK 1.8中，"sun"包下的源码是许多开发者探索Java内部机制的关键。反射（Reflection）是Java的...
JDK源码，JDK源码，JDK源码，JDK源码，JDK源码，JDK源码，JDK源码
**Java Development Kit (JDK) 1.6 源码包详解** JDK 1.6源码包是Java编程语言的核心开发工具集，它包含了大量的类库和工具，为开发者提供了深入理解Java平台工作原理的机会。源码包允许程序员查看并研究Java API的...
JDK 1.8源码分析可以帮助开发者深入了解Java的内部工作原理，包括类库的实现、垃圾收集机制、编译器优化等。例如，研究`java.util.stream`包下的源码可以理解Stream API的实现细节；查看`java.lang.invoke`包，可以...