内容目录
1、源码
源码地址: GITHUB
https://github.com/fofcn/operation-system/blob/main/%E5%AE%9E%E8%B7%B5/os/src/main/java/lang/skiplists/SkipLists.java
2、概念
跳跃表命名的原因是因为作者认为链表结构使用了额外的节点之间的指针。
跳跃表是一种可能的平衡树的替换方法。跳跃表是通过查询一个随机数生成器来保持平衡。尽管跳跃表在最坏情况性能特别差，但是在平均情况下跳跃表的性能很好。
跳跃表的关键概念是有序，索引节点有序，数据节点有序，这样层层查找才能进行二分查找。
下图为跳跃表的模型图：
3、跳跃表
通常列表的搜索需要列表链表中的每一个节点是否和搜索内容一致。如果列表是有序的，并且列表中每两个节点都有一个指向该节点的指针，那么我们检查的次数不会超过n/2 + 1次。如果每四个节点都有一个指向该节点的指针，那么需要不超过n/4 + 2次检查就可以找到元素。如果每个2^i个节点都有一个节点指向它，那么检查次数可以减少到log（n）次。跳跃表可以用来快速搜索，但是插入和删除的运行时间会比较长。
4、跳跃表算法
这部分给出跳跃表在字典或符号表应用中的搜索、插入和删除算法。
4.1、搜索
搜索操作返回key关联的value值，如果失败则返回不存在。下图给出了搜索路径（图片来自原）
4.2、插入
插入操作将一个key对应的值插入到跳跃表中，如果插入的key已经存在则更新值。
4.3、删除
删除操作来删除指定的key。
其他操作也很容易支持，比如：查找最大或最小的key。
删除完成后需要检查是否需要减少索引层数。
5、算法实现
5.1、搜索
/**
* 根据key从跳跃表中获取一个值
* @param key key
* @return 存在则返回对应的value，不存在则返回null
*/
public Value get(Key key) {
// 参数检查
if (key == null) {
throw new IllegalArgumentException();
}
// 找到key对应的前驱节点
Node<Key, Value> predecessor = findPredecessor(key);
// 从前驱节点开始遍历查找key对应的节点
for (Node<Key, Value> next = predecessor.next;;) {
if (next == null) {
break;
}
// key与节点的Key比较
// 如果相等就找到了直接返回值
// 如果key大于节点的key，继续向后查找
// 如果key小于节点的key，那么没找到，退出循环
int cmp = key.compareTo(next.key);
if (cmp == 0) {
return next.value;
} else if (cmp > 0) {
next = next.next;
} else {
break;
}
}
return null;
}5.2、插入
/**
* 向跳跃表添加一个key-value对
* @param key key
* @param value value
*/
public void put(Key key, Value value) {
if (key == null) {
throw new NullPointerException();
}
Node<Key, Value> newNode = null;
// 找到最底层插入节点的前驱节点
Node<Key, Value> predecessor = findPredecessor(key);
// 找到索引节点对应的数据节点以后，开始查找插入数据前驱节点
for (Node<Key, Value> b = predecessor, next = b.next;;) {
if (next != null) {
// 如果插入的key大于当前数据节点，那么继续查找下一个
int cmp = key.compareTo(next.key);
if (cmp > 0) {
b = next;
next = next.next;
continue;
} else if (cmp == 0) {
next.value = value;
break;
}
}
// 新建节点并更改前驱节点的下一个节点为新节点
newNode = new Node<>(key, value, next);
b.next = newNode;
break;
}
// 是否要为数据节点添加索引层
int level = randomLevel();
// 需要加层
if (level > header.level) {
int oldLevel = header.level;
int newLevel = level;
// 为新节点创建索引节点
Index<Key, Value>[] newNodeIndexes = createNewNodeIndex(newNode, newLevel);
// 为头结点增量补充索引节点,并将头结点的索引节点指向新节点的索引节点
header = incrHeaderIdxes(newLevel, newNodeIndexes);
// 根据老层更新新节点的数据
updateIndex(key, newNodeIndexes[oldLevel], oldLevel, newLevel);
} else {
// 如果节点索引层大于1就需要为节点新建索引层
if (level > 1) {
// 根据新节点索引层新建节点索引
Index<Key, Value>[] newNodeIndexes = createNewNodeIndex(newNode, level);
// 更新索引
// 在没有新建层时，为新节点新建层传入的新层参数是头索引的层数，因为每次都从头索引开始查找，
// 需要将头索引直接下降到对应的层后开始修改关系
updateIndex(key, newNodeIndexes[level], level, header.level);
}
}
}5.3、删除
/**
* 根据key删除一个节点
* 注意删除节点可能需要减层
* @param key 要删除的关键字
* @return key对应的value值，如果没有找到value就返回null
*/
public Value delete(Key key) {
if (key == null) {
throw new NullPointerException();
}
Value val = null;
// 找到最底层插入节点的前驱节点
Node<Key, Value> predecessor = findPredecessor(key);
for (Node<Key, Value> b = predecessor, next = b.next;;) {
if (next != null) {
// 如果插入的key大于当前数据节点，那么继续查找下一个
int cmp = key.compareTo(next.key);
if (cmp > 0) {
b = next;
next = next.next;
continue;
} else if (cmp < 0) {
break;
} else {
// 相等就将节点元素设置为空
val = next.value;
next.value = null;
break;
}
}
break;
}
// 通过查找前驱索引节点删除可能需要删除的索引
// 删除索引的标记信息就是node.value==null
findPredecessor(key);
// 删除层
// 如果头索引的右侧索引已经被删除就减层
while (header.right == null && header.level > 1) {
header = (HeaderIndex<Key, Value>) header.down;
}
return val;
}5.4、其他关键实现
5.4.1、查找key对应的前驱索引
/**
* 查找key对应的前驱索引
* @param key key
* @return 前驱索引
*/
private Index<Key, Value> findIndex(Key key) {
for (Index<Key, Value> cur = header, right = cur.right, down;;) {
// 如果索引的右侧不为空
// 用搜索的key对数据节点的key进行比较
// 如果搜索的key大于索引节点的key，那么继续向右进行搜索
if (right != null) {
Node<Key, Value> n = right.node;
Key k = n.key;
// value为空代表节点的值已经被删除
// 删除节点对应的索引
if (n.value == null) {
// 将当前所有的右侧索引更新为右侧的右侧
cur.right = right.right;
// 更新right索引变量为当前索引的右侧
right = cur.right;
continue;
}
// 如果搜索的key大于右侧节点指向的key，那么继续向右查找
if (key.compareTo(k) > 0) {
cur = right;
right = right.right;
continue;
}
}
// 如果索引节点的右侧节点大于key，那么向下放索引查找
if ((down = cur.down) != null) {
// 将当前节点指向下方索引节点
// 右侧节点指针指向下方索引的右侧
cur = down;
right = down.right;
} else {
return cur;
}
}
}5.4.2、随机生成节点层
/**
* 随机生成节点的层，但是不超过32
* @return 新节点层数
*/
private int randomLevel() {
int level = 1;
int rnd = ThreadLocalRandom.current().nextInt(1, 101);
while (rnd > PROBABILITY && level <= MAX_LEVEL) {
// 根据随机数来生成索引层数
++level;
rnd = ThreadLocalRandom.current().nextInt(1, 101);
}
return level;
}5.4.3、更新索引
/**
* 更新老层的索引
* @param key 关键字
* @param newNodeOldIdx 新节点索引
* @param oldLevel 老层数
* @param newLevel 新层数
*/
private void updateIndex(Key key, Index<Key, Value> newNodeOldIdx, int oldLevel, int newLevel) {
Index<Key, Value> newNodeIdx = newNodeOldIdx;
Index<Key, Value> precursorIdx = header;
// 跳过新索引层，因为已经做了关联
for (int i = oldLevel + 1; i <= newLevel; i++) {
precursorIdx = precursorIdx.down;
}
Index<Key, Value> right = precursorIdx.right;
// 找到对应的层之后，我们开始向右继续查找前驱索引节点
while (true) {
if (right != null && right.node.value != null) {
int cmp = key.compareTo(right.node.key);
if (cmp > 0) {
precursorIdx = right;
right = right.right;
continue;
}
}
// 找到需要更新的索引之后，重建索引
// 前驱索引节点的右侧设置新的索引
precursorIdx.right = newNodeIdx;
// 新索引有右侧设置为老索引的右侧节点
newNodeIdx.right = right;
// 新节点索引向下
newNodeIdx = newNodeIdx.down;
// 老索引向下
precursorIdx = precursorIdx.down;
if (precursorIdx == null) {
break;
}
}
}6、总结
- 跳跃表特点就是通过跳跃的方式组织数据，相当于给数据建了一个多级索引，思想有点像二分查找
- 跳跃表更容易实现并且运行效率也很高
- 跳跃表使用了空间换取时间的设计思想
7、参考
- https://www.cl.cam.ac.uk/teaching/0506/Algorithms/skiplists.pdf
- JDK1.8 ConcurrentSkipListMap源码