站点图标

浅谈跳表

2019-09-14折腾记录浅谈 / 数据结构
本文最后更新于 607 天前,文中所描述的信息可能已发生改变

为什么使用跳表

**跳表是(skip list)**Redis 实现 sorted set 使用的数据结构,是一种平衡数据结构,其中常用的数据结构有:B 树,AVL 树,红黑树等,如果你了解过这些平衡结构,你或许会有个疑问,为什么要使用跳表?想象一下,给你一支笔,一张纸,一个编辑器或者 IDE,你能在短时间内写出一个红黑树或者 AVL 树?这很难吧。而跳表,我们只需要对链表稍加改造就可以支持快速增删改查,使用类似于二分搜索的查找算法,而这种数据结构就是跳表。它的效率和红黑树以及 AVL 树不相上下。

什么是跳表

首先我们先来看一个链表:

91c27188 a379 4167 bd86 74520148dcda

对于这种链表来说,即使链表之中是有序的,如果我们要从中查找某个值,也只能从头逐个查找,运气好的话查找一次就能找到,运气差的话或许要查找 n 次。在使用数组存储的方式中我们可以通过二分搜索来快速的查找某个值,而链表由于不支持随机查询,所以就不能使用二分搜索的方式来查找。

那么如何能提高查找效率呢?在 O(n)的时间复杂度下如果要提高运行效率,二分是必不可少的,树结构可以通过左右子树来分区,那链表又如何分区呢?建立索引,我们对这个链表加上一层索引。

76327415 551c 4652 a2d1 f25edaf1f5c8

假如我们要查找 6,只需要走 1->3->5->6,减少了 2 步,那如果我们再加几层索引呢?

f63d447e a72e 42fe b15c 252f387ab57d

这时的查找其实就是二分查找了,查找效率已经有质的提升。而这种的原理其实很简单就是通过分区来跳过大量的节点。


上面所说的结构是静态的,当我们向上方的跳表中不断加入数据,如果不更新索引就有可能出现某节点之间出现大量节点的情况,在极端的情况下还会退化成链表。而如果在插入的时候重建索引那势必会导致跳表的插入效率大幅下降。那要如何解决动态插入的问题呢?在红黑树和 AVL 树中是使用左右旋来平衡二叉树,而跳表同样也有一种机制来平衡:通过随机函数来是插入的节点的层高是随机的,不强制要求 1:2 的分区。如,我们要在以下的跳表中添加一个值为 18 的节点:

73bb37f0 6a78 4710 8046 3b428bc46ac1

首先我们需要通过一个随机函数来得出新节点的层高。假设在这次插入中得到的层高是 3


_9
public int randomLevel() {
_9
int level = 1;
_9
for (int i = 1; i < this.maxLevel; ++i) {
_9
if (this.r.nextInt() % 2 == 1) {
_9
level++;
_9
}
_9
}
_9
return level;
_9
}

然后搜索到插入的位置。

cb0a8b0c 4b58 4194 aa24 831ed4d8b64f

最后将节点插入并重新设置指针,从上一张图中我们可以看到游标走了所有的层,而游标在游走的时候就可以记录层信息,就可以重设指针了。

30aea029 03f7 4379 aed3 e530f12ad283

简单分析跳表效率

从上面图中我们可以知道,大致每两个结点会抽出一个结点作为上一级索引的结点,那第一级索引的结点个数大约就是 n/2,第二级索引的结点个数大约就是 n/4,也就是说,第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2,第 k索引结点的个数就是 n/(2k)。那么假设层数足够高,即最高层只有两个节点,那么可知 n/(2k)=2,即 k=log2n-1,若把原始链表计算在内那 k=logn,若每次查找都要下降 m 层的时候,那在跳表中查询一个数据的时间复杂度就是 O(m*logn)。而 m 可以认为是参数,所以跳表查询一个数据的时间复杂度就为 O(logn)。

说完时间,那么我们来说说空间,比起链表和二叉树,跳表需要多个指针域,肯定需要比链表和二叉树多许多空间。若我们两个节点就提升一层,那需要的索引数量就为 n/2+n/4+n/8+…+2,即 n-2,所以可以知道跳表所用的空间复杂度为 O(n),看起来似乎很大?但是我们需要考虑原始链表中数据存储的大小,若数据的大小很大,那么索引使用的空间就微不足道了。

实现代码

忘记附上代码了,逃


_187
package MySkipListDemo;
_187
_187
import java.lang.reflect.Array;
_187
import java.util.Random;
_187
import java.util.Scanner;
_187
_187
/**
_187
* MySkipListDemo
_187
*/
_187
public class MySkipListDemo {
_187
public static void main(String[] args) {
_187
Scanner in = new Scanner(System.in);
_187
// SkipList list = new SkipList();
_187
MySkipList<Integer, Integer> list = new MySkipList<Integer, Integer>();
_187
list.insert(3, 3);
_187
list.insert(1, 1);
_187
list.insert(2, 2);
_187
list.insert(4, 4);
_187
list.insert(15, 15);
_187
list.insert(5, 5);
_187
list.insert(6, 6);
_187
list.insert(16, 16);
_187
list.insert(17, 17);
_187
list.insert(7, 7);
_187
list.insert(8, 8);
_187
list.insert(9, 9);
_187
list.insert(13, 13);
_187
list.insert(10, 10);
_187
list.insert(11, 11);
_187
list.insert(20, 20);
_187
list.insert(12, 12);
_187
list.insert(15, 15);
_187
list.insert(18, 18);
_187
list.insert(19, 19);
_187
list.remove(1, 1);
_187
list.remove(10, 10);
_187
list.remove(20, 20);
_187
list.printAll();
_187
in.close();
_187
}
_187
}
_187
_187
/**
_187
* MySkipList
_187
*/
_187
class MySkipList<K extends Comparable<K>, V extends Comparable<V>> {
_187
int maxLevel = 16;
_187
int currLevel = 0;
_187
boolean keySort = true;
_187
boolean isMax = false;
_187
_187
Node head = null;
_187
_187
private Random r = new Random();
_187
_187
class Node {
_187
Node[] next;
_187
K key;
_187
V value;
_187
int level;
_187
_187
Node() {
_187
}
_187
_187
@SuppressWarnings("unchecked")
_187
Node(K key, V value, int level) {
_187
this.next = (Node[]) Array.newInstance(Node.class, level);
_187
this.key = key;
_187
this.value = value;
_187
this.level = level;
_187
}
_187
_187
public String toString() {
_187
return "[" + key + "," + value + "](" + level + ")";
_187
}
_187
}
_187
_187
MySkipList() {
_187
}
_187
_187
MySkipList(int maxLevel, boolean keySort, boolean isMax) {
_187
this.maxLevel = maxLevel;
_187
this.isMax = isMax;
_187
this.keySort = keySort;
_187
}
_187
_187
public int randomLevel() {
_187
int level = 1;
_187
for (int i = 1; i < this.maxLevel; ++i) {
_187
if (this.r.nextInt() % 2 == 1) {
_187
level++;
_187
}
_187
}
_187
return level;
_187
}
_187
_187
public void insert(K key, V value) {
_187
this.add(key, value);
_187
}
_187
_187
@SuppressWarnings("unchecked")
_187
public void add(K key, V value) {
_187
if (this.head == null) {
_187
head = new Node(key, value, maxLevel);
_187
return;
_187
}
_187
if (this.head.key.compareTo(key) == (this.isMax ? -1 : 1)) {
_187
K tempKey = head.key;
_187
V tempValue = head.value;
_187
head.value = value;
_187
head.key = key;
_187
value = tempValue;
_187
key = tempKey;
_187
}
_187
int level = this.randomLevel();
_187
Node p = head;
_187
Node update[] = (Node[]) Array.newInstance(Node.class, level);
_187
Node newNode = new Node(key, value, level);
_187
for (int i = level - 1; i >= 0; i--) {
_187
while (p.next[i] != null && p.next[i].key.compareTo(key) == (this.isMax ? 1 : -1)) {
_187
p = p.next[i];
_187
}
_187
update[i] = p;
_187
}
_187
for (int i = 0; i < level; ++i) {
_187
newNode.next[i] = update[i].next[i];
_187
update[i].next[i] = newNode;
_187
}
_187
_187
if (currLevel < level)
_187
currLevel = level;
_187
}
_187
_187
@SuppressWarnings("unchecked")
_187
public void remove(K key, V value) {
_187
Node p = head;
_187
if (p.key.compareTo(key) == 0) {
_187
head.key = head.next[0].key;
_187
head.value = head.next[0].value;
_187
Node rNode = head.next[0];
_187
for (int i = 0; i < rNode.level; i++) {
_187
head.next[i] = rNode.next[i];
_187
}
_187
return;
_187
}
_187
Node update[] = (Node[]) Array.newInstance(Node.class, p.level);
_187
for (int i = p.level - 1; i >= 0; i--) {
_187
while (p.next[i] != null && p.next[i].key.compareTo(key) == (this.isMax ? 1 : -1)) {
_187
p = p.next[i];
_187
}
_187
update[i] = p;
_187
}
_187
if (p.next[0] != null && p.next[0].value.compareTo(value) == 0) {
_187
Node rNode = p.next[0];
_187
for (int i = 0; i < rNode.level; i++) {
_187
update[i].next[i] = rNode.next[i];
_187
}
_187
}
_187
}
_187
_187
public Node search(K key, V value) {
_187
Node p = head;
_187
if (p.key.compareTo(key) == (this.isMax ? -1 : 1)) {
_187
return null;
_187
} else if (p.key.compareTo(key) == 0) {
_187
return p;
_187
}
_187
for (int i = p.level - 1; i >= 0; i--) {
_187
while (p.next[i] != null && p.next[i].key.compareTo(key) == (this.isMax ? 1 : -1)) {
_187
p = p.next[i];
_187
}
_187
}
_187
if (p.next[0] != null && p.next[0].value.compareTo(value) == 0) {
_187
return p.next[0];
_187
} else {
_187
return null;
_187
}
_187
}
_187
_187
public void printAll() {
_187
Node p = head;
_187
while (p != null) {
_187
System.out.println(p);
_187
p = p.next[0];
_187
}
_187
}
_187
}

结语

跳表的时间复杂度是 O(logn),空间复杂度是 O(n),虽然不如平衡树来的“高效”,但是跳表的实现非常灵活,可以有效的平衡执行效率和内存消耗,并且实现起来也比平衡树容易,所以多数情况下跳表会是比平衡树更好的选择。

浅谈跳表

https://blog.ixk.me/post/talking-about-skip-list
  • 许可协议

    BY-NC-SA

  • 发布于

    2019-09-14

  • 本文作者

    Otstar Lin

转载或引用本文时请遵守许可协议,注明出处、不得用于商业用途!

浅谈B+树浅谈数据库索引