大数据和云计算读书笔记（3）

这次讲SkipList，其实这是第四篇了，上周一的Boom filter也是大数据的常用算法。

01

—

简介

SkipList，一般译作跳表，由William Pugh于1990年提出，是一种可替代平衡树的数据结构。在William的论文《Skip lists: a probabilistic alternative to balanced trees》中是这么说的，

Skip lists are a data structure that can be used in place of balanced trees.

Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

尽管SkipList在最坏的情况下效率不如平衡树，但在大多数情况下表现更好，其插入，删除和查找的时间复杂度都是O（log（N））。因为其优异得性能且编程实现比红黑树简单，所以很多大数据系统中维护有序列表高效读写的场景下会采用SkipList，比如LevelDB的MemTable是用SkipList实现的 ，Redis的Sotored Set也是用它实现的， Lucene也使用SkipList对倒排列表进行快速查找。

02

—

原理

下图来自William的论文

上图a，已排好序的链表，查找一个结点最多需要比较个结点。

上图b，每隔2个结点增加一个指针，指向该结点间距为2的后续结点，那么查找一个结点最多需要比较个结点。

上图c，每隔4个结点增加一个指针，指向该结点间距为4的后续结点，那么查找一个结点最多需要比较个结点。

如果每第个结点都有一个指向间距为2^i的后续结点的指针，这样不断增加指针，比较次数会降为。这样的话，搜索会很快，但插入和删除会很困难。

一个拥有k个指针的结点称为一个k层结点（level k node）。按照上面的逻辑，50%的结点为1层，25%的结点为2层，12.5%的结点为3层...如果每个结点的层数随机选取，但仍服从这样的分布呢（上图e，对比上图d）？

使一个k层结点的第i个指针指向第i层的下一个结点，而不是它后面的第2^(i-1)个结点，那么结点的插入和删除只需要原地修改操作；一个结点的层数，是在它被插入的时候随机选取的，并且永不改变。因为这样的数据结构是基于链表的，并且额外的指针会跳过中间结点，所以作者称之为跳表（Skip Lists）。

SkipList中的查找非常便捷，假设skip list的key按照从小到大的顺序排列，那么从跳表的当前最高层listLevel开始寻找searchKey。在某一层找到一个非小于searchKey的结点后，跳到下一层继续找，直到最底层为止。那么根据最后搜索停止位置的下一个结点，就可以判断searchKey在不在跳表中。

下图为在跳表中找8的过程：

SkipList插入删除的方法相似，都是通过查找与连接（search and splice），如下图：

维护一个update数组，在搜索结束之后，update[i]保存的是待插入/删除结点在第i层的左侧结点。

1. 插入

若key不存在，则插入该key与对应的value；若key存在，则更新value。

如果待插入的结点的层数高于跳表的当前层数listLevel，则更新listLevel。

选择待插入结点的层数randomLevel：

randomLevel只依赖于跳表的最高层数和概率值p。算法在后面的代码中。

另一种实现方法为，如果生成的randomLevel大于当前跳表的层数listLevel，那么将randomLevel设置为listLevel+1，这样方便以后的查找，在工程上是可以接受的，但同时也破坏了算法的随机性。

2. 删除

删除特定的key与对应的value。

如果待删除的结点为跳表中层数最高的结点，那么删除之后，要更新listLevel。

03

—

Code

java的类库中没有普通的SkipList，但是在concurrent库中可以看到这两个个类型：ConcurrentSkipListMap和ConcurrentSkipListSet，其实他们底层都是使用的基于CAS来构建的SkipList。

我在网上找到了一个通用SkipList的实现以及一个测试。

public class SkipList {

// 最高层数

private final int MAX_LEVEL;

// 当前层数

private int listLevel;

// 表头

private SkipListNode listHead;

// 表尾

private SkipListNode NIL;

// 生成randomLevel用到的概率值

private final double P;

// 论文里给出的最佳概率值

private static final double OPTIMAL_P = 0.25;

public SkipList() {

// 0.25, 15

this(OPTIMAL_P, (int)Math.ceil(Math.log(Integer.MAX_VALUE) / Math.log(1 / OPTIMAL_P)) - 1);

}

public SkipList(double probability, int maxLevel) {

P = probability;

MAX_LEVEL = maxLevel;

listLevel = 1;

listHead = new SkipListNode(Integer.MIN_VALUE, null, maxLevel);

NIL = new SkipListNode(Integer.MAX_VALUE, null, maxLevel);

listHead.forward[i] = NIL;

}

}

// 内部类

class SkipListNode {

int key;

T value;

SkipListNode[] forward;

public SkipListNode(int key, T value, int level) {

this.key = key;

this.value = value;

this.forward = new SkipListNode[level];

}

}

public T search(int searchKey) {

SkipListNode curNode = listHead;

for (int i = listLevel; i > 0; i--) {

while (curNode.forward[i].key

curNode = curNode.forward[i];

}

}

if (curNode.key == searchKey) {

return curNode.value;

} else {

return null;

}

}

public void insert(int searchKey, T newValue) {

SkipListNode[] update = new SkipListNode[MAX_LEVEL];

SkipListNode curNode = listHead;

for (int i = listLevel - 1; i >= 0; i--) {

while (curNode.forward[i].key

curNode = curNode.forward[i];

}

// curNode.key

update[i] = curNode;

}

curNode = curNode.forward[0];

if (curNode.key == searchKey) {

curNode.value = newValue;

} else {

int lvl = randomLevel();

if (listLevel

for (int i = listLevel; i

update[i] = listHead;

}

listLevel = lvl;

}

SkipListNode newNode = new SkipListNode(searchKey, newValue, lvl);

for (int i = 0; i

newNode.forward[i] = update[i].forward[i];

update[i].forward[i] = newNode;

}

}

}

public void delete(int searchKey) {

SkipListNode[] update = new SkipListNode[MAX_LEVEL];

SkipListNode curNode = listHead;

for (int i = listLevel - 1; i >= 0; i--) {

while (curNode.forward[i].key

curNode = curNode.forward[i];

}

// curNode.key

update[i] = curNode;

}

curNode = curNode.forward[0];

if (curNode.key == searchKey) {

for (int i = 0; i

if (update[i].forward[i] != curNode) {

break;

}

update[i].forward[i] = curNode.forward[i];

}

while (listLevel > 0 && listHead.forward[listLevel - 1] == NIL) {

listLevel--;

}

}

}

private int randomLevel() {

int lvl = 1;

while (lvl

lvl++;

}

return lvl;

}

public void print() {

for (int i = listLevel - 1; i >= 0; i--) {

SkipListNode curNode = listHead.forward[i];

while (curNode != NIL) {

curNode = curNode.forward[i];

}

}

}

public static void main(String[] args) {

SkipList sl = new SkipList();

sl.insert(20, 20);

sl.insert(5, 5);

sl.insert(10, 10);

sl.insert(1, 1);

sl.insert(100, 100);

sl.insert(80, 80);

sl.insert(60, 60);

sl.insert(30, 30);

sl.print();

sl.delete(20);

sl.delete(100);

sl.print();

}

}