在数据结构中，树一直被许多系统钟爱，如mysql 的innodb运用的是B+ 数，在java中Map的hash磕碰后，假如链表超越8 会切换为红黑树。树结构的优点个人认为是在写入的时分对数据进行一个预处理，并且这个出力和子节点的数量相关，在写入的时分依照规则刺进，能够在查询的时分有效的查询对应的子树，然后到达查询时刻为LogN 。如红黑树，红黑树的结构是异构化的23 树，能够确保左右子树的高度差维持在1，有效保证数据平衡，可是红黑树的完成比较复杂，刺进进程涉及到树的重平衡。后来呈现了一种链表的结构，称之为跳表即SkipList，他是由William Pugh 在Skip Lists: A Probabilistic Alternative to Balanced Trees提出的一种平衡性很好的数据结构，这种数据结构是运用空间换时刻，完成较为简略，查询复杂度和树结构接近。在redis 和leveldb中都有运用。本文会介绍下SkipList的基本原理和一个java完成。
SkipList 原理
在某种意义上，链表能够算得上是一种特殊的树，只需一个分支的树。一般情况下分为单向链表和双向链表。单向链表里边的节点会有个指针指向下一个节点，双向链表包括两个指针，一个指向指向他的节点（prev），一个指向下一个节点。SkipList 是单向链表，可是不止一个链表，而是运用n个链表分层，每一层中的node 指向的下一个节点各不相同。后续的阐明首要是针对上文说到的论文中的一个小摘录：
论文中说到（第一节），二叉树在随机巨细写入的情况下功率很高，可是假如是次序巨细写入则体现的比较一般，这个是由于二叉树尤其是平衡二叉树需求对数结构进行一个平衡引起的。
SkipList是一种平衡树的概率性的替代品，这里概率性个人觉得首要是上面说到的随机巨细数据写入进程平衡树功率比次序写高，便是通过别的的方式完成了这种次序写变为随机。论文中说到，250个元素的skiplist需求查询查过3次的概率不到百万分之一。
论文中还说到，skiplist在完成上比较简单，并且运用的是概率性的计算来保持数据的平衡，在空间上平均每个节点或许只需求1+1/3 个指针。
SkipList 还有一个优点就对锁规模的操控上，在平衡二叉树或许红黑树，在并发操作的情况下，特定的时分如需求修改Root节点的属性，或许需求对整棵树都加锁。可是SkipList里边能够针对局部节点进行加锁，在并发情况下完成比较好。
上图选自论文中的figure1。
n标识当时链表的长度，且链表是次序存储的。
- 在初始阶段，当时的单向链表查询或许需求遍历n
- 假如将能够记载每间隔个节点创立衔接，则能够将查找的时刻缩小为n/2+1。依照最上层比较，能够找到当时查询值的前一个节点，所以是n/2+1
- 还能够在2 的根底上，每间隔一个持续创立一个衔接，则时刻缩小为n/4+2。首要最上层找，此刻是n/4，然后在第二层，由于当时中间有b层，并且b层此刻只需1个节点，当时值要么大于这个值要么小于，所以需求2次就能够找到当时值。
- 现在将具有k 个指向其他指针的节点称之为level K 节点，则阐明第2^i 节点后面有2^i 个节点，则节点分布在一个比较均匀的数据中。level0 0 节点有100%个节点，有50% 的节点在level1,有25% 在level2，以此类推。
- 可是假如咱们随机挑选level1 层的节点，或许会呈现上图e中情况，也便是高层分配不均匀，如6 虽然在第四层，可是他却处于第二个方位。
能够看到，SkipList的核心其实是这个层数的确认，假如是依照十分恰当的分配节点中的每一个节点的level，他的时刻复杂度便是logN。
这个上升当时节点的level的机遇是影响链表查询的关键。
SkipList的操作
首要设计到增删查：
- Search操作回来方针关键字所相关的value，假如没有该关键字则回来failure
- Insert操作对方针关键字更新value，假如方针关键字不存在，则将关键字刺进
- Delete操作删去方针关键字。
查询操作
查询操作是删去和刺进的根底，由于每一层都是单向链表，所以必需要找到刺进的父节点才行，假如当时节点的level 较高，或许还需求将查询进程中的每一层的父节点都记载下来。
伪代码如下：（论文figure2）
伪代码是查找一个searchKey 是否在skiplist中。具体步骤如下：
- 将x 初始话为skiplist的头节点
- 进入第一次循环，循环是从当时最大的level 到 level1
- 然后进入第二层循环，在当时层的forword 目标中找到key值不小于当时searchkey的值
- 跳出3 的循环后，此刻已经找到本层不小于searchkey的值，持续往下一层找。假如找到了等于当时searchkey的值，则回来值存储的value。
- 假如从maxlevel到1 都没有这个值，回来一个failture。
查询便是从最上层往下查询的进程。
刺进和删去
在上文中，咱们查询不到这个值就回来一个failture，可是其实也能够回来当时找到的level1层的值，由于这个值是当时skiplist中不小于searchKey的值。假如说是刺进，那么也应该是刺进到这个值的后面。可是由于涉及到level的改变，所以查询进程中需求将当时查到的每一层不小于当时的值都查出来，然后随机一个当时值的level，然后将存储的每一层level都和当时level进行一个绑定。删去也相似。
刺进和删去图形化为:
后文依据论文中的伪代码介绍下操作
刺进
刺进的伪代码如下：论文figure4
- 界说一个变量update，用来存储上文说到的每一层中不小于当时值的Node。
- 查找当时的key和将每一层比较的结果赋值到update中。
- 假如查到当时值了，那么put就变成了update，直接将skiplist中的对应key的value修改为当时的newvalue。
- 假如没有找到，也便是上文说到的，首要随机发生一个当时的level。假如当时的level超越skiplist当时最大的level，那么需求将当时的level设置为新生成的level，然后将head放到每一层的头节点。
- 将刺进的数据变成Node，Node 包括了当时key，value 和level信息，当然内部还有个next信息
- 从第1层往上，将当时的x刺进到每一层。
这里有个问题便是对level的办理，由于不或许随意随机一个数出来，最好的是希望设置一个maxlevel，然后作为seed，在maxLevel下面随机发生层数。
随机算法
在论文中说到过，skiplist本身是个概率性的算法，个人觉得概率性其实便是指的层数的挑选。他想要到达的效果是在上升中，某一层呈现的概率是大致一定的。也便是说假如第i层的元素能够依照某个固定的概率p（上文运用的是1/2）呈现在在i+1 层，这里边涉及到概率论里边期望运算，就不再赘述了（我已经还给教师了）。一句话说便是如过挑选的是p=1/2，那么咱们就希望假如n等于16，那么第0层是16，第2次是8，第三层是4。说白了便是回来的值呈现的概率是一样的，比方 回来1的概率便是1/2，回来2的概率便是1/4。
private static final double PROBABILITY = 0.5;
private int randomLevel() {
int level = 1;
Random random = new Random();
while (random.nextDouble() < PROBABILITY && level < MAX_LEVEL) {
level++;
}
return level;
}
运用这种方式能够生成，首要是由于random.nextDouble() 呈现的数是比较均匀的分布，便是呈现的概率是相对一定的，然后只需小于0.5 就多一层，也便是上面的1/2的概率，持续添加level，则便是1/2 *1/2 的概率了。
删去
删去也是在查询根底上做的，伪代码如下：
首要仍然是记载下查询进程的每一层的上一个节点，假如找到这个值对应的Node，就将update中存储的值都进行一个链表删去操作，然后释放内存。最终，还需求检查当时是否删去了最高的level中的最终一个node，假如是还需求将当时的level减1.
自己写个SkipList
运用java 自己写了个skiplist，其中数据运用DataNode，索引运用IndexNode，避免值的无效覆盖：
import java.util.LinkedList;
import java.util.Random;
public class SkipList<K extends Comparable<K>, V> {
// 当时最大的层数
private int maxLevel = 12;
// 头结点，down 运用down指向下一层
private SkipListIndexNode<K, V> head;
// 当时的level
private int level = 1;
private static Random random;
//跳到下一层的概率
private double probability = 0.5;
public SkipList(int maxLevel, double probability) {
random = new Random();
this.maxLevel = maxLevel;
this.probability = probability;
SkipListDataNode data = new SkipListDataNode(Integer.MIN_VALUE, null);
head = new SkipListIndexNode(data, 1);
}
// 依据key ，回来存储的Value，假如没有，回来null
public V get(K key) {
SkipListDataNode<K, V> old = searchNode(key);
if (old != null) {
return old.value;
} else {
return null;
}
}
// 获取最大值，应该有更优解，比方存储最底层的末尾节点
public K getMax() {
SkipListIndexNode<K, V> cur = head;
while (cur.down != null) {
while (cur.right != null) {
cur = cur.right;
}
if (cur.down == null && cur.right == null) {
break;
}
cur = cur.down;
}
return cur.getKey();
}
// 获取最小值，应该有更优解，比方存储最底层的head节点
public K getMin() {
SkipListIndexNode<K, V> cur = head;
while (cur.down != null) {
cur = cur.down;
}
return cur.right == null ? null : cur.right.getKey();
}
public void put(K key, V value) {
SkipListDataNode old = searchNode(key);
if (old != null) {
old.value = value;
return;
}
int newLevel = randomLevel();
if(newLevel>maxLevel){
newLevel=maxLevel;
}
if (newLevel > level ) {
for (int i = level; i < newLevel; i++) {
genNewHead();
}
}
SkipListDataNode<K, V> data = new SkipListDataNode<K, V>(key, value);
SkipListIndexNode<K, V> indexNode = new SkipListIndexNode<K, V>(data, newLevel);
LinkedList<SkipListIndexNode> update = new LinkedList<SkipListIndexNode>();
SkipListIndexNode<K, V> cur = head;
while (cur != null && cur.level > newLevel) {
cur = cur.down;
}
while (cur != null) {
while (cur.right != null && cur.right.getKey().compareTo(key) < 0) {
cur = cur.right;
}
update.add(cur);
cur = cur.down;
}
SkipListIndexNode<K, V> bottom = null;
while (!update.isEmpty()) {
SkipListIndexNode prevNode = update.pollLast();
SkipListIndexNode curLevelIndex = indexNode.genIndexNodeByLevel(prevNode.level);
curLevelIndex.right = prevNode.right;
prevNode.right = curLevelIndex;
curLevelIndex.down = bottom;
bottom = curLevelIndex;
}
}
public void delete(K key) {
LinkedList<SkipListIndexNode> update = new LinkedList<SkipListIndexNode>();
SkipListIndexNode<K, V> cur = head;
while (cur != null) {
while (cur.right != null && cur.right.getKey().compareTo(key) < 0) {
cur = cur.right;
}
update.add(cur);
cur = cur.down;
}
while (!update.isEmpty()) {
SkipListIndexNode skipListIndexNode = update.pollLast();
if (skipListIndexNode.right != null && skipListIndexNode.right.getKey().compareTo(key) == 0) {
skipListIndexNode.right = skipListIndexNode.right.right;
}
}
while (head.right == null) {
level--;
head = head.down;
}
}
// 分层打印skiplist
public void printList() {
SkipListIndexNode bottom = head;
LinkedList<SkipListIndexNode> stack = new LinkedList<SkipListIndexNode>();
while (bottom.down != null) {
bottom = bottom.down;
}
SkipListIndexNode printLevel = head;
while (printLevel != null) {
SkipListIndexNode printLeveltail = printLevel;
System.out.printf("%-5s", "head->");
SkipListIndexNode bottomTail = bottom;
while (printLeveltail != null && bottomTail != null) {
if (printLeveltail.right != null && printLeveltail.right.getKey().compareTo(bottomTail.right.getKey()) == 0) {
System.out.printf("%-5s", printLeveltail.right.getKey() + "->");
printLeveltail = printLeveltail.right;
} else {
System.out.printf("%-5s", "");
}
bottomTail = bottomTail.right;
}
printLevel = printLevel.down;
System.out.println();
}
}
// 通过key查询当时的节点，假如没有，则回来null
private SkipListDataNode searchNode(K key) {
if (key == null) {
return null;
}
SkipListIndexNode<K, V> cur = head;
while (cur != null) {
while (cur.right != null && cur.right.getKey().compareTo(key) < 0) {
cur = cur.right;
}
if (cur.right != null && cur.right.getKey().compareTo(key) == 0) {
return cur.right.dataNode;
}
cur = cur.down;
}
return null;
}
// 呈现需求扩展当时层数的情况下，创立新的head
private void genNewHead() {
SkipListIndexNode<K, V> skipListIndexNode = new SkipListIndexNode<K, V>(null, ++level);
skipListIndexNode.down = head;
head = skipListIndexNode;
}
// 依照概率生成level
private int randomLevel() {
int level = 1;
while (random.nextDouble() < probability && level < maxLevel) {
level++;
}
return level;
}
public static void main(String[] args) {
SkipList<Integer, Integer> skipList = new SkipList<Integer, Integer>(12, 0.5);
for (int i = 1; i <= 200; i++) {
skipList.put(new Random().nextInt(200), 100 + i);
}
skipList.printList();
;
System.out.println(skipList.get(10));
System.out.println(skipList.get(11));
System.out.println(skipList.get(12));
System.out.println(skipList.getMin());
System.out.println(skipList.getMax());
for (int i = 0; i <= 20; i += 2) {
skipList.delete(i);
}
System.out.println(skipList.get(10));
System.out.println(skipList.get(11));
System.out.println(skipList.get(12));
System.out.println(skipList.getMin());
System.out.println(skipList.getMax());
}
// 存储数据的节点，每一份数据只保存一次
class SkipListDataNode<K extends Comparable<K>, V> {
private K key;
private V value;
SkipListDataNode(K key, V value) {
this.key = key;
this.value = value;
}
}
// 索引节点，用来创立skiplist的结构
class SkipListIndexNode<K extends Comparable<K>, V> {
SkipListDataNode<K, V> dataNode;
int level = 0;
SkipListIndexNode<K, V> right;
SkipListIndexNode<K, V> down;
public SkipListIndexNode(SkipListDataNode<K, V> dataNode, int level) {
this.dataNode = dataNode;
this.level = level;
}
public SkipListIndexNode genIndexNodeByLevel(int level) {
return new SkipListIndexNode(this.dataNode, level);
}
public V getValue() {
return dataNode.value;
}
public K getKey() {
return dataNode.key;
}
}
}
上面是能够直接run 起来，最终按层数打印当时的skiplist
head-> 107->
head->8-> 41-> 107->
head->8-> 41-> 98-> 107-> 177->
head->8-> 41-> 67-> 70-> 92-> 98-> 107->120->177-> 181->
head->8-> 17-> 34-> 37-> 41-> 45-> 67-> 70-> 76-> 92-> 98-> 101->107->120->177->179->181->
