原理参考：SkipList跳表
这里我使用Java实现其原理：
首先是SkipListNode的定义：
SkipListNode.java
package skiplist;
/**
* Created by zhuxinquan on 17-3-11.
*/
public class SkipListNode implements Comparable {
private int value;
private SkipListNode next = null;
private SkipListNode downNext = null;
@Override
protected void finalize() throws Throwable {
super.finalize();
System.out.printf("123");
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public SkipListNode getNext() {
return next;
}
public void setNext(SkipListNode next) {
this.next = next;
}
public SkipListNode getDownNext() {
return downNext;
}
public void setDownNext(SkipListNode downNext) {
this.downNext = downNext;
}
@Override
public int compareTo(Object o) {
return this.value > ((SkipListNode)o).value ? 1 : -1;
}
}然后是跳跃表的具体操作，操作过程在开始部分处的链接已明了，这里直接模拟实现：
SkipList.java
package skiplist;
import java.util.Random;
/**
* Created by zhuxinquan on 17-3-11.
*/
public class SkipList {
public int level = 0;
public SkipListNode top = null;
public SkipList() {
this(4);
}
//跳跃表的初始化
public SkipList(int level) {
this.level = level;
SkipListNode skipListNode = null;
SkipListNode temp = top;
SkipListNode tempDown = null;
SkipListNode tempNextDown = null;
int tempLevel = level;
while(tempLevel -- != 0){
skipListNode = createNode(Integer.MIN_VALUE);
temp = skipListNode;
skipListNode = createNode(Integer.MAX_VALUE);
temp.setNext(skipListNode);
temp.setDownNext(tempDown);
temp.getNext().setDownNext(tempNextDown);
tempDown = temp;
tempNextDown = temp.getNext();
}
top = temp;
}
//随机产生数k，k层下的都需要将值插入
public int randomLevel(){
int k = 1;
while(new Random().nextInt()%2 == 0){
k ++;
}
return k > level ? level : k;
}
//查找
public SkipListNode find(int value){
SkipListNode node = top;
while(true){
while(node.getNext().getValue() < value){
node = node.getNext();
}
if(node.getDownNext() == null){
//返回要查找的节点的前一个节点
return node;
}
node = node.getDownNext();
}
}
//删除一个节点
public boolean delete(int value){
int tempLevel = level;
SkipListNode skipListNode = top;
SkipListNode temp = skipListNode;
boolean flag = false;
while(tempLevel -- != 0){
while(temp.getNext().getValue() < value){
temp = temp.getNext();
}
if(temp.getNext().getValue() == value){
temp.setNext(temp.getNext().getNext());
flag = true;
}
temp = skipListNode.getDownNext();
}
return flag;
}
//插入一个节点
public void insert(int value){
SkipListNode skipListNode = null;
int k = randomLevel();
SkipListNode temp = top;
int tempLevel = level;
SkipListNode tempNode = null;
//当在第n行插入后，在第n - 1行插入时需要将第n行backTempNode的DownNext域指向第n - 1的域
SkipListNode backTempNode = null;
int flag = 1;
while(tempLevel-- != k){
temp = temp.getDownNext();
}
tempLevel++;
tempNode = temp;
//小于k层的都需要进行插入
while(tempLevel-- != 0){
//在第k层寻找要插入的位置
while(tempNode.getNext().getValue() < value){
tempNode = tempNode.getNext();
}
skipListNode = createNode(value);
//如果是顶层
if(flag != 1){
backTempNode.setDownNext(skipListNode);
}
backTempNode = skipListNode;
skipListNode.setNext(tempNode.getNext());
tempNode.setNext(skipListNode);
flag = 0;
tempNode = tempNode.getDownNext();
}
}
//创建一个节点
private SkipListNode createNode(int value){
SkipListNode node = new SkipListNode();
node.setValue(value);
return node;
}
}然后再定义一个测试类如下：
SkipListTest.java
package skiplist;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
/**
* Created by zhuxinquan on 17-3-11.
*/
public class SkipListTest {
public static void main(String[] args) {
long startTime = 0;
long endTime = 0;
SkipList skipList = new SkipList(12);
Set<Integer> set = new HashSet();
List<Integer> list = new LinkedList<>();
//测试跳跃表性能
startTime = System.currentTimeMillis();
for (int i = 1; i < 100000; i++) {
skipList.insert(i);
}
endTime = System.currentTimeMillis();
System.out.printf("createSkipList:%d\n", endTime - startTime);
startTime = System.currentTimeMillis();
System.out.printf("find(555)：%d\n", skipList.find(55555).getNext().getValue());
endTime = System.currentTimeMillis();
System.out.printf("skipListFindTime:%d\n\n", endTime - startTime);
//测试LinkedList性能
startTime = System.currentTimeMillis();
for (int i = 1; i < 100000; i++) {
list.add(i);
}
endTime = System.currentTimeMillis();
System.out.printf("createList:%d\n", endTime - startTime);
startTime = System.currentTimeMillis();
System.out.printf("find(555)：%b\n", list.contains(55555));
endTime = System.currentTimeMillis();
System.out.printf("linkedListFindTime:%d\n\n", endTime - startTime);
//测试hashSet性能
startTime = System.currentTimeMillis();
for (int i = 1; i < 100000; i++) {
set.add(i);
}
endTime = System.currentTimeMillis();
System.out.printf("createSet:%d\n", endTime - startTime);
startTime = System.currentTimeMillis();
System.out.printf("find(555)：%b\n", set.contains(55555));
endTime = System.currentTimeMillis();
System.out.printf("hashSetFindTime:%d\n", endTime - startTime);
}
}上述测试类对100000条数据进行插入和查找，分别统计使用跳跃表、LinkedList、HashSet时插入和查找的时间，结果如下：
下面是50000整数中查找38555这个值消耗的时间：
上图很明显的可以看出，跳跃表的查找效率还是很高的（在数据量高的时候），同时，跳跃表也肯定消耗了不少的额外空间。
上述代码只是个人根据自己的理解简单实现了跳跃表的原理，其中自然有不少瑕疵，也有好多可优化的地方，比如可以将每层的起点节点的引用保存在一个一维数组当中、跳表中存储键值对这样的数据结构等等。。。。
个人理解，如有不足之处，还望指正！