JDK的跳表源码实现分析 博客分类： java
程序员文章站
2024-03-06 18:01:20
...
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操作只能保证一个变量操作的原子性。
推荐阅读
-
HashMap和ConcurrentHashMap的实现原理和冲突解决 博客分类： java
-
JDK的跳表源码实现分析 博客分类： java
-
JDK的跳表源码实现分析 博客分类： java
-
String jdk源码查看 博客分类： java JDKJ#
-
不可变类String--阅读源码从jdk开始 博客分类： java基础 java String不可变类
-
linux服务器上安装jdk的两种方法（yum+下载包)(转载) 博客分类： linux 相关JAVA基础知识 linuxjdkyum
-
Set是如何实现"没有重复元素" - hashCode compareTo equals 博客分类： JDK Java多线程
-
Set是如何实现"没有重复元素" - hashCode compareTo equals 博客分类： JDK Java多线程
-
Hibernate在查询的时候2个重要的接口实现 博客分类： Java Hibernate
-
使用maven 如何生成源代码的jar包 博客分类： Java WebJava maven打包源码打包源代码sourcejarsources.jar