快速的 SkipList 实现教程
在计算机科学领域，跳跃链表是一种数据结构，允许快速查询一个有序连续元素的数据链表。快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集。
基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作需要O(log n)平均时间）。
基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表，因此得名。所有操作都以对数随机化的时间进行。
要查找一个目标元素，起步于头元素和顶层列表，并沿着每个链表搜索，直到到达小于或着等于目标的最后一个元素。通过跟踪起自目标直到到达在更高列表中出现的元素的反向查找路径，在每个链表中预期的步数显而易见是 1/*p*。所以查找的总体代价是 O((log1/p n) / p)，当p 是常数时是 O(log n)。通过选择不同 p 值，就可以在查找代价和存储代价之间作出权衡。
插入和删除的实现非常像相应的链表操作，除了”高层”元素必须在多个链表中插入或删除之外。
跳跃列表不像某些传统平衡树数据结构那样提供绝对的最坏情况性能保证，因为用来建造跳跃列表的扔硬币方法总有可能（尽管概率很小）生成一个糟糕的不平衡结构。但是在实际中它工作的很好，随机化平衡方案比在平衡二叉查找树中用的确定性平衡方案容易实现。跳跃列表在并行计算中也很有用，这里的插入可以在跳跃列表不同的部分并行的进行，而不用全局的数据结构重新平衡。
—— Wikipedia
以上就是 Wikipedia 中对 SkipList 的描述，从描述中和以往的了解我们可以得知，SkipList 是对 List 的一种加强，通过拔高某些 Node 的层次来达到快速搜索的目的，根据这个想法我们可以知道，这个有点类似于躺平的二叉搜索树，这套 快速实现教程 的目的，就是截取文章中讨论内容的重点部分，通过重点讨论其中的精要部分来达到快速实现的目的。
搜索方法
我们知道 SkipList 的结构知道我们就知道应该怎么对这个东西进行搜索，首先是从最上层的开始搜索，根据 Key 的比较进行判断向哪个方向进行搜索：
private SkipListNode<K, V> findNodeByKey(K key) {
SkipListNode<K, V> head = headNode;
while (true) {
// 首先右侧节点不为空 并且当前节点比右侧节点大 ===> 我们可以往右侧进行查找
while (head.right.key != null && key.compareTo(head.right.key) >= 0) {
head = head.right;
}
// 向下查找 ===> 直到最下一层
if (head.down != null) {
head = head.down;
} else {
break;
}
}
return head;
}
根据 从左到右，从上到下 的方法，我们就能查找到对应的节点，如果本身 List 中没有对应的节点，我们会获得 比所搜索的 Key 最小的一个节点 这样我们无论是存放还是搜索都很方便。
private SkipListNode<K, V> search(K key) {
SkipListNode<K, V> p = findNodeByKey(key);
if (key.equals(p.key)) {
return p;
} else {
return null;
}
}
暴露在外层的方法，可以根据拿到的 Node 是 所找的节点 还是 接近的节点 来判断返回。
存放方法
普通的存放方法其实是和普通的 LinkedList 是类似的，因为毕竟无论是几层的 Level 最终数据都是存储在 最下面一层的，所以我们存储的开始就和普通的链表没有区别，但是由于有 层次 的设定，所以说我们每个 Node 类都有 上下左右 四个方向的功能：
static class SkipListNode<K, V> implements Entry<K, V> {
/**
* point to =>
*/
SkipListNode<K, V> up, down, left, right;
K key;
V value;
}
我们可以先来简单的实现普通的存储方法：
@Override
public V put(K key, V value) {
if (key == null) {
throw new UnsupportedOperationException("key could not be null");
}
// 找到对应的 Key-Node 或者是最近的节点
SkipListNode<K, V> p = findNodeByKey(key);
// 如果存在这个节点只需要替换 Value 就可以了
if (key.equals(p.key)) {
p.value = value;
return value;
}
// 把新节点放在 p 节点后面
SkipListNode<K, V> q = new SkipListNode<>(key, value);
// 一些绑定而已
backLink(p, q);
nodeCounts++;
// ...
}
这部分只是普通的 LinkedList 的存取方法，然后更新一些数据而已，刚才我们从 SkipList 的介绍中可以得出，SkipList 是一个概率型的数据结构，每次存储的时候 随机进行把 level 把高的操作 ：
// current level
int currentLevel = 0;
while (random.nextDouble() < PROBABILITY) {
// 当 `当前拔高的层次` 超过已有的层次，新建层次
if (currentLevel >= listLevels) {
createNewLevel();
}
// 向左搜索 =====> 直到一个有上层的节点
while (p.up == null) {
// 这个 corner case 是为了解决此时还没有上面的层次
if (p.left == null) {
// p equal header node
createNewLevel();
break;
}
p = p.left;
}
// 向上拔高一层
p = p.up;
// 只保存 key
SkipListNode<K, V> e = new SkipListNode<>(key, null);
// 各方面链接
backLink(p, e);
verticalLink(e, q);
// 交换节点有助于多层链接
q = e;
currentLevel++;
}
新建层次：
private void createNewLevel() {
listLevels++;
SkipListNode<K, V> p1 = new SkipListNode<>(null, null);
SkipListNode<K, V> p2 = new SkipListNode<>(null, null);
horizontalLink(p1, p2);
verticalLink(p1, headNode);
verticalLink(p2, tailNode);
headNode = p1;
tailNode = p2;
}
删除方法
删除操作肯定也是和 Search 操作紧密衔接的，我们 先找到最底层的节点，然后从下到上逐层删除索引 。
@Override
public V remove(Object key) {
// nest noe
SkipListNode<K, V> node = findNodeByKey((K) key);
if (node == null) {
return null;
// 找到的 节点的部分
} else if (node.key.equals(key)) {
// 从下到上不断读取节点合并两侧的节点
while (node != null) {
SkipListNode<K, V> left = node.left;
SkipListNode<K, V> right = node.right;
if (left != null && right != null) {
horizontalLink(left, right);
}
node = node.up;
}
node = headNode;
// 从上到下删除空的层次 —— 这个操作其实不是必要的，
// 很多的实现仅仅是删除最上层的空层
while (node != null && node.right.equals(tailNode)) {
SkipListNode<K, V> oldHeadNode = headNode;
SkipListNode<K, V> oldTailNode = tailNode;
this.headNode = oldHeadNode.down;
this.tailNode = oldTailNode.down;
this.listLevels--;
node = headNode;
oldHeadNode = null;
oldTailNode = null;
}
}
return null;
}
删除的内容就比较简单了：
- 获取最下层节点
- 从下到上不断读取节点合并两侧的节点
- 删除空层
你学到了什么
- 一种新的搜索和存储的数据结构
- 快速构建 Skip-List 数据结构的思路和组成方法
全部代码
package set;
import com.sun.org.apache.bcel.internal.classfile.ExceptionTable;
import java.util.*;
/**
* Created by liufengkai on 2017/9/11.
*/
public class SkipList<K extends Comparable<K>, V> implements Map<K, V> {
/**
* Probability to flow one node up
*/
private static final double PROBABILITY = 0.5;
/**
* head / tail
*/
private SkipListNode<K, V> headNode, tailNode;
/**
* all node counts
*/
private int nodeCounts;
/**
* all list level
*/
private int listLevels;
/**
* random util
*/
private Random random;
/**
* Key Set
*/
private Set<K> keySet = new HashSet<>();
/**
* Value Set
*/
private Set<V> valueSet = new HashSet<>();
public SkipList() {
this.random = new Random();
this.clear();
}
@Override
public int size() {
return nodeCounts;
}
@Override
public boolean isEmpty() {
return nodeCounts == 0;
}
@Override
public boolean containsKey(Object key) {
return get(key) != null;
}
@Override
public boolean containsValue(Object value) {
for (SkipListNode node = headNode; node != null; node = node.right) {
if (node.value.equals(value)) {
return true;
}
}
return false;
}
@Override
public V get(Object key) {
if (key == null) {
throw new UnsupportedOperationException("key could not be null");
}
SkipListNode<K, V> node = search((K) key);
return node == null ? null : node.value;
}
@Override
public V put(K key, V value) {
if (key == null) {
throw new UnsupportedOperationException("key could not be null");
}
SkipListNode<K, V> p = findNodeByKey(key);
// change value | equal key
if (key.equals(p.key)) {
p.value = value;
return value;
}
SkipListNode<K, V> q = new SkipListNode<>(key, value);
backLink(p, q);
nodeCounts++;
// current level
int currentLevel = 0;
while (random.nextDouble() < PROBABILITY) {
if (currentLevel >= listLevels) {
createNewLevel();
}
// find up level node to bind it
while (p.up == null) {
if (p.left == null) {
// p equal header node
createNewLevel();
break;
}
p = p.left;
}
// upper level node
p = p.up;
// save key
SkipListNode<K, V> e = new SkipListNode<>(key, null);
backLink(p, e);
verticalLink(e, q);
q = e;
currentLevel++;
}
keySet.add(key);
valueSet.add(value);
return value;
}
private void createNewLevel() {
listLevels++;
SkipListNode<K, V> p1 = new SkipListNode<>(null, null);
SkipListNode<K, V> p2 = new SkipListNode<>(null, null);
horizontalLink(p1, p2);
verticalLink(p1, headNode);
verticalLink(p2, tailNode);
headNode = p1;
tailNode = p2;
}
@Override
public V remove(Object key) {
SkipListNode<K, V> node = findNodeByKey((K) key);
if (node == null) {
return null;
} else if (node.key.equals(key)) {
while (node != null) {
SkipListNode<K, V> left = node.left;
SkipListNode<K, V> right = node.right;
if (left != null && right != null) {
horizontalLink(left, right);
}
node = node.up;
}
node = headNode;
while (node != null && node.right.equals(tailNode)) {
SkipListNode<K, V> oldHeadNode = headNode;
SkipListNode<K, V> oldTailNode = tailNode;
this.headNode = oldHeadNode.down;
this.tailNode = oldTailNode.down;
this.listLevels--;
node = headNode;
oldHeadNode = null;
oldTailNode = null;
}
}
return null;
}
@Override
public boolean remove(Object key, Object value) {
return remove(key) != null;
}
@Override
public void putAll(Map<? extends K, ? extends V> m) {
for (Entry<? extends K, ? extends V> entry : m.entrySet()) {
put(entry.getKey(), entry.getValue());
}
}
@Override
public void clear() {
this.headNode = new SkipListNode<>(null, null);
this.tailNode = new SkipListNode<>(null, null);
this.nodeCounts = 0;
this.listLevels = 0;
// horizontal link head === tail nodes
this.horizontalLink(headNode, tailNode);
}
@Override
public Set<K> keySet() {
return keySet;
}
@Override
public Collection<V> values() {
return valueSet;
}
@Override
public Set<Entry<K, V>> entrySet() {
Set<Entry<K, V>> set = new HashSet<>();
for (SkipListNode<K, V> node = headNode; node != null; node = node.right) {
set.add(node);
}
return set;
}
/**
* add front link after node
*
* @param front front-node
* @param back back-node
*/
private void backLink(SkipListNode<K, V> front, SkipListNode<K, V> back) {
back.left = front;
back.right = front.right;
front.right.left = back;
front.right = back;
}
private SkipListNode<K, V> findNodeByKey(K key) {
// System.out.println("Start Search: ");
SkipListNode<K, V> head = headNode;
while (true) {
while (head.right.key != null && key.compareTo(head.right.key) >= 0) {
head = head.right;
// System.out.println(head);
}
if (head.down != null) {
head = head.down;
// System.out.println(head);
} else {
break;
}
}
return head;
}
private SkipListNode<K, V> search(K key) {
SkipListNode<K, V> p = findNodeByKey(key);
if (key.equals(p.key)) {
return p;
} else {
return null;
}
}
/**
* Horizontal Link
*
* @param left left node
* @param right right node
*/
private void horizontalLink(SkipListNode<K, V> left, SkipListNode<K, V> right) {
left.right = right;
right.left = left;
}
/**
* Vertical Link
*
* @param up up node
* @param down down node
*/
private void verticalLink(SkipListNode<K, V> up, SkipListNode<K, V> down) {
up.down = down;
down.up = up;
}
String debugStructure() {
List<List<SkipListNode<K, V>>> list = new LinkedList<>();
int currentLevel = listLevels;
SkipListNode<K, V> node = headNode;
while (true) {
if (currentLevel == -1) break;
List<SkipListNode<K, V>> levelList = new LinkedList<>();
while (node != null) {
levelList.add(node);
node = node.right;
}
currentLevel--;
int times = listLevels - currentLevel;
node = headNode;
while (times != 0) {
node = node.down;
times--;
}
list.add(levelList);
}
StringBuilder builder = new StringBuilder();
for (int i = 0; i < list.size(); i++) {
List<SkipListNode<K, V>> level = list.get(i);
builder.append("Level : ")
.append(String.valueOf(listLevels - i))
.append(" > \t");
for (SkipListNode<K, V> kvSkipListNode : level) {
builder.append(kvSkipListNode.key)
.append("\t");
}
builder.append("\n");
if (i == list.size() - 1) {
builder.append(" \t");
for (SkipListNode<K, V> kvSkipListNode : level) {
builder.append(kvSkipListNode.value)
.append("\t");
}
}
}
return builder.toString();
}
/**
* Node in Skip List
*
* @param <V> Type
*/
static class SkipListNode<K, V> implements Entry<K, V> {
/**
* point to =>
*/
SkipListNode<K, V> up, down, left, right;
K key;
V value;
SkipListNode(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public V setValue(V value) {
return this.value = value;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null) {
return false;
}
if (!(o instanceof SkipListNode<?, ?>)) {
return false;
}
SkipListNode<K, V> ent;
try {
ent = (SkipListNode<K, V>) o;
} catch (ClassCastException ex) {
return false;
}
return (ent.key == key) && (ent.value == value);
}
@Override
public String toString() {
return "SkipListNode{" +
"key=" + key +
", value=" + value +
'}';
}
}
}
测试代码和结果
class SkipListTest {
@Test
void testSkip() {
SkipList<Integer, String> list = new SkipList<>();
Random random = new Random();
for (int i = 0; i < 5; i++) {
list.put(Math.abs(random.nextInt() % 10), i + "lfk");
}
System.out.println(list.debugStructure());
for (Integer key : list.keySet()) {
System.out.println("========> remove key :" + key + " <========= ");
list.remove(key);
System.out.println(list.debugStructure());
}
}
}
测试结果：
Level : 2 > null 4 null
Level : 1 > null 4 null
Level : 0 > null 2 3 4 9 null
null 3lfk 4lfk 2lfk 1lfk null
========> remove key :2 <=========
Level : 2 > null 4 null
Level : 1 > null 4 null
Level : 0 > null 3 4 9 null
null 4lfk 2lfk 1lfk null
========> remove key :3 <=========
Level : 2 > null 4 null
Level : 1 > null 4 null
Level : 0 > null 4 9 null
null 2lfk 1lfk null
========> remove key :4 <=========
Level : 0 > null 9 null
null 1lfk null
========> remove key :9 <=========