数据结构
21 分钟 读完 (大约 3179 个字)

跳表SkipList

跳表介绍

目前经常使用的平衡数据结构有：B树，红黑树，AVL树，Splay Tree, Treep等。
跳表是一种随机化的数据结构，目前开源软件Redis和LevelDB都有用到它，它的效率和红黑树以及AVL树不相上下，但跳表的原理相当简单，只要你能熟练操作链表，就能轻松实现一个 SkipList。
这是跳表的作者，上面介绍的William Pugh给出的解释。

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.

跳表是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，这样也就是说跳表的插入和删除的工作是比较简单的。

跳表核心思想


从该有序表中搜索元素“23,43,59”，需要比较的次数分别为<2, 4, 6>，总共比较的次数为2 + 4 + 6 = 12次。有没有优化的算法吗? 链表是有序的，但不能使用二分查找。类似二叉搜索树，把一些节点提取出来，作为索引。得到如下结构。

把“14,34,50,72”提取出来作为一级索引，这样搜索的时候就可以减少比较次数了。还可以再从一级索引提取一些元素出来，作为二级索引，变成如下结构。

如果是说链表是排序的，并且节点中还存储指向前面第二个节点的指针的话，那么在查找一个节点时，仅仅需要遍历N/2个节点即可。
这基本上就是跳表的核心思想，其实也是一种通过“空间来换取时间”的一个算法，通过在每个节点中增加了向前的指针，从而提升查找的效率。

存储模式

-1表示INT_MIN，链表的最小值。1表示INT_MAX，链表的最大值。

性质

  1. 由很多层结构组成。
  2. 每一层都是一个有序的链表。
  3. 最底层(Level 1)的链表包含所有元素。
  4. 如果一个元素出现在Level i的链表中，则它在Level i之下的链表也都会出现。
  5. 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

    结构设计

    如果一个跳表的层MaxLevel义为跳表中所有节点中最大的层数。

    定义每个节点类型 
    1
    2
    3
    4
    5
    6
    7
    8
    typedef struct nodeStructure *node;
    typedef struct nodeStructure
    {
        keyType key; // key值
        valueType value; // value值
        // 向前指针数组，根据该节点层数的不同，指向不同大小的数组
        node forward[1];
    };


上面的每个结构体对应着图中的每个节点，如果一个节点是一层的节点的话（如7，12等节点），那么对应的forward将指向一个只含一个元素的数组，以此类推。
定义跳表数据类型

1
2
3
4
typedef struct listStructure{
   int level;    /* Maximum level of the list  (1 more than the number of levels in the list) */
   struct nodeStructure * header; /* pointer to header */
} * list;

跳表数据类型中包含了维护跳表的必要信息，level表明跳表的层数，header如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#define MaxNumberOfLevels 16  
#define MaxLevel (MaxNumberOfLevels-1) //NIL变量：node NIL;
#define newNodeOfLevel(l) (node)malloc(sizeof(struct nodeStructure)+(l)*sizeof(node *)) // newNodeOfLevel生成一个nodeStructure结构体，同时生成l个node *数组指针
``` 
# 操作
## 搜索
![](./skiplist-8.jpg)
例子：查找元素 117
1. 比较21，比21大，往后面找。
2. 比较37，比37大，比链表最大值小，从37的下面一层开始找。
3. 比较71，比71大，比链表最大值小，从71的下面一层开始找。
4. 比较85，比85大，从后面找。
5. 比较117，等于117，找到了节点。

伪代码搜索算法如下。

/* 如果存在 x, 返回 x 所在的节点，

  • 否则返回 x 的后继节点 */
    find(x)
    {
    p = top;
    while (1) { 
    while (p->next->key < x)  
    p = p->next;  
if (p->down == NULL)   
    return p->next;  
p = p->down;
    }
    } 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    ## 插入
    先确定该元素要占据的层数K（采用随机方式，这完全是随机的）。然后在`Level 1 ... Level K`各个层的链表都插入元素。  
    例子：插入119，K = 2  
    ![](./skiplist-9.jpg)
    如果K大于链表的层数，则要添加新的层。  
    例子：插入 119， K = 4  
    ![](./skiplist-10.jpg)
    ### K取值
    插入元素的时候，元素所占有的层数完全是随机的，通过一下随机算法产生。
    ``` c++
    int random_level()  
    {  
        K = 1;
        while (random(0,1))  
            K++;  
        return K;  
    }

显然随机变量K满足参数为p = 1/2的几何分布，K的期望值E[K] = 1/p = 2，各个元素的层数，期望值是2层。

高度

n个元素的跳表，每个元素插入的时候都要检查，用来决定元素占据的层数K，跳表的高度等于这n次检查生成中产生的最大K。

空间复杂度

根据上面的分析，每个元素的期望高度为2， 一个大小为n的跳表，其节点数目的期望值是2n。

删除

在各个层中找到包含x的节点，使用标准的delete from list删除该节点。
例子：删除71

代码

Java

跳表节点类型，每个跳表类型中仅仅存储左侧的节点和下面的节点。

  • 完成初始化
  • 插入操作：和上面介绍的插入操作是类似的，首先查找到插入的位置，生成update数组，然后随机生成一个level，然后修改指针。
  • 删除操作：和上面介绍的删除操作是类似的，查找到需要删除的节点，如果查找不到，抛出异常，如果查找到的需要删除的节点的话，修改指针，释放删除节点的内存。

SkipNode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package demo1;


class SkipNode<E extends Comparable<? super E>> {
	public final E value; // 节点存储的数据
	public final SkipNode<E>[] forward; // 节点的指针数组

	/**
	 * 根据节点的层级构造一个节点
	 * 
	 * @param level
	 *            节点层级
	 * @param value
	 *            节点存储值
	 */
	@SuppressWarnings("unchecked")
	public SkipNode(int level, E value) {
		forward = new SkipNode[level + 1];// level层的元素后面带着level+1的指针数组
		this.value = value;
	}

}

SkipSet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
package demo1;


public class SkipSet<E extends Comparable<? super E>> {
	/**
	 * 概率因子，实验证明p=1/e比p=0.5要好，e是个神奇的数字！
	 */
	// public static final double P = 0.5;
	public static final double P = 1 / Math.E;
	/**
	 * 最大层级
	 */
	public static final int MAX_LEVEL = 6;
	/**
	 * 开始节点，不存值，贯穿所有层
	 */
	public final SkipNode<E> header = new SkipNode<E>(MAX_LEVEL, null);
	/**
	 * 当前跳表的最高层级
	 */
	public int level = 0;

	/**
	 * 插入一个元素
	 * 
	 * @param value
	 *            待插入值
	 */
	@SuppressWarnings("unchecked")
	public void insert(E value) {
		SkipNode<E> x = header;
        //节点所有层更新的数组
		SkipNode<E>[] update = new SkipNode[MAX_LEVEL + 1];
		for (int i = level; i >= 0; i--) {
			while (x.forward[i] != null && x.forward[i].value.compareTo(value) < 0) {
				x = x.forward[i];
			}
			// update[i]是比value小的数里面最大的，是value的前置节点
			update[i] = x;
		}
		x = x.forward[0];
		// 此处不允许插入相同元素，为一个set
		// 跳表中不包含所要插的元素
		if (x == null || !x.value.equals(value)) {
			// 随机产生插入的层级
			int lvl = randomLevel();
			// 产生的随机层级比当前跳表的最高层级大，需要添加相应的层级，并更新最高层级
			if (lvl > level) {
				for (int i = level + 1; i <= lvl; i++) {
					update[i] = header;
				}
				level = lvl;
			}
			// 生成新节点
			x = new SkipNode<E>(lvl, value);
			// 调整节点的指针，和指向它的指针
			for (int i = 0; i <= lvl; i++) {
				x.forward[i] = update[i].forward[i];
				update[i].forward[i] = x;
			}
		}
	}

	/**
	 * 删除一个元素
	 * 
	 * @param value
	 *            待删除值
	 */
	@SuppressWarnings("unchecked")
	public void delete(E value) {
		SkipNode<E> x = header;
		SkipNode<E>[] update = new SkipNode[MAX_LEVEL + 1];
		for (int i = level; i >= 0; i--) {
			while (x.forward[i] != null && x.forward[i].value.compareTo(value) < 0) {
				x = x.forward[i];
			}
			update[i] = x;
		}
		x = x.forward[0];
		// 删除元素，调整指针
		if (x.value.equals(value)) {
			for (int i = 0; i <= level; i++) {
				if (update[i].forward[i] != x)
					break;
				update[i].forward[i] = x.forward[i];
			}
			// 如果元素为本层最后一个元素，则删除同时降低当前层级
			while (level > 0 && header.forward[level] == null) {
				level--;
			}
		}
	}

	/**
	 * 查找是否包含此元素
	 * 
	 * @param searchValue
	 *            带查找值
	 * @return true：包含；false:不包含
	 */
	public boolean contains(E searchValue) {
		SkipNode<E> x = header;
		// 从开始节点的最高层级开始查找
		for (int i = level; i >= 0; i--) {
			// 当到达本层级的NULL节点或者遇到比查找值大的节点时，转到下一层级查找
			while (x.forward[i] != null && x.forward[i].value.compareTo(searchValue) < 0) {
				x = x.forward[i];
			}
		}
		x = x.forward[0];
		// 此时x有三种可能，1.x=null,2.x.value=searchValue,3.x.value>searchValue
		return x != null && x.value.equals(searchValue);
	}

	/**
	 * 这里是跳表的精髓所在，通过随机概率来判断节点的层级
	 * 
	 * @return 节点的层级
	 */
	public static int randomLevel() {
		int lvl = (int) (Math.log(1. - Math.random()) / Math.log(1. - P));
		return Math.min(lvl, MAX_LEVEL);
	}

	/**
	 * 输出跳表的所有元素 遍历最底层的元素即可
	 */
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("{");
		SkipNode<E> x = header.forward[0];
		while (x != null) {
			sb.append(x.value);
			x = x.forward[0];
			if (x != null) {
				sb.append(",");
			}
		}
		sb.append("}");
		return sb.toString();
	}
}

Test1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package demo1;

public class Test1 {
	public static void main(String[] args) {
		SkipSet skipSet=new SkipSet<>();
		skipSet.insert(1);
		skipSet.insert(7);
		skipSet.insert(14);
		skipSet.insert(21);
		skipSet.insert(32);
		skipSet.insert(37);
		skipSet.insert(71);
		skipSet.insert(85);
		skipSet.insert(117);
		System.out.println(skipSet.toString());
	}
}

1
{1,7,14,21,32,37,71,85,117}

C++

初始化

初始化的过程很简单，仅仅是生成下图中红线区域内的部分，也就是跳表的基础结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
list newList()
{
  list list1;
  int i;
  // 申请list类型大小的内存
  list1 = (list)malloc(sizeof(struct listStructure));
  // 设置跳表的层level，初始的层为0层（数组从0开始）
  list1->level = 0;
  // 生成header部分
  list1->header = newNodeOfLevel(MaxNumberOfLevels);
  // 将header的forward数组清空
  for(i=0;i<MaxNumberOfLevels;i++) list1->header->forward[i] = NIL;
  return(list1);
};

插入

由于跳表数据结构整体上是有序的，所以在插入时，需要首先查找到合适的位置，然后就是修改指针（和链表中操作类似），然后更新跳表的level变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
boolean insert(l,key,value) 
register list l;
register keyType key;
register valueType value;
{
	  register int k;
	  // 使用了update数组
	  node update[MaxNumberOfLevels];
	  register node p,q;
	  p = l->header;
	  k = l->level;
	  /*******************1步*********************/
	  do {
	    // 查找插入位置
	    while (q = p->forward[k], q->key < key)
	    p = q;
	    // 设置update数组
	    update[k] = p;
	  } while(--k>=0); // 对于每一层进行遍历
	  // 这里已经查找到了合适的位置，并且update数组已经
	  // 填充好了元素
	  if (q->key == key)
	  {
		q->value = value;
		return(false);
	  };
	  // 随机生成一个层数
	  k = randomLevel();  
	  if (k>l->level) 
	  {
		// 如果新生成的层数比跳表的层数大的话
		// 增加整个跳表的层数
		k = ++l->level;
		// 在update数组中将新添加的层指向l->header
		update[k] = l->header;
	  };
	  /*******************2步*********************/
	  // 生成层数个节点数目
	  q = newNodeOfLevel(k);
	  q->key = key;
	  q->value = value;  
	  // 更新两个指针域
	  do 
	  {
		p = update[k];
		q->forward[k] = p->forward[k];
		p->forward[k] = q;
	  } while(--k>=0);
	  // 如果程序运行到这里，程序已经插入了该节点
	  return(true);
}

删除

和插入是相同的，首先查找需要删除的节点，如果找到了该节点的话，那么只需要更新指针域，如果跳表的level需要更新的话，进行更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
boolean delete(list1,key) 
register list list1;
register keyType key;
{
  register int k,m;
  // 生成一个辅助数组update
  node update[MaxNumberOfLevels];
  register node p,q;
  p = list1->header;
  k = m = list1->level;
  // 这里和查找部分类似，最终update中包含的是：
  // 指向该节点对应层的前驱节点
  do 
  {
     while (q = p->forward[k], q->key < key) 
     p = q;
     update[k] = p;
  } while(--k>=0);
  // 如果找到了该节点，才进行删除的动作
  if (q->key == key) 
  {
   // 指针运算
   for(k=0; k<=m && (p=update[k])->forward[k] == q; k++) 
   // 这里可能修改l->header->forward数组的值的 
   p->forward[k] = q->forward[k];
   // 释放实际内存
   free(q);
   // 如果删除的是最大层的节点，那么需要重新维护跳表的
   // 层数level
   while( list1->header->forward[m] == NIL && m > 0 ){
     m--;
   }
   list1->level = m;
   return(true);
  }
  else
  {
    // 没有找到该节点，不进行删除动作 
    return(false);
  }
}

# 数据结构, 跳表

喜欢这篇文章？打赏一下作者吧

Java序列化和反序列化
中缀表达式转换为后缀表达式

评论

关注我

链接

分类

标签云

Android Centos Effect Java JDK6 源码 JDK7 源码 JDK8 源码 JMM JVM Java Linux MongoDB Mongodb MyBatis MySQL Redis Spring Think In Java Tomcat Ubuntu 一致性哈希算法 书 倒排索引 内存泄漏 分支限界算法 分治法 分治算法 分词算法 动态规划 动态规划算法 华为 回溯算法 多线程 工具 并发 开源项目 手机游戏 排序算法 推荐 散列表 数学 数据库 数据结构 日语 最优路径算法 机器学习 源码 算法 线程安全 编程珠玑 计算机基础 设计模式 贪心算法 跳表 面试

最新文章

归档

标签

Android 1
Centos 3
Effect Java 2
JDK6 源码 18
JDK7 源码 6
JDK8 源码 1
JMM 7
JVM 10
Java 40
Linux 4
MongoDB 1
Mongodb 1
MyBatis 3
MySQL 2
Redis 1
Spring 4
Think In Java 1
Tomcat 7
Ubuntu 1
一致性哈希算法 1
书 3
倒排索引 1
内存泄漏 1
分支限界算法 2
分治法 1
分治算法 1
分词算法 2
动态规划 1
动态规划算法 2
华为 1
回溯算法 4
多线程 2
工具 1
并发 5
开源项目 17
手机游戏 1
排序算法 1
推荐 1
散列表 1
数学 1
数据库 2
数据结构 5
日语 1
最优路径算法 1
机器学习 1
源码 3
算法 26
线程安全 2
编程珠玑 3
计算机基础 1
设计模式 4
贪心算法 3
跳表 1
面试 1

最新文章

归档

标签

Android 1
Centos 3
Effect Java 2
JDK6 源码 18
JDK7 源码 6
JDK8 源码 1
JMM 7
JVM 10
Java 40
Linux 4
MongoDB 1
Mongodb 1
MyBatis 3
MySQL 2
Redis 1
Spring 4
Think In Java 1
Tomcat 7
Ubuntu 1
一致性哈希算法 1
书 3
倒排索引 1
内存泄漏 1
分支限界算法 2
分治法 1
分治算法 1
分词算法 2
动态规划 1
动态规划算法 2
华为 1
回溯算法 4
多线程 2
工具 1
并发 5
开源项目 17
手机游戏 1
排序算法 1
推荐 1
散列表 1
数学 1
数据库 2
数据结构 5
日语 1
最优路径算法 1
机器学习 1
源码 3
算法 26
线程安全 2
编程珠玑 3
计算机基础 1
设计模式 4
贪心算法 3
跳表 1
面试 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×