文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2023-05-31 03:21

关注

跳跃链表是一种随机化数据结构,基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要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 + ")"; }}

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 资料下载
  • 历年真题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯