masyarakat Belajar Perpustakaan Alatan Masa lapang
cari
Melayu
Rumah > Java > javaTutorial > teks badan

Java实现跳跃表skiplist的示例分享

黄舟
Lepaskan： 2017-09-19 11:44:20
asal
1484 orang telah melayarinya

这篇文章主要介绍了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 + ")";
 }
}
Salin selepas log masuk

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);
 }
}
Salin selepas log masuk

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
Salin selepas log masuk

总结

Atas ialah kandungan terperinci Java实现跳跃表skiplist的示例分享. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Label berkaitan：
java skiplist 示例
sumber：php.cn
Artikel sebelumnya：Core Java简单介绍HashSet Artikel seterusnya：Java如何获取中文拼音首字母的方法介绍
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Artikel terbaru oleh pengarang
Isu terkini
function_exists() tidak boleh menentukan fungsi tersuai Ujian fungsi () {return true;} jika (function_exists ('test')) {echo "test is functio...
daripada 2024-04-29 11:01:01
0
2
2026
Bagaimana untuk memaparkan versi mudah alih Google Chrome Hello cikgu, bagaimana saya boleh menukar Google Chrome kepada versi mudah alih?
daripada 2024-04-23 00:22:19
0
11
2188
Tetingkap anak mengendalikan tetingkap induk, tetapi output tidak bertindak balas. Dua ayat pertama boleh dilaksanakan, tetapi ayat terakhir tidak boleh dilaksanakan.
daripada 2024-04-19 15:37:47
0
1
1845
Tiada output dalam tetingkap induk document.onclick = function(){ window.opener.document.write('Saya adalah output tetingkap ...
daripada 2024-04-18 23:52:34
0
1
1735
Di manakah perisian kursus tentang pemetaan minda CSS? Perisian kursus
daripada 2024-04-16 10:10:18
0
0
1758
Topik-topik yang berkaitan
Lagi>
Cadangan popular
Tutorial Popular
Lagi>
Tutorial berkaitan
Cadangan popular
Kursus terkini
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan