跳跃链表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)，并且对并发算法友好。
基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。
实现原理：
跳跃表的结构是：假如底层有10个节点， 那么底层的上一层理论上就有5个节点，再上一层理论上就有2个或3个节点，再上一层理论上就有1个节点。所以从这里可以看出每一层的节点个数为其下一层的1/2个元素，以此类推。从这里我们可以看到，从插入时我们只要保证上一层的元素个数为下一层元素个数的1/2，我们的跳跃表就能成为理想的跳跃表。那么怎么才能保证我们插入时上层元素个数是下层元素个数的1/2呢，？很简单 抛硬币就可以解决了，假设元素X要插入跳跃表，最底层是肯定要插入X的，那么次低层要不要插入呢，我们希望上层元素个数是下层的1/2，那么我们有1/2的概率要插入到次低层，这样就来抛硬币吧，正面就插入，反面就不插入，次次底层相对于次低层，我们还是有1/2的概率插入，那么就继续抛硬币吧 ， 以此类推元，素X插入第n层的概率是(1/2)的n次。这样，我们能在跳跃表中插入一个元素了。
第一次知道跳表这种数据结构的时间大概是在一年前（说这句话时候可能就被无数同胞鄙视了），但自己却不知道如何实现。当时印象最深的就是一篇跳跃表(Skip List)-实现(Java)的文章，因为这篇文章中的Skip List的实现方式最让人容易理解，我最初也是通过这篇文章对跳表有了更进一步的认识，所以，真的要在这里感谢这篇文章的主人。一年之后，我发现自己对跳表的认识又模糊不清了，所以最先想到的也是这篇文章。今天再次拜读此文，同时实现了其中未给出的删除方法。并增加了泛型，但泛型也只是对value采用了泛型，对Key依然采用原文中的String类型。所以依然比较简单和局限。之所以贴出来，是为了增进自己对Skip List的理解和作为备忘。原文的链接如之前所述，原文具体作者其实我也不知道是谁，只想在此默默的说声感谢。当然了，若原文作者觉得我有什么冒犯或侵权的行为，我会立马删帖。
关于跳表的定义和介绍，读者可以参考原文。这里就直接给出原码了，这里的原码与原文的唯一的一点区别就是，我这里给出了原文没给出的删除方法（原文其实参考的是一篇英文文章，英文文章给出了删除方法，我直到后来才发现，不过自己的实现和英文文章想比，代码略显多余，此处贴出来的是我自己实现的删除方法）。可能实现上比较糟糕，所以也恳请大家批评指正！！！
1 对跳表中各个元素（键值对）的封装类SkipListEntry.java
|
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
|
public class SkipListEntry<v>{ public String key; public V value; public int pos; // 主要为了打印 链表用 public SkipListEntry<v deep="6"> up, down, left, right; // 上下左右 四个指针 public static String negInf = new String("-oo"); // 负无穷 public static String posInf = new String("+oo"); // 正无穷 public SkipListEntry(String k, V v) { key = k; value = v; up = down = left = right = null; } public V getValue() { return value; } public String getKey() { return key; } public V setValue(V val) { V oldValue = value; value = val; return oldValue; } @SuppressWarnings("unchecked") public boolean equals(Object o) { SkipListEntry<v> entry; try { entry = (SkipListEntry<v>) o; // 检测类型 } catch (ClassCastException ex) { return false; } return (entry.getKey() == key) && (entry.getValue().equals(value)); } public String toString() { return "(" + key + "," + value + ")"; }} |
2 Skip List的具体实现（包含增、删、改、查 ）
|
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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
|
import java.util.Random;/** * 跳表的一种简单实现。key只能为字符串类型，value可以为任意对象类型 * @param <v> * @author xxx 2017年2月14日 下午9:42:06 * @version v1.0 */public class SkipList<v>{ public SkipListEntry<v> head; // 顶层的第一个元素 public SkipListEntry<v> tail; // 顶层的最后一个元素 public int size; // 跳跃表中的元素个数 public int height; // 跳跃表的高度 public Random flag; // 投掷硬币 /** * 默认构造函数 * @author xxx 2017年2月14日 下午9:32:22 * @since v1.0 */ public SkipList() { head = new SkipListEntry<v>(SkipListEntry.negInf, null); tail = new SkipListEntry<v>(SkipListEntry.posInf, null); head.right = tail; tail.left = head; size = 0; height = 0; flag = new Random(); } /** * 返回元素的个数 * @return * @author xxx 2017年2月14日 下午9:35:22 * @since v1.0 */ public int size() { return size; } /** * 判断跳表中的元素个数是否为零 * @return * @author xxx 2017年2月14日 下午9:35:52 * @since v1.0 */ public boolean isEmpty() { return (size == 0); } /** * 从最顶层的第一个元素，也即head元素开始查找，直到找到第0层、要插入的位置前面的那个key * @param k * @return * @author xxx 2017年2月14日 下午9:42:12 * @since v1.0 */ private SkipListEntry<v> findEntry(String k) { SkipListEntry<v> p = head; while (true) { /* * 一直向右找，例: k=34。 10 ---> 20 ---> 30 ---> 40 ^ | p 会在30处停止 */ while (p.right.key != SkipListEntry.posInf && p.right.key.compareTo(k) <= 0) { p = p.right; } // 如果还有下一层，就到下一层继续查找 if (p.down != null) { p = p.down; } else { break; // 到了最下面一层 就停止查找 } } return p; // p.key <= k } /** 返回和key绑定的值 */ public V get(String k) { SkipListEntry<v> p = findEntry(k); if (k.equals(p.getKey())) { return p.value; } else { return null; } } /** * 往跳表中插入一个键值对，如果键已经存在，则覆盖相应的值并返回旧值 * @param k * @param v * @return * @author xxx 2017年2月14日 下午9:48:54 * @since v1.0 */ public V put(String k, V v) { System.out.println("-----插入[" + k + "]之前的跳跃表是:-----"); printHorizontal(); SkipListEntry<v> p, q; p = findEntry(k); if (k.equals(p.getKey())) { V old = p.value; p.value = v; return old; } q = new SkipListEntry<v>(k, v); q.left = p; q.right = p.right; p.right.left = q; p.right = q; int currentLevel = 0; // 当前层 currentLevel = 0 // 随机值小于0.5，则插入的键值对对应的键需要在上一层建立关联，同时有可能增加跳表的高度 while (flag.nextDouble() < 0.5) { // 如果超出了高度，需要重新建一个顶层 if (currentLevel >= height) { SkipListEntry<v> p1, p2; height = height + 1; p1 = new SkipListEntry<v>(SkipListEntry.negInf, null); p2 = new SkipListEntry<v>(SkipListEntry.posInf, null); p1.right = p2; p1.down = head; p2.left = p1; p2.down = tail; head.up = p1; tail.up = p2; head = p1; tail = p2; } while (p.up == null) { p = p.left; } p = p.up; SkipListEntry<v> e; /* * 注意，本实现中只有第0层的链表持有键对应的值，1 ~ height 层中的SkipListEntry对象 * 仅仅持有键的引用，值为空，以便节省空间。 */ e = new SkipListEntry<v>(k, null); e.left = p; e.right = p.right; e.down = q; p.right.left = e; p.right = e; q.up = e; q = e; // q 进行下一层迭代 currentLevel = currentLevel + 1; // 当前层 +1 } // 插入一个键值对后总数加1 size = size + 1; System.out.println("-----插入[" + k + "]之后的跳跃表是:-----"); printHorizontal(); return null; } /** * 根据键删除键值对 * @param key * @return * @author xxx 2017年2月14日 下午10:08:17 * @since v1.0 */ public void remove(String key) { SkipListEntry<v> p = findEntry(key); if(!p.getKey().equals(key)) { return; } //删除元素后重新关联，同时使被删除的对象游离，便于垃圾回收 p.left.right = p.right; p.right.left = p.left; p.right = null; p.left = null; //自底向上，使所有键等于key的SkipListEntry对象左右两个方向的引用置空 while(p.up != null) { p = p.up; p.left.right = p.right; p.right.left = p.left; p.right = null; p.left = null; } //自顶向下，使所有键等于key的SkipListEntry对象上下两个方向的引用置空 while(p.down != null) { SkipListEntry<v> temp = p.down; p.down = null; temp.up = null; p = temp; } /* * 删除元素后，如果顶层的链表只有head和tail两个元素，则删除顶层。 * 删除顶层以后最新的顶层如果依然只有head和tail两个元素，则也要被删除，以此类推。 */ while(head.right.key == tail.key && height > 0) { SkipListEntry<v> p1, p2; p1 = head.down; p2 = tail.down; head.right = null; head.down = null; tail.left = null; tail.down = null; p1.up = null; p2.up = null; head = p1; tail = p2; height = height - 1; } //成功移除一个元素，大小减1 size = size - 1; System.out.println("-----删除[" + key + "]后的跳跃表是:-----"); printHorizontal(); } /** * 打印出跳表的图示结构(水平方向) * @author xxx 2017年2月14日 下午10:35:36 * @since v1.0 */ public void printHorizontal() { String s = ""; int i; SkipListEntry<v> p; p = head; while (p.down != null) { p = p.down; } i = 0; while (p != null) { p.pos = i++; p = p.right; } p = head; while (p != null) { s = getOneRow(p); System.out.println(s); p = p.down; } } private String getOneRow(SkipListEntry<v> p) { String s; int a, b, i; a = 0; s = "" + p.key; p = p.right; while (p != null) { SkipListEntry<v> q; q = p; while (q.down != null) q = q.down; b = q.pos; s = s + " <-"; for (i = a + 1; i < b; i++) s = s + "--------"; s = s + "> " + p.key; a = b; p = p.right; } return s; } /** * 打印出跳表的图示结构(垂直方向) * @author xxx 2017年2月14日 下午10:35:36 * @since v1.0 */ public void printVertical() { String s = ""; SkipListEntry<v> p; p = head; while (p.down != null) p = p.down; while (p != null) { s = getOneColumn(p); System.out.println(s); p = p.right; } } private String getOneColumn(SkipListEntry<v> p) { String s = ""; while (p != null) { s = s + " " + p.key; p = p.up; } return (s); }} |
3 测试
|
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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
|
public class Test{ public static void main(String[] args) { SkipList<String> s = new SkipList<String>(); s.put("ABC", ""); s.put("DEF", ""); s.put("KLM", ""); s.put("HIJ", ""); s.put("GHJ", ""); s.put("AAA", ""); s.remove("ABC"); s.remove("DEF"); s.remove("KLM"); s.remove("HIJ"); s.remove("GHJ"); s.remove("AAA"); s.put("ABC", ""); s.put("DEF", ""); s.put("KLM", ""); s.put("HIJ", ""); s.put("GHJ", ""); s.put("AAA", ""); }}//运行测试后结果示例如下（注意：由于跳表的特性，每次运行结果都不一样）-----插入[ABC]之前的跳跃表是:------oo <-> +oo-----插入[ABC]之后的跳跃表是:------oo <-> ABC <-> +oo-oo <-> ABC <-> +oo-----插入[DEF]之前的跳跃表是:------oo <-> ABC <-> +oo-oo <-> ABC <-> +oo-----插入[DEF]之后的跳跃表是:------oo <---------> DEF <-> +oo-oo <-> ABC <-> DEF <-> +oo-oo <-> ABC <-> DEF <-> +oo-----插入[KLM]之前的跳跃表是:------oo <---------> DEF <-> +oo-oo <-> ABC <-> DEF <-> +oo-oo <-> ABC <-> DEF <-> +oo-----插入[KLM]之后的跳跃表是:------oo <---------> DEF <-> KLM <-> +oo-oo <-> ABC <-> DEF <-> KLM <-> +oo-oo <-> ABC <-> DEF <-> KLM <-> +oo-----插入[HIJ]之前的跳跃表是:------oo <---------> DEF <-> KLM <-> +oo-oo <-> ABC <-> DEF <-> KLM <-> +oo-oo <-> ABC <-> DEF <-> KLM <-> +oo-----插入[HIJ]之后的跳跃表是:------oo <---------> DEF <---------> KLM <-> +oo-oo <-> ABC <-> DEF <---------> KLM <-> +oo-oo <-> ABC <-> DEF <-> HIJ <-> KLM <-> +oo-----插入[GHJ]之前的跳跃表是:------oo <---------> DEF <---------> KLM <-> +oo-oo <-> ABC <-> DEF <---------> KLM <-> +oo-oo <-> ABC <-> DEF <-> HIJ <-> KLM <-> +oo-----插入[GHJ]之后的跳跃表是:------oo <-----------------> GHJ <-----------------> +oo-oo <-----------------> GHJ <-----------------> +oo-oo <-----------------> GHJ <-----------------> +oo-oo <-----------------> GHJ <-----------------> +oo-oo <-----------------> GHJ <-----------------> +oo-oo <-----------------> GHJ <-----------------> +oo-oo <---------> DEF <-> GHJ <---------> KLM <-> +oo-oo <-> ABC <-> DEF <-> GHJ <---------> KLM <-> +oo-oo <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo-----插入[AAA]之前的跳跃表是:------oo <-----------------> GHJ <-----------------> +oo-oo <-----------------> GHJ <-----------------> +oo-oo <-----------------> GHJ <-----------------> +oo-oo <-----------------> GHJ <-----------------> +oo-oo <-----------------> GHJ <-----------------> +oo-oo <-----------------> GHJ <-----------------> +oo-oo <---------> DEF <-> GHJ <---------> KLM <-> +oo-oo <-> ABC <-> DEF <-> GHJ <---------> KLM <-> +oo-oo <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo-----插入[AAA]之后的跳跃表是:------oo <-------------------------> GHJ <-----------------> +oo-oo <-------------------------> GHJ <-----------------> +oo-oo <-------------------------> GHJ <-----------------> +oo-oo <-------------------------> GHJ <-----------------> +oo-oo <-------------------------> GHJ <-----------------> +oo-oo <-> AAA <-----------------> GHJ <-----------------> +oo-oo <-> AAA <---------> DEF <-> GHJ <---------> KLM <-> +oo-oo <-> AAA <-> ABC <-> DEF <-> GHJ <---------> KLM <-> +oo-oo <-> AAA <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo-----删除[ABC]后的跳跃表是:------oo <-----------------> GHJ <-----------------> +oo-oo <-----------------> GHJ <-----------------> +oo-oo <-----------------> GHJ <-----------------> +oo-oo <-----------------> GHJ <-----------------> +oo-oo <-----------------> GHJ <-----------------> +oo-oo <-> AAA <---------> GHJ <-----------------> +oo-oo <-> AAA <-> DEF <-> GHJ <---------> KLM <-> +oo-oo <-> AAA <-> DEF <-> GHJ <---------> KLM <-> +oo-oo <-> AAA <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo-----删除[DEF]后的跳跃表是:------oo <---------> GHJ <-----------------> +oo-oo <---------> GHJ <-----------------> +oo-oo <---------> GHJ <-----------------> +oo-oo <---------> GHJ <-----------------> +oo-oo <---------> GHJ <-----------------> +oo-oo <-> AAA <-> GHJ <-----------------> +oo-oo <-> AAA <-> GHJ <---------> KLM <-> +oo-oo <-> AAA <-> GHJ <---------> KLM <-> +oo-oo <-> AAA <-> GHJ <-> HIJ <-> KLM <-> +oo-----删除[KLM]后的跳跃表是:------oo <---------> GHJ <---------> +oo-oo <---------> GHJ <---------> +oo-oo <---------> GHJ <---------> +oo-oo <---------> GHJ <---------> +oo-oo <---------> GHJ <---------> +oo-oo <-> AAA <-> GHJ <---------> +oo-oo <-> AAA <-> GHJ <---------> +oo-oo <-> AAA <-> GHJ <---------> +oo-oo <-> AAA <-> GHJ <-> HIJ <-> +oo-----删除[HIJ]后的跳跃表是:------oo <---------> GHJ <-> +oo-oo <---------> GHJ <-> +oo-oo <---------> GHJ <-> +oo-oo <---------> GHJ <-> +oo-oo <---------> GHJ <-> +oo-oo <-> AAA <-> GHJ <-> +oo-oo <-> AAA <-> GHJ <-> +oo-oo <-> AAA <-> GHJ <-> +oo-oo <-> AAA <-> GHJ <-> +oo-----删除[GHJ]后的跳跃表是:------oo <-> AAA <-> +oo-oo <-> AAA <-> +oo-oo <-> AAA <-> +oo-oo <-> AAA <-> +oo-----删除[AAA]后的跳跃表是:------oo <-> +oo-----插入[ABC]之前的跳跃表是:------oo <-> +oo-----插入[ABC]之后的跳跃表是:------oo <-> ABC <-> +oo-----插入[DEF]之前的跳跃表是:------oo <-> ABC <-> +oo-----插入[DEF]之后的跳跃表是:------oo <---------> DEF <-> +oo-oo <---------> DEF <-> +oo-oo <---------> DEF <-> +oo-oo <---------> DEF <-> +oo-oo <-> ABC <-> DEF <-> +oo-----插入[KLM]之前的跳跃表是:------oo <---------> DEF <-> +oo-oo <---------> DEF <-> +oo-oo <---------> DEF <-> +oo-oo <---------> DEF <-> +oo-oo <-> ABC <-> DEF <-> +oo-----插入[KLM]之后的跳跃表是:------oo <---------> DEF <---------> +oo-oo <---------> DEF <---------> +oo-oo <---------> DEF <---------> +oo-oo <---------> DEF <---------> +oo-oo <-> ABC <-> DEF <-> KLM <-> +oo-----插入[HIJ]之前的跳跃表是:------oo <---------> DEF <---------> +oo-oo <---------> DEF <---------> +oo-oo <---------> DEF <---------> +oo-oo <---------> DEF <---------> +oo-oo <-> ABC <-> DEF <-> KLM <-> +oo-----插入[HIJ]之后的跳跃表是:------oo <---------> DEF <-----------------> +oo-oo <---------> DEF <-----------------> +oo-oo <---------> DEF <-----------------> +oo-oo <---------> DEF <-> HIJ <---------> +oo-oo <-> ABC <-> DEF <-> HIJ <-> KLM <-> +oo-----插入[GHJ]之前的跳跃表是:------oo <---------> DEF <-----------------> +oo-oo <---------> DEF <-----------------> +oo-oo <---------> DEF <-----------------> +oo-oo <---------> DEF <-> HIJ <---------> +oo-oo <-> ABC <-> DEF <-> HIJ <-> KLM <-> +oo-----插入[GHJ]之后的跳跃表是:------oo <---------> DEF <-------------------------> +oo-oo <---------> DEF <-------------------------> +oo-oo <---------> DEF <-------------------------> +oo-oo <---------> DEF <---------> HIJ <---------> +oo-oo <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo-----插入[AAA]之前的跳跃表是:------oo <---------> DEF <-------------------------> +oo-oo <---------> DEF <-------------------------> +oo-oo <---------> DEF <-------------------------> +oo-oo <---------> DEF <---------> HIJ <---------> +oo-oo <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo-----插入[AAA]之后的跳跃表是:------oo <-----------------> DEF <-------------------------> +oo-oo <-----------------> DEF <-------------------------> +oo-oo <-----------------> DEF <-------------------------> +oo-oo <-----------------> DEF <---------> HIJ <---------> +oo-oo <-> AAA <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo |
总结
以上所述就是本文关于Java编程实现一个简单的跳跃表的实现方法实例，希望对大家有所帮助，感谢大家对本站的支持！
原文链接：https://www.2cto.com/kf/201702/599228.html
