温馨提示×

温馨提示×

您好，登录后才能下订单哦！

密码登录×
登录注册×
获取短信验证码
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》
登 录 注册有礼
云服务器 香港服务器 高防服务器
最新更新 网站标签 地图导航
产品

Java实现跳跃表(skiplist)的简单实例

发布时间：2020-09-05 10:04:03 来源：脚本之家 阅读：139 作者：lhever_的博客 栏目：编程语言

跳跃链表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树(对于大多数操作需要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编程实现一个简单的跳跃表的实现方法实例，希望对大家有所帮助，感谢大家对本站的支持！

向AI问一下细节
推荐阅读：
  1. c++怎么实现跳跃表的方法示
  2. 探索Redis设计与实现6：Redis内部数据结构详解——skiplist

免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。

java 跳跃表 skiplist

猜你喜欢

最新资讯
相关推荐

相关标签

java 高并发 继续学习 part1 java学习路线 java编程思想 java线程 java框架 javax javaserver java技术 java ee javaapi java web java开发环境 java语言 java集合 java14 java内部类 java爬虫 javaswing java7 java编程语言
AI
助
手
产品服务
地区划分
专题活动
帮助支持
关于我们
售后咨询
7*24小时在线电话：400-100-2938
7*24小时在线 QQ：800811969
关注亿速云

亿速云公众号

手机网站二维码

Copyright © Yisu Cloud Ltd. All Rights Reserved. 2018 版权所有

广州亿速云计算有限公司粤ICP备17096448号-1 粤公网安备 44010402001142号增值电信业务经营许可证编号：B1-20181529