跳跃表学习笔记

跳跃表学习笔记

跳跃表(Skip List),是一种基于概率,提供了查找、插入、删除近似于O(logN)性能的数据结构。

这篇文章是学习跳跃表的一个记录,包含了跳跃表的原理以及其Java实现

介绍

跳跃表(Skip List),是一种基于概率,提供了查找、插入、删除近似于O(logN)性能的数据结构。

在线性数据结构中,查找、插入、删除性能均为O(N),当数据量比较大的时候,是非常不乐观的,因此,科学家们相处了各种各样的数据结构来进行优化,将线性的数据结构进行一系列转换,从而得到在理想情况下查找、插入、删除性能均为或近似为O(logN)的数据结构,前面提到的AVL、红黑树是通过平衡(旋转、变色)等将线性数据结构转换为平衡树,从而利用平衡树的特性来实现O(logN)的复杂度

除了平衡树之外,还有另外一种数据结构,跳跃表,采取另类的思路来实现同样的性能优化,平衡树等牺牲的是部分的操作性能,而跳跃表牺牲的则是空间

跳跃表可以达到与红黑树等类似的性能,并且实现起来相对简单,虽然消耗部分空间,但也具有一定的应用场景,例如redis中的sorted set、Java中的ConcurrentSkipListMap就是通过跳跃表来实现的

原理

跳跃表本质上是基于链表,并且跳跃表中的元素是有序的(默认根据key递减)

传统的链表查找、插入、删除操作都是O(N),跳跃表对其进行了优化,为原来的链表建立多个层次(基于概率函数)的索引,每个层次的索引依次递减(通过概率来控制,而非严格的数量关系),从而建立了一个基于链表的性能卓越的跳跃表数据结构,如下图所示:

跳跃表

最底层黄色的节点是实际上真正的数据节点,从最底层往上的每一个层次都是下一个层次的索引

查找节点

在查找的时候,从最head节点出发,在最顶层开始往右边查找,直到第一个不小于目标值的节点出现,说明目标节点位于当前节点区间,从上图中也可以看到,最顶层的索引是非常稀疏的,所以最上层节点的查找速度是非常快的,然后从当前节点往下一层次查找,重复上述步骤,直到到达最底层

举个栗子:查找节点8

1
2
3
4
1. head的最顶层(第4层)出发,此时已经到达第四层的末尾处
2. 从第3层出发,1<8,4<8,6<8,此时已经到达第三层的末尾处
3. 从第二层key为6的节点出发,9>8,继续往下一层查找
4. 从第一层key为6的节点出发,6<8,7<8,8=8,找到目标节点

可以看到,此时仅仅需要4次查找,而链表本身的长度为10

插入节点

插入节点的前部分操作与查找节点一样,先找到离目标节点最近的节点(目标节点或前一个节点),然后插入目标节点,根据概率函数,计算当前节点应该所占有的层次,然后依次补充将每个层次对应的索引链表连接起来(普通的链表插入操作)

跳跃表插入节点

具体插入步骤参见上图

删除节点

删除节点的操作步骤与插入节点类似,只是现在是找到之后,将其从各个层次的索引链表中删除(普通的链表删除操作)

注:以上所有的图片均来自维基百科-跳跃表介绍

实现

从上面的描述以及图片示例,大致上已经能够猜测出实现的代码结构了

ListNode

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
static class ListNode {
// key
private final String key;

private String value;

// 当前节点的层次数,由random函数生成
private Integer level;

private final ListNode[] nexts;

public ListNode(String key, String value, Integer level) {
this.key = key;
this.value = value;
this.level = level;
this.nexts = new ListNode[level];
}

@Override
public String toString() {
return "ListNode{" +
"key='" + key + '\'' +
", value='" + value + '\'' +
", level=" + level +
'}';
}
}

SimpleSkipList

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
/**
* @author huanfeng
*/
public class SimpleSkipList {

// 节点的最高层次数
private static final int MAX_LEVEL = 16;

// 控制每一层的概率
private static final double RATE = 0.25;

// 跳跃表的头结点,该节点是空节点
private ListNode head = new ListNode(null, null, MAX_LEVEL);

private int size = 1;

private Random random = new Random();

private Integer randomLevel() {
int level = 1;
while (level < MAX_LEVEL &&
Double.compare(random.nextDouble(), RATE) < 0) {
level++;
}
return level;
}
}

get:获取元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode get(String key) {
ListNode preNode = head;
int level = preNode.level;

// 注意这里查找出来的是目标key的前一个节点
// 从最高一层的索引链表往后、下查找
for (int i = level - 1; i >= 0; i--) {
// 判断next.val是否小于当前的key
while (preNode.nexts[i] != null &&
preNode.nexts[i].key.compareTo(key) < 0) {
preNode = preNode.nexts[i];
}
// 往下一层继续查找
}

// 如果前一个元素存在,并且其next的key等于目标key,说明我们找到了
if (preNode.nexts[0] != null &&
preNode.nexts[0].key.compareTo(key) == 0) {
return preNode.nexts[0];
}
return null;
}

put:添加元素

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
public void put(String key, String value) {
ListNode preNode = head;

// 先查找看是否存在,存在则替换
ListNode currentNode = get(key);
if (currentNode != null && currentNode.key.compareTo(key) == 0) {
currentNode.value = value;
return;
}

int level = randomLevel();

ListNode[] nextHolder = new ListNode[level];

// 默认新插入的节点都由head指向,并且指向head.next
// eg:
// next = head.next
// head -> newNode -> next
for (int i = 0; i < level; i++) {
nextHolder[i] = head;
}

for (int i = level - 1; i >= 0; i--) {
while (preNode.nexts[i] != null &&
preNode.nexts[i].key.compareTo(key) < 0) {
preNode = preNode.nexts[i];
}
// 获取当前层次的next
nextHolder[i] = preNode;
}

ListNode newNode = new ListNode(key, value, level);

for (int i = 0; i < level; i++) {
// 将当前节点插入到所有层次中
// node的第i层的next = 目标节点的i层的next
newNode.nexts[i] = nextHolder[i].nexts[i];
// 目标节点的i层的next指向当前的node
nextHolder[i].nexts[i] = newNode;
}

head.level = Math.max(level, head.level);
size++;
}

remove

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
public ListNode remove(String key) {

ListNode preNode = head;
int level = preNode.level;

ListNode[] nextHolder = new ListNode[level];

for (int i = level - 1; i >= 0; i--) {
while (preNode.nexts[i] != null &&
preNode.nexts[i].key.compareTo(key) < 0) {
preNode = preNode.nexts[i];
}
nextHolder[i] = preNode;
}

// 找不到
if (preNode.nexts[0] == null ||
preNode.nexts[0].key.compareTo(key) != 0) {
return null;
}

// 注意这里的步骤是必须的,因为跳跃表的level是随机的
// 因此,不是preNode的每一层的next都是指向目标节点
for (int i = level - 1; i >= 0; i--) {
if (nextHolder[i].nexts[i] != null &&
nextHolder[i].nexts[i].key.compareTo(key) == 0) {
nextHolder[i].nexts[i] = nextHolder[i].nexts[i].nexts[i];
}
}
return preNode.nexts[0];
}