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<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编程实现一个简单的跳跃表的实现方法实例，希望对大家有所帮助，感谢大家对本站的支持！