跳表的介绍与实现

背景

我们现在要实现一种数据结构，可以实现较为快速的 插入、删除、查询 操作。

显然每次暴力 O(n)O(n) 操作并不可取，我们第一眼就想到了比如 红黑树、Splay、Treap 这样的 平衡树 结构来实现。

最近我发现一种数据结构 —— 跳表，它基于链表建立多层索引来实现快速操作。

原本我以为这玩意儿形同鸡肋，但是了解到其在 Redis、LevelDB、ES 中都有应用，了解过后，发现其确实有可取之处。

介绍

首先对于一段序列，我们可以用链表的形式储存，如果不进行任何其它设计，那么我们进行 插入、删除、查询 的操作，复杂度显然是 O(n)O(n) 的，因为我们基本需要遍历每一个节点。

现在我们引用多个 索引链表 来优化这个链表。

对于一个链表，我们这样构建它：

image-20210613003910137

原本的链表是：1→2→3→4→5，我们现在将其中的 某几个（后面会介绍如何确定） 节点，放到上一层链表中（即上一层索引中），构建出了一个新链表： 1→3→5，对于 1→3→5 ，我们再将其中某几个节点继续放到上一层中，构建出 3→5。

对于这样一个结构，我们就可以快速地实现一些操作。

比如我们现在要查询 4 是否存在：

  1. 在最高层索引中（即第二层索引）中，找到 该层中最后一个比 4 小的值，这里也就是 3 ；
  2. 进入 3 的低一层索引（即第一层索引）的位置，发现这一层 3 后面的值还是 5，那么 3 依然是 该层最后一个比 4 小的元素；
  3. 我们依然从 3 进入低一层索引（即原链表），发现 3 后面的值是 4，那么 4 就存在；假设这里后面依然是 5，那比 4 大，并且我们当前已经在最底层的链表了，也就是说不存在 4。

时间复杂度

我们考虑一下需要遍历的节点，显然是上一层的某些节点，加上下一层往后的节点（红色为走的节点）：

image-20210613021317589

我们现在有 一种直观的策略： 假设，一层的个数为 nn，每距离 n\sqrt{n} 个节点将其放到上一层中，对于每一层如此操作，显然这样对于每一次操作可以做到 O(n)O(\sqrt{n}) 的复杂度。

事实上，我们可以用一种更优秀的策略确定 某几个 放到上一层，到底是哪些节点该往上放。

新的策略 ： 对于一层的节点，我们以一个 随机的概率 P 来决定是否将它往上一层放，当前 Redis 中将 P 设置为 0.250.25 （旧版本为 0.50.5 ）。可以证明这样进行一次操作的复杂度是 O(logn)O(log_n) 左右的，确实比较优秀。

为了防止某些情况以及方便实现，我们在一开始就确定这个跳表的最高层数 MAXLEVEL，当前 Redis 中的最高层数为 6464 （旧版本为 3232 ）。

实现

对于这个 跳表 我们要怎么实现呢，我们可以稍微改一下上面的图，来更加直观的理解：

image-20210613012035980

对于每一个节点，我们分别记录：keykey 、 forward[]forward[] ，其中 keykey 表示这个节点的值， forward[i]forward[i] 表示这个节点在第 ii 层（记原链表为第 00 层）的后序节点。

当然，对于一开始我们需要一个 headerheader 节点，header→forward[i]header→forward[i] 用于表示第 ii 层的开始节点。

1
2
3
4
5
6
7
8
9
10
11
12
class Node
{
public:
	int key;
	vector <shared_ptr<Node>> forward;
	
	// 创建一个所在最高层为 level 的节点
	Node(int _key, int _level) : key(_key)
	{
		forward = vector<shared_ptr<Node>>(_level + 1);
	}
};

有了这些信息，我们就可以进行最基础的操作了。

查找

我们考虑查找一个值为 keykey 的节点。

从最高层级开始走，每次找到当前层最后一个值比 keykey 小的节点，然后从这个节点的位置进入下一层。

如此走完一遍后，找到的节点一定是比 keykey 小且最接近的。

如果这个点所在层不是原链表，我们从该节点往下跳到原链表的 这个节点所在的位置。那么当前位置的 后一个节点 的值才有可能是 keykey。当然，也有可能比 keykey 大，或者不存在后面的节点，这时候链表中就不存在值为 keykey 的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool Search(int key)
{
    shared_ptr<Node> cur = header;

    // 从最高层级开始走，找到当前层最后一个比 key 值小的节点
    for (int i = level; i >= 0; i--)
    {
        while (cur->forward[i] != nullptr && cur->forward[i]->key < key)
            cur = cur->forward[i];
    }

    // 跳转到原链表，然后往后一个位置
    cur = cur->forward[0];
    return cur != nullptr && cur->key == key;
}

插入

我们考虑插入一个值为 keykey 的节点。

显然，我们首先需要判断一下是否已经存在值为 keykey 的节点。

于是我们从最上层开始走，每次找到当前层最后一个值比 keykey 小的节点，然后从这个节点的位置进入下一层。在这个过程中，我们对于第 ii 层记录下这个节点 record[i]record[i]，方便后面的更新。

然后我们和 查找 操作一样，判断是否 keykey 已存在。如果存在则直接返回（或者进行你想要的操作，比如记录下出现 keykey 了几次，自己修改即可），如果不存在我们进行之后的插入。

我们按照之前的策略，为这个节点按生成一个随机的最高层数 rLevelrLevel。

对于 i∈[0,rLevel]i\in[0,rLevel] 层的 record[i]record[i]，显然我们现在要将它的后一个节点，设置成我们现在的节点。然后将现在节点的 forward[i]forward[i] 设为原本 record[i]record[i] 的 forward[i]forward[i]。

需要特别注意的是，如果 跳表当前的level<rLevel跳表当前的level < rLevel ，我们需要将 i∈(level,rLevel]i\in(level,rLevel] 的 header→forward[i]header→forward[i] 设为该节点，最后更新一下 levellevel。

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
void Insert(int key)
{
    auto record = vector<shared_ptr<Node>>(MAXLEVEL + 1);
    shared_ptr<Node> cur = header;

    for (int i = level; i >= 0; i--)
    {
        while (cur->forward[i] != nullptr && cur->forward[i]->key < key)
            cur = cur->forward[i];
        record[i] = cur;
    }
    cur = cur->forward[0];
    // 节点已存在则直接返回
    if (cur != nullptr && cur->key == key) return;

    // 创建一个新的节点 n 进行更新
    int rLevel = RandomLevel();
    shared_ptr<Node> n = make_shared<Node>(key, rLevel);
    for (int i = 0; i <= rLevel; i++)
    {
        if (i <= level)
        {
            n->forward[i] = record[i]->forward[i];
            record[i]->forward[i] = n;
        }
        else header->forward[i] = n;
    }

    level = max(level, rLevel);
}

删除

我们考虑删除一个值为 keykey 的节点。

我们从最上层开始走，每次找到当前层最后一个值比 keykey 小的节点，然后从这个节点的位置进入下一层。在这个过程中，我们对于第 ii 层记录下这个节点 record[i]record[i]，方便后面的更新。

然后我们跳转到原链表，判断一下是否存在值为 keykey 的节点，若存在我们假设它为 curcur。

我们从原链表开始一层一层往上走，进行删除。显然我们对于 record[i]→forward[i]record[i]→forward[i] 是 curcur 的节点，我们直接将 record[i]→forward[i]record[i]→forward[i] 设置为 cur→forward[i]cur→forward[i]；如果不是，则说明 curcur 并没有被上放到该层，可以停止操作。

然后释放 curcur 的资源。可能我们的删除会导致跳表 levellevel 的改变，更新一下 levellevel。

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
void Delete(int key)
{
    auto record = vector<shared_ptr<Node>>(MAXLEVEL + 1);
    shared_ptr<Node> cur = header;

    for (int i = level; i >= 0; i--)
    {
        while (cur->forward[i] != nullptr && cur->forward[i]->key < key)
        {
            cur = cur->forward[i];
        }
        record[i] = cur;
    }
    cur = cur->forward[0];
    // 节点不存在 或 值不为 key 则直接返回
    if (cur == nullptr || cur->key != key) return;

    for (int i = 0; i <= level; i++)
    {
        if (record[i]->forward[i] == nullptr || record[i]->forward[i]->key != key) break;
        record[i]->forward[i] = cur->forward[i];
    }

    // 更新 level
    while (header->forward[level] == nullptr && level > 0)
        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
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <bits/stdc++.h>
using namespace std;

class Node
{
public:
	int key;
	vector <shared_ptr<Node>> forward;
	
	// 创建一个所在最高层为 level 的节点
	Node(int _key, int _level) : key(_key)
	{
		forward = vector<shared_ptr<Node>>(_level + 1);
	}
};

class SkipList
{
private:
	shared_ptr<Node> header;
	int MAXLEVEL;
	float P;

	// 跳表当前的层数
	int level;

public:
	SkipList(int _MAXLEVEL = 64, float _P = 0.25) :
		MAXLEVEL(_MAXLEVEL), P(_P), level(0)
	{
		header = make_shared<Node>(-1, MAXLEVEL);
	}


	// 随机生成一个节点最高的层数
	int RandomLevel()
	{
		int rLevel = 0;
		while ((float)rand() / RAND_MAX < P && rLevel < MAXLEVEL)
		{
			rLevel++;
		}
		return rLevel;
	}

	bool Search(int key)
	{
		shared_ptr<Node> cur = header;

		// 从最高层级开始走，找到当前层最后一个比 key 值小的节点
		for (int i = level; i >= 0; i--)
		{
			while (cur->forward[i] != nullptr && cur->forward[i]->key < key)
				cur = cur->forward[i];
		}

		// 跳转到原链表，然后往后一个位置
		cur = cur->forward[0];
		return cur != nullptr && cur->key == key;
	}

	void Insert(int key)
	{
		auto record = vector<shared_ptr<Node>>(MAXLEVEL + 1);
		shared_ptr<Node> cur = header;

		for (int i = level; i >= 0; i--)
		{
			while (cur->forward[i] != nullptr && cur->forward[i]->key < key)
				cur = cur->forward[i];
			record[i] = cur;
		}
		cur = cur->forward[0];
		// 节点已存在则直接返回
		if (cur != nullptr && cur->key == key) return;

		// 创建一个新的节点 n 进行更新
		int rLevel = RandomLevel();
		shared_ptr<Node> n = make_shared<Node>(key, rLevel);
		for (int i = 0; i <= rLevel; i++)
		{
			if (i <= level)
			{
				n->forward[i] = record[i]->forward[i];
				record[i]->forward[i] = n;
			}
			else header->forward[i] = n;
		}

		level = max(level, rLevel);
	}

	void Delete(int key)
	{
		auto record = vector<shared_ptr<Node>>(MAXLEVEL + 1);
		shared_ptr<Node> cur = header;

		for (int i = level; i >= 0; i--)
		{
			while (cur->forward[i] != nullptr && cur->forward[i]->key < key)
			{
				cur = cur->forward[i];
			}
			record[i] = cur;
		}
		cur = cur->forward[0];
		// 节点不存在 或 值不为 key 则直接返回
		if (cur == nullptr || cur->key != key) return;

		for (int i = 0; i <= level; i++)
		{
			if (record[i]->forward[i] == nullptr || record[i]->forward[i]->key != key) break;
			record[i]->forward[i] = cur->forward[i];
		}

		// 更新 level
		while (header->forward[level] == nullptr && level > 0)
			level--;
	}

	void Show()
	{
		printf("- SkipList:\n");
		for (int i = level; i >= 0; i--)
		{
			shared_ptr<Node> cur = header->forward[i];
			while (cur != nullptr)
			{
				printf("%d", cur->key);
				cur = cur->forward[i];
				printf(cur != nullptr ? " → " : "\n");
			}
		}
		printf("- End\n\n");
	}
};

int main()
{
	srand(time(0));

	SkipList* skipList = new SkipList(10, 0.5);

	skipList->Insert(1);
	skipList->Insert(2);
	skipList->Insert(3);
	skipList->Insert(4);
	skipList->Insert(5);
	skipList->Insert(6);
	skipList->Insert(7);
	skipList->Insert(8);

	skipList->Show();

	skipList->Delete(2);
	skipList->Delete(4);
	skipList->Delete(6);

	skipList->Show();

	delete skipList;

	return 0;
}