跳跃表的原理及Java实现

原理参考：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这个值消耗的时间：

上图很明显的可以看出，跳跃表的查找效率还是很高的（在数据量高的时候），同时，跳跃表也肯定消耗了不少的额外空间。

上述代码只是个人根据自己的理解简单实现了跳跃表的原理，其中自然有不少瑕疵，也有好多可优化的地方，比如可以将每层的起点节点的引用保存在一个一维数组当中、跳表中存储键值对这样的数据结构等等。。。。

个人理解，如有不足之处，还望指正！