我是靠谱客的博主 优秀美女,这篇文章主要介绍20、redis底层实现跳表,现在分享给大家,希望可以做个参考。

一、简单介绍

1、我们为什么要使用跳表?

当我们使用对一个链表进行查找的时候,我们需要的时间复杂度是O(n)。我们没有办法对一个有序的链表进行二分查找。

当我们使用跳表实现,我们查找效率会很高,是O(logn)。

2、跳表的时间复杂度分析

每两个结点会抽出一个结点作为上一级索引的结点,那第一级索引的结点个数大约就是 n/2,第二级索引的结点个数大约就是 n/4,第三级索引的结点个数大约就是 n/8,依次类推,也就是说,第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2,那第 k级索引结点的个数就是 n/(2 )。
假设索引有 h 级,最高级的索引有 2 个结点。通过上面的公式,我们可以得到 n/(2 )=2,从而求得 h=log n-1。如果包含原始链表这一层,整个跳表的高度就是 log n。我们在跳表中查询某个数据的时候,如果每一层都要遍历 m 个结点,那在跳表中查询一个数据的时间复杂度就是O(m*logn)。并且m 的最大值是3.所以在跳表中查询任意数据的时间复杂度就是 O(logn)。

3、跳表的空间复杂度分析

这几级索引的结点总和就是 n/2+n/4+n/8…+8+4+2=n-2。所以,跳表的空间复杂度是 O(n)。也就是说,如果将包含 n 个结点的单链表构造成跳表,我们需要额外再用接近 n 个结点的存储空间。

二、跳表的代码实现

复制代码
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
165
166
167
168
169
170
171
172
173
174
package com.ipp.test; import java.util.Random; public class SkiptList { private class SkipListEntry { // data public String key; public Integer value; // links public SkipListEntry up; public SkipListEntry down; public SkipListEntry left; public SkipListEntry right; // special public static final String negInf = "-oo"; public static final String posInf = "+oo"; // constructor public SkipListEntry(String key, Integer value) { this.key = key; this.value = value; } } public SkipListEntry head; // First element of the top level public SkipListEntry tail; // Last element of the top level public int n; // number of entries in the Skip List public int h; // Height public Random r; // Coin toss public SkiptList() { // 创建一个 -oo 和一个 +oo 对象 SkipListEntry p1 = new SkipListEntry(SkipListEntry.negInf, null); SkipListEntry p2 = new SkipListEntry(SkipListEntry.posInf, null); //p1 和 p2 相互连接 p1.right = p2; p2.left = p1; // 给 head 和 tail 初始化 head = p1; tail = p2; //初始化其他的对象 n = 0; h = 0; r = new Random(); } /** * 查找小于等于它的元素下标 * * @param key * @return */ private SkipListEntry findEntry(String key) { SkipListEntry node = head; while (true) { // 从左向右查找,直到右节点的key值大于要查找的key值 while (node.right.key != SkipListEntry.posInf && node.right.key.compareTo(key) <= 0) { //如果右边有元素,并且是右边的元素小于等于要找的key node = node.right; } //如果下面还有元素,我们继续往下找知道到最底层的元素 if (node.down != null) { node = node.down; } else// if(node.right.key!=SkipListEntry.posInf&&node.right.key.compareTo(key)>0) { break; } } // 返回p,!注意这里p的key值是小于等于传入key的值的(p.key <= key) return node; } /** * 根据key 去寻找value 值 */ public Integer get(String key) { SkipListEntry node = findEntry(key); if (key.equals(node.key)) { return node.value; } else { return null; } } public Integer put(String key, Integer value) { SkipListEntry p, q; int i = 0; // 查找适合插入的位子 p = findEntry(key); // 如果跳跃表中存在含有key值的节点,则进行value的修改操作即可完成 if (p.key.equals(key)) { Integer oldValue = p.value; p.value = value; return oldValue; } // 如果跳跃表中不存在含有key值的节点,则进行新增操作 q = new SkipListEntry(key, value); //链表的插入操作 q.left = p; p.right.left = q; q.right = p.right; p.right = q; // 再使用随机数决定是否要向更高level攀升 while (r.nextDouble() < 0.5) { // 如果新元素的级别已经达到跳跃表的最大高度,则新建空白层 if (i >= h) { addEmptyLevel(); } // 从p向左扫描含有高层节点的节点 while (p.up == null) { p = p.left; } p = p.up; // 新增和q指针指向的节点含有相同key值的节点对象 // 这里需要注意的是除底层节点之外的节点对象是不需要value值的 SkipListEntry z = new SkipListEntry(key, null); //双链表的添加操作 z.left = p; p.right.left = z; z.right = p.right; p.right = z; //上下进行关联 z.down = q; q.up = z; i = i + 1; q = z; } n = n + 1; // 返回null,没有旧节点的value值 return null; } /** * 添加层 */ private void addEmptyLevel() { SkipListEntry p1, p2; p1 = new SkipListEntry(SkipListEntry.negInf, null); p2 = new SkipListEntry(SkipListEntry.posInf, null); p1.right = p2; p2.left = p1; //对p1 进行操作 p1.down = head; head.up = p1; //对p2 进行操作 p2.down = tail; tail.up = p2; //进行重新赋值 head = p1; tail = p2; h = h + 1; } /** * 链表的移除包含键值得某个元素 * * @param key * @return */ public Integer remove(String key) { SkipListEntry p, q; p = findEntry(key); if (!p.key.equals(key)) { return null; } Integer oldValue = p.value; //表示的是查到了 从下往上查找 while (p != null) { q = p.up; //双链表的删除 p.left.right = p.right; p.right.left = p.left; p = q; } return oldValue; } }

 

三、总结

 

1、为什么redis 底层用跳表实现而不是使用红黑树?

 

插入、删除、查找以及迭代输出有序序列这几个操作,红黑树也可以完成,时间复杂度跟跳表是一样的按照区间来查找数据这个操作,红黑树的效率没有跳表高。还有就是跳表更容易实现,安全性比较高。

 

2、跳跃表在Java中的应用


ConcurrentSkipListMap:在功能上对应HashTable、HashMap、TreeMap;

ConcurrentSkipListSet : 在功能上对应HashSet;

确切的说,SkipList更像Java中的TreeMap,TreeMap基于红黑树(一种自平衡二叉查找树)实现的,时间复杂度平均能达到O(log n)。 
HashMap是基于散列表实现的,查找时间复杂度平均能达 
到O(1)。ConcurrentSkipListMap是基于跳跃表实现的,查找时间复杂度平均能达到O(log n)。

ConcurrentSkipListMap具有SkipList的性质 ,并且适用于大规模数据的并发访问。多个线程可以安全地并发执行插入、移除、更新和访问操作。与其他有锁机制的数据结构在巨大的压力下相比有优势。

TreeMap插入数据时平衡树采用严格的旋转操作(比如平衡二叉树有左旋右旋)来保证平衡,因此SkipList比较容易实现,而且相比平衡树有着较高的运行效率。
 

 

最后

以上就是优秀美女最近收集整理的关于20、redis底层实现跳表的全部内容,更多相关20、redis底层实现跳表内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(93)

评论列表共有 0 条评论

立即
投稿
返回
顶部