跳躍鏈表是一種隨機化數據結構，基于并聯的鏈表，其效率可比擬于二叉查找樹(對于大多數操作需要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
