这次讲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();
}
}
领取专属 10元无门槛券
私享最新 技术干货