首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >有关跳跃表的干货都在这里

有关跳跃表的干货都在这里

作者头像
全菜工程师小辉
发布2019-08-16 10:10:06
3520
发布2019-08-16 10:10:06
举报

ConcurrentSkipListSet、ConcurrentSkipListMap等数据结构用的是它,更不用说Redis也广泛用它。它是一种思想,即使你不写它。

跳表的数据结构

跳表全称叫做跳跃表,简称跳表。跳表是一个随机化的数据结构,实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。

其中-1表示INT_MIN, 链表的最小值,1表示INT_MAX,链表的最大值。

跳表的性质
  1. 由很多层结构组成
  2. 每一层都是一个有序的链表
  3. 最底层(Level 1)的链表包含所有元素
  4. 如果一个元素出现在Level i的链表中,则它在Level i之下的链表也都会出现。
  5. 每个节点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素。

1. 跳表的get操作

例子:查找元素 117

  1. 比较21,比21大,往后面找
  2. 比较37, 比37大,比链表最大值小,从37的下面一层开始找
  3. 比较71, 比71大,比链表最大值小,从71的下面一层开始找
  4. 比较85,比85大,从后面找
  5. 比较117,等于117, 找到了节点。

2. 跳表的insert操作

先确定该元素要占据的层数 K(采用丢硬币的方式,这完全是随机的)

然后在 Level 1 ... Level K 各个层的链表都插入元素。

例子:插入 119, K = 2

如果 K 大于链表的层数,则要添加新的层。

例子:插入 119, K = 4

丢硬币决定K的值

插入元素的时候,元素所占有的层数完全是随机的,通过一下随机算法产生:

public int random_level() {
    int k = 1;
    while (Math.random() <= 0.5f) {
        k++;
    }
    return k;
}

相当于做一次丢硬币的实验,如果遇到正面,继续丢,遇到反面,则停止。各个元素的层数,期望值是2层。

3. 跳表的delete操作

在各个层中找到包含 x 的节点,使用标准的 delete from list 方法删除该节点。

例子:删除 71

实现步骤

  1. 定义一个跳表的Node类
  2. 私有变量,保存层数K和链表最高层最小的节点(即最左结点)
  3. 按照上面的图,写出每个函数,注意边界判断

需求只要很明确,接下来都是体力活了。代码就不写了,毕竟跳跃表只是个思想,很多细节东西都是因人而异,因业务而异。

总结

大部分编程语言中的Map类型都是通过红黑树实现的,在写程序的时候,可以直接拿过来用,不用自己再去实现一个红黑树。但是跳表并没有一个现成的实现,所以在开发中,如果要使用跳表这种数据结构,需要自己先去实现。

更多内容,欢迎关注微信公众号:全菜工程师小辉~

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-07-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 全菜工程师小辉 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • ConcurrentSkipListSet、ConcurrentSkipListMap等数据结构用的是它,更不用说Redis也广泛用它。它是一种思想,即使你不写它。
  • 跳表的数据结构
    • 跳表的性质
    • 1. 跳表的get操作
    • 2. 跳表的insert操作
      • 丢硬币决定K的值
      • 3. 跳表的delete操作
      • 实现步骤
      • 总结
      相关产品与服务
      云数据库 Redis
      腾讯云数据库 Redis(TencentDB for Redis)是腾讯云打造的兼容 Redis 协议的缓存和存储服务。丰富的数据结构能帮助您完成不同类型的业务场景开发。支持主从热备,提供自动容灾切换、数据备份、故障迁移、实例监控、在线扩容、数据回档等全套的数据库服务。
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档