Java实现跳跃表(skiplist)的简单实例-创新互联

跳跃链表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树(对于大多数操作需要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
{
 public String key;
 public V value;
 public int pos; // 主要为了打印 链表用
 public SkipListEntry 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 entry;
  try
  {
   entry = (SkipListEntry) o; // 检测类型
  } catch (ClassCastException ex)
  {
   return false;
  }
  return (entry.getKey() == key) && (entry.getValue().equals(value));
 }
 public String toString()
 {
  return "(" + key + "," + value + ")";
 }
}