这篇文章主要介绍了Java编程中跳跃表的概念和实现原理，并简要叙述了它的结构，具有一定参考价值，需要的朋友可以了解下。
跳跃链表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树(对于大多数操作需要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
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的具体实现（包含增、删、改、查 ）
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 测试
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实现跳跃表skiplist的示例分享的详细内容，更多请关注其它相关文章！
与其用泪水悔恨今天，不如用汗水拼搏今天。
