跳跃表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)，并且对并发算法友好。 关于跳跃表的具体介绍可以参考MIT的公开课：跳跃表 跳跃表的应用 Skip list(跳表）是一种可以代替平衡树的数据结构，默认是按照Key值升序的。Skip list让已排序的数据分布在多层链表中，以0-1随机数决定一个数据的向上攀升与否，通过“空间来换取时间”的一个算法，在每个节点中增加了向前的指针，在插入、删除、查找时可以忽略一些不可能涉及到的结点，从而提高了效率。 在Java的API中已经有了实现：分别是 ConcurrentSkipListMap(在功能上对应HashTable、HashMap、TreeMap) ； ConcurrentSkipListSet(在功能上对应HashSet). 确切来说，SkipList更像Java中的TreeMap，TreeMap基于红黑树（一种自平衡二叉查找树）实现的，时间复杂度平均能达到O(log n)。 HashMap是基于散列表实现的，时间复杂度平均能达到O(1)。ConcurrentSkipListMap是基于跳表实现的，时间复杂度平均能达到O(log n)。 Skip list的性质 (1) 由很多层结构组成，level是通过一定的概率随机产生的。
(2) 每一层都是一个有序的链表，默认是升序
(3) 最底层(Level 1)的链表包含所有元素。
(4) 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现。
(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。 Ø ConcurrentSkipListMap具有Skip list的性质 ，并且适用于大规模数据的并发访问。多个线程可以安全地并发执行插入、移除、更新和访问操作。与其他有锁机制的数据结构在巨大的压力下相比有优势。 Ø TreeMap插入数据时平衡树采用严格的旋转（比如平衡二叉树有左旋右旋）来保证平衡，因此Skip list比较容易实现，而且相比平衡树有着较高的运行效率。 Java代码实现： 1. SkipListEntry.java ， 这是跳跃表中存储的每个元素实体类，包含 上下左右 四个指针。
01
package skiplist;
02 03
public class SkipListEntry {
04
public String key;
05
public Integer value;
06 07
public int pos; //主要为了打印 链表用
08 09
public SkipListEntry up, down, left, right; // 上下左右 四个指针
10 11
public static String negInf = new String("-oo"); // 负无穷
12
public static String posInf = new String("+oo"); // 正无穷
13 14
public SkipListEntry(String k, Integer v) {
15
key = k;
16
value = v;
17 18
up = down = left = right = null;
19
}
20 21
public Integer getValue() {
22
return value;
23
}
24 25
public String getKey() {
26
return key;
27
}
28 29
public Integer setValue(Integer val) {
30
Integer oldValue = value;
31
value = val;
32
return oldValue;
33
}
34 35
public boolean equals(Object o) {
36
SkipListEntry ent;
37
try {
38
ent = (SkipListEntry) o; // 检测类型
39
} catch (ClassCastException ex) {
40
return false;
41
}
42
return (ent.getKey() == key) && (ent.getValue() == value);
43
}
44 45
public String toString() {
46
return "(" + key + "," + value + ")";
47
}
48
} 2. SkipList.java, 跳跃表类，包含算法的实现。 head 和 tail 分别是 顶层的头和尾。
001
package skiplist;
002 003
import java.util.*;
004 005
public class SkipList {
006
public SkipListEntry head; // 顶层的第一个元素
007
public SkipListEntry tail; // 顶层的最后一个元素
008 009
public int n; // 跳跃表中的元素个数
010 011
public int h; // 跳跃表的高度
012
public Random r; // 投掷硬币
013 014
public SkipList() // 默认构造函数...
015
{
016
SkipListEntry p1, p2;
017 018
p1 = new SkipListEntry(SkipListEntry.negInf, null);
019
p2 = new SkipListEntry(SkipListEntry.posInf, null);
020 021
head = p1;
022
tail = p2;
023 024
p1.right = p2;
025
p2.left = p1;
026 027
n = 0;
028
h = 0;
029
r = new Random();
030
}
031 032
/** 返回 包含的元素个数 */
033
public int size() {
034
return n;
035
}
036 037
/** 跳跃表是否为空 */
038
public boolean isEmpty() {
039
return (n == 0);
040
}
041 042
//在最下面一层，找到要插入的位置前面的那个key
043
public SkipListEntry findEntry(String k) {
044
SkipListEntry p;
045
p = head;
046 047
while (true) {
048
/**
049
* 一直向右找，例: k=34.
050
* 10 ---> 20 ---> 30 ---> 40 ^ | p 会在30处停止
051
* --------------------------------------------
052
***/
053
while (p.right.key != SkipListEntry.posInf
054
&& p.right.key.compareTo(k) <= 0) {
055
p = p.right;
056
// System.out.println(">>>> " + p.key);
057
}
058
// 如果还有下一层，就到下一层继续查找
059
if (p.down != null) {
060
p = p.down;
061
//System.out.println("vvvv " + p.key);
062
} else
063
break; // 到了最下面一层 就停止查找
064
}
065 066
return (p); // p.key <= k
067
}
068 069
/** 返回和key绑定的值 */
070
public Integer get(String k) {
071
SkipListEntry p;
072 073
p = findEntry(k);
074 075
if (k.equals(p.getKey()))
076
return (p.value);
077
else
078
return (null);
079
}
080 081
/** 放一个key-value到跳跃表中, 替换原有的并返回 */
082
public Integer put(String k, Integer v) {
083
SkipListEntry p, q;
084
int i;
085 086
p = findEntry(k);
087 088
if (k.equals(p.getKey())) {
089
Integer old = p.value;
090
p.value = v;
091
return (old);
092
}
093 094
q = new SkipListEntry(k, v);
095
q.left = p;
096
q.right = p.right;
097
p.right.left = q;
098
p.right = q;
099 100
i = 0; // 当前层 level = 0
101 102
while (r.nextDouble() < 0.5) {
103 104
//如果超出了高度，需要重新建一个顶层
105
if (i >= h) {
106
SkipListEntry p1, p2;
107 108
h = h + 1;
109
p1 = new SkipListEntry(SkipListEntry.negInf, null);
110
p2 = new SkipListEntry(SkipListEntry.posInf, null);
111 112
p1.right = p2;
113
p1.down = head;
114 115
p2.left = p1;
116
p2.down = tail;
117 118
head.up = p1;
119
tail.up = p2;
120 121
head = p1;
122
tail = p2;
123
}
124 125
while (p.up == null) {
126
p = p.left;
127
}
128
p = p.up;
129 130
SkipListEntry e;
131 132
e = new SkipListEntry(k, null);
133
e.left = p;
134
e.right = p.right;
135
e.down = q;
136 137
p.right.left = e;
138
p.right = e;
139
q.up = e;
140 141
q = e; // q 进行下一层迭代
142
i = i + 1; // 当前层 +1
143 144
}
145
n = n + 1;
146 147
return (null); // No old value
148
}
149 150
public Integer remove(String key) {
151
return (null);
152
}
153 154
public void printHorizontal() {
155
String s = "";
156
int i;
157
SkipListEntry p;
158 159
p = head;
160 161
while (p.down != null) {
162
p = p.down;
163
}
164 165
i = 0;
166
while (p != null) {
167
p.pos = i++;
168
p = p.right;
169
}
170 171
p = head;
172
while (p != null) {
173
s = getOneRow(p);
174
System.out.println(s);
175 176
p = p.down;
177
}
178
}
179 180
//用了打印测试
181
public String getOneRow(SkipListEntry p) {
182
String s;
183
int a, b, i;
184 185
a = 0;
186 187
s = "" + p.key;
188
p = p.right;
189 190
while (p != null) {
191
SkipListEntry q;
192 193
q = p;
194
while (q.down != null)
195
q = q.down;
196
b = q.pos;
197 198
s = s + " <-";
199 200
for (i = a + 1; i < b; i++)
201
s = s + "--------";
202 203
s = s + "> " + p.key;
204 205
a = b;
206 207
p = p.right;
208
}
209 210
return (s);
211
}
212 213
//用了打印测试
214
public void printVertical() {
215
String s = "";
216
SkipListEntry p;
217
p = head;
218
while (p.down != null)
219
p = p.down;
220 221
while (p != null) {
222
s = getOneColumn(p);
223
System.out.println(s);
224 225
p = p.right;
226
}
227
}
228
//用了打印测试
229
public String getOneColumn(SkipListEntry p) {
230
String s = "";
231
while (p != null) {
232
s = s + " " + p.key;
233
p = p.up;
234
}
235
return (s);
236
}
237
} 测试类，Test.java
01
package skiplist;
02 03
public class Test1 {
04
public static void main(String[] args) {
05
SkipList S = new SkipList();
06 07
S.printHorizontal();
08
System.out.println("------");
09
// S.printVertical();
10
// System.out.println("======");
11 12
S.put("ABC", 123);
13
S.printHorizontal();
14
System.out.println("------");
15
// S.printVertical();
16
//System.out.println("======");
17 18
S.put("DEF", 123);
19
S.printHorizontal();
20
System.out.println("------");
21
// S.printVertical();
22
// System.out.println("======");
23 24
S.put("KLM", 123);
25
S.printHorizontal();
26
System.out.println("------");
27
// S.printVertical();
28
// System.out.println("======");
29 30
S.put("HIJ", 123);
31
S.printHorizontal();
32
System.out.println("------");
33
// S.printVertical();
34
// System.out.println("======");
35 36
S.put("GHJ", 123);
37
S.printHorizontal();
38
System.out.println("------");
39
// S.printVertical();
40
// System.out.println("======");
41 42
S.put("AAA", 123);
43
S.printHorizontal();
44
System.out.println("------");
45
// S.printVertical();
46
// System.out.println("======");
47 48
}
49
} 输出结果：
01
-oo <-> +oo
02
------
03
-oo <-> ABC <-> +oo
04
-oo <-> ABC <-> +oo
05
------
06
-oo <-> ABC <---------> +oo
07
-oo <-> ABC <-> DEF <-> +oo
08
------
09
-oo <-> ABC <---------> KLM <-> +oo
10
-oo <-> ABC <-> DEF <-> KLM <-> +oo
11
------
12
-oo <-----------------> HIJ <---------> +oo
13
-oo <-> ABC <---------> HIJ <-> KLM <-> +oo
14
-oo <-> ABC <-> DEF <-> HIJ <-> KLM <-> +oo
15
------
16
-oo <-------------------------> HIJ <---------> +oo
17
-oo <-> ABC <-----------------> HIJ <-> KLM <-> +oo
18
-oo <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo
19
------
20
-oo <---------------------------------> HIJ <---------> +oo
21
-oo <---------> ABC <-----------------> HIJ <-> KLM <-> +oo
22
-oo <-> AAA <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo
23
------ 每次运行的结果是不一样的，这就是为什么说跳跃表是属于随机化数据结构。 代码参考：Implementing the skip list data structure