精华内容
下载资源
问答
  • 在JDK并发包中有很多的数据结构,最常用的有链表,哈希表等等,除了这些数据结构之外,还有一种特殊的数据结构跳表,可能大多数人都不太了解,因此,本篇文章主要介绍跳表这一数据结构的原理以及它在JDK内部的使用。...

    在JDK并发包中有很多的数据结构,最常用的有链表,哈希表等等,除了这些数据结构之外,还有一种特殊的数据结构跳表,可能大多数人都不太了解,因此,本篇文章主要介绍跳表这一数据结构的原理以及它在JDK内部的使用。

    一、什么是跳表?

    跳表(SkipList),是一种可以快速查找的数据结构,类似于平衡树。它们都可以对元素进行快速的查找。因为跳表是基于链表的(具体结构等下会将),因此,它的插入和删除效率比较高。因此在高并发的环境下,如果是平衡树,你需要一个全局锁来保证整个树的线程安全,而对于跳表,你只需要局部锁来控制即可。对于查询而言,它的时间复杂度为O(logn)。

    那么跳表具体的结构到底是怎么样的呢?下图是跳表数据结构的原理图:
    在这里插入图片描述

    可以明显看到,跳表就是一种典型的以空间换时间的数据结构。

    该算法与哈希算法的另一个区别就是:哈希算法不会保存数据的顺序,而跳表内的所有元素都是排序的。因此对于跳表进行遍历会得到一组有序的数据。

    在JDK内部,也使用了该数据结构,比如ConcurrentSkipListMap,ConcurrentSkipListSet等。下面我们主要介绍ConcurrentSkipListMap。说到ConcurrentSkipListMap,我们就应该比较HashMap,ConcurrentHashMap,ConcurrentSkipListMap这三个类来讲解。它们都是以键值对的方式来存储数据的。HashMap是线程不安全的,而ConcurrentHashMap和ConcurrentSkipListMap是线程安全的,它们内部都使用无锁CAS算法实现了同步。ConcurrentHashMap中的元素是无序的,ConcurrentSkipListMap中的元素是有序的。它们三者的具体区别可以参考具体的资料,下面主要讲解ConcurrentSkipListMap的实现原理。

    二、ConcurrentSkipListMap的实现原理

    理解了跳表的原理,ConcurrentSkipListMap的原理不难理解,在它的内部有几个重要的数据结构,首先是Node,一个Node表示一个节点,里面含有两个重要的元素key和value,还有一个next指向Node的节点表示下一个节点。
    这里写图片描述
    对于Node的所有方法,使用了CAS方法,因此是线程安全的。
    这里写图片描述
    上面两个方法一个是设置value,另一个是设置next的,具体实现可以查看源代码。

    另外一个重要的数据结构就是Index,从上面跳表的结构可以看出,我们需要知道要一个元素在哪一层,哪一个节点,因此都需要Index来管理。
    这里写图片描述
    在Index中封装了Node,并且有一个向右和向下的引用。此外,还有一个数据结构也很重要,HeadIndex,它记录每一层的表头处于哪一层,它继承自Index。
    这里写图片描述

    上面就简单介绍完了ConcurrentSkipListMap的内部重要数据结构,重点是了解跳表数据结构,理解跳表是掌握ConcurrentSkipListMap的关键。


    展开全文
  • redis 数据结构 跳表

    2018-03-03 12:12:55
    要先有跳表数据结构基础: 跳表是链表的一个变种,通过增加多余的指针,将单向链表变成多向链表,进而使跳表的查询效率和平衡二叉树看齐(平均o(logN),最坏o(N)),而且较之二叉树实现方便。 而跳表本身,有一些...

    跳表

    要先有跳表的数据结构基础:
    跳表是链表的一个变种,通过增加多余的指针,将单向链表变成多向链表,进而使跳表的查询效率和平衡二叉树看齐(平均o(logN),最坏o(N)),而且较之二叉树实现方便。
    而跳表本身,有一些比较迷的实现策略:比如,新增节点的层次是通过随机数(抛硬币)指定的,存在一个随机概率,这在redis内,概率为1/4,同时规定,层数最大为32

    结构:

    /**
     * 跳表节点
    **/
    typedef struct zskiplistNode{
        struct zskiplistLevel{
            zskiplistNode *forward;//当前层(level)指向下一节点的指针
            unsigned int span;//到下一个节点之间的距离
        } level[];
        struct zskiplistNode *backward;//指向前一个节点的指针
        double score;
        robj * obj;//存储的redis对象
    }

    要点:

    1. redis内的跳表存在一个zskiplist的结构体,内部保存一个跳表的头、尾、节点个数和当前层数
    2. redis的跳表,第一个节点是不保存数据的,而只起到连接各个层的作用
    3. 层序号是,1层表示包含所有节点的层,之后越大的层包含节点越少
    4. zskiplistLevel内包含两个属性,其中span属性表示通过 forward指针,跨过了底层的几个节点连接到当前层的下一个节点,在有序集合中,节点的rank,就是通过累加span来计算出来的
    5. 和leve内的forward指针在一个node里可以有多个不同,一个node内只有一个backward指针,表示在最底层,指向上一个节点的指针
    6. 对于score,跳表是按照score的升序排列,如果分数一样,按照obj对象的字典序排序(字典序是:1 < 11 < 111 < 2 < 221 < 23,和js默认对数字的排序方式一样)
    7. robj *obj是一个指向字符串对象的指针,字符串对象内包含一个sds,字典序就是这个sds的字典序

    redis内的使用

    有序集合的实现之一,适用范围不广

    展开全文
  • 前面学习很多类的源码过程中,底层基本都是数组和链表,今天学习第三种结构跳表(SkipList)。 ​ 跳表解决的问题 一个有序的数组如果我们要判断一个数据是否存在可以通过二分查找法非常快速的判断出来,但是如果是...

    前面学习很多类的源码过程中,底层基本都是数组和链表,今天学习第三种结构跳表(SkipList)。

    跳表解决的问题

    一个有序的数组如果我们要判断一个数据是否存在可以通过二分查找法非常快速的判断出来,但是如果是一个有序的链表结构,因为不知道链表两个节点之间的数量,就不能通过二分查找法实现了。

    那么就只能通过从头开始遍历查询,但是这种查询是最慢的方式,那么就需要通过其他方法来实现了,而跳表就能够解决这个问题。

    跳表出现过程

    链表不能快速判断数据是否存在的原因在于不能使用像二分查找法这种算法,不能实现的原因是找不到中间节点,那么我们可以通过把中间节点记录下来,这样就能够找到了。

    但是链表是在随时变化的,所以并不能记录中间节点,那么我们可以没间隔一个节点记录一下,把记录的节点组成一个新的链表,如下图:
    1第一次.png

    通过间隔保存,新的链表数量少了接近一半,这样查询起来就要快很多了,比如要查询9,那么就可以从间隔提取那个链表开始查询,查询顺序是1—>5—>8—>8(下一层)—>9。

    如果数据太长这样只经过一次抽取还是太大了,间隔链表的数据还是太长,效率还是太大,可以进行多次提取,最终结果如下图:

    2第三次提取.png

    通过这种多次抽取,最上面的链表长度已经大大的减少,尤其在数据量很大的时候能够大幅提高执行效率。

    跳表的查询

    那么跳表的查询是如何实现的呢?这里以上图为例,判断12是否在链表中。

    首先拿到最顶上的节点,如果当前节点大于12那么说明12不存在链表中,然后当前节点的右节点与12比较,发现比12大,那么节点下沉。

    下层到第二层验证右节点(第二层值为8的节点)发现比12小,切换验证值为8这个节点,然后再验证节点的右节点(第二次值为13的节点)发现比12大,所以再次下沉。

    来到第三层值为8的节点,发现它的右节点11比12小,所以切换到11节点进行验证右节点,11节点的右节点为13,比12大,所以再次下沉;

    来到第四层值为11的节点,发现它的右节点等于12,所以存在。如果发现小于12那么需要继续往右走,发现大于12则往下走,如果下节点为null则查找结束,说明不存在。

    验证的过程如下图:

    3查询.png

    判断的流程总的来说比较简单,拿到最顶层最左边的节点,如果当前节点比判断的值大则直接不存在,接下来就是当前节点的右节点与值得比较,根据判断结果分三种情况:

    相等说明存在,也就是找到了;

    右节点较大,往下沉,如果下层为null,则说明到了最底层,所以不存在;

    右节点较小,切换右节点继续验证,右节点的节点为null则下沉,下沉为null则说明不存在;

    总结

    今天只是简单的梳理了跳表的原理,但是也可以看出来跳表是一个最典型的空间换时间解决方案,而且只有在数据量较大的情况下才能体现出来优势。而且应该是读多些少的情况下才能使用,所以它的适用范围应该还是比较有限的。

    Java程序员日常学习笔记,如理解有误欢迎各位交流讨论!

    Java程序员日常学习笔记

    展开全文
  • 前面学习很多类的源码过程中,底层基本都是数组和链表,今天学习第三种结构跳表(SkipList)。跳表解决的问题一个有序的数组如果我们要判断一个数据是否存在可以通过二分查找法非常快速的判断出来,但是如果是一个有序...

    前面学习很多类的源码过程中,底层基本都是数组和链表,今天学习第三种结构跳表(SkipList)。

    跳表解决的问题

    一个有序的数组如果我们要判断一个数据是否存在可以通过二分查找法非常快速的判断出来,但是如果是一个有序的链表结构,因为不知道链表两个节点之间的数量,就不能通过二分查找法实现了。

    那么就只能通过从头开始遍历查询,但是这种查询是最慢的方式,那么就需要通过其他方法来实现了,而跳表就能够解决这个问题。

    跳表出现过程

    链表不能快速判断数据是否存在的原因在于不能使用像二分查找法这种算法,不能实现的原因是找不到中间节点,那么我们可以通过把中间节点记录下来,这样就能够找到了。

    但是链表是在随时变化的,所以并不能记录中间节点,那么我们可以每间隔一个节点记录一下,把记录的节点组成一个新的链表,如下图:

    55930996_20201021092726052648C106322T284IL40Q_wm.jpg

    通过间隔保存,新的链表数量少了接近一半,这样查询起来就要快很多了,比如要查询9,那么就可以从间隔提取那个链表开始查询,查询顺序是1—>5—>8—>8(下一层)—>9。

    如果数据太长这样只经过一次抽取还是太大了,间隔链表的数据还是太长,效率还是太大,可以进行多次提取,最终结果如下图:

    55930996_202010210927260573A01SICSFE83K8UPCNA_wm.jpg

    通过这种多次抽取,最上面的链表长度已经大大的减少,尤其在数据量很大的时候能够大幅提高执行效率。

    跳表的查询

    那么跳表的查询是如何实现的呢?这里以上图为例,判断12是否在链表中。

    首先拿到最顶上的节点,如果当前节点大于12那么说明12不存在链表中,然后当前节点的右节点与12比较,发现比12大,那么节点下沉。

    下层到第二层验证右节点(第二层值为8的节点)发现比12小,切换验证值为8这个节点,然后再验证节点的右节点(第二次值为13的节点)发现比12大,所以再次下沉。

    来到第三层值为8的节点,发现它的右节点11比12小,所以切换到11节点进行验证右节点,11节点的右节点为13,比12大,所以再次下沉;

    来到第四层值为11的节点,发现它的右节点等于12,所以存在。如果发现小于12那么需要继续往右走,发现大于12则往下走,如果下节点为null则查找结束,说明不存在。

    验证的过程如下图:

    55930996_2020102109272605897YNXVTW9VESGESLJS5_wm.jpg

    判断的流程总的来说比较简单,拿到最顶层最左边的节点,如果当前节点比判断的值大则直接不存在,接下来就是当前节点的右节点与值得比较,根据判断结果分三种情况:

    相等说明存在,也就是找到了;

    右节点较大,往下沉,如果下层为null,则说明到了最底层,所以不存在;

    右节点较小,切换右节点继续验证,右节点的节点为null则下沉,下沉为null则说明不存在;

    总结

    今天只是简单的梳理了跳表的原理,但是也可以看出来跳表是一个最典型的空间换时间解决方案,而且只有在数据量较大的情况下才能体现出来优势。而且应该是读多些少的情况下才能使用,所以它的适用范围应该还是比较有限的。

    Java程序员日常学习笔记,如理解有误欢迎各位交流讨论!

    55930996_202010210927260620IQRIY1NU5LKDU4BAQN_wm.jpg

    展开全文
  • 最初知道跳表是看到redis源码里用了跳表做实时排序,跳表的模型如下 ...3、当有玩家数据变动  1)如果排行榜已满,先判断Score是否比最后一名低,如果是直接抛弃  2)如果自己在排行榜,是 ,如果在帮...
  • 前面学习很多类的源码过程中,底层基本都是数组和链表,今天学习第三种结构跳表(SkipList)。跳表解决的问题一个有序的数组如果我们要判断一个数据是否存在可以通过二分查找法非常快速的判断出来,但是如果是一个有序...
  • 跳表简介跳表是平衡树的一种替代的数据结构,但是和红黑树不相同的是,跳表对于树的平衡的实现是基于一种随机化的算法的,这样也就是说跳表的插入和删除的工作是比较简单的。我们知道,普通单链表查询一个元素的时间...
  • 跳表是平衡树的一种替代的数据结构,但是和红黑树不相同的是,跳表对于树的平衡的实现是基于一种随机化的算法的,这样也就是说跳表的插入和删除的工作是比较简单的。  下载地址 : ...
  • 数据结构跳表

    2017-03-18 11:15:41
    数据结构跳表的完整代码
  • 数据结构-跳表

    2019-08-02 12:13:19
    数据结构-跳表 转载声明 本文大量内容系转载自以下文章,有删改,并参考其他文档资料加入了一些内容: HBase内存结构之跳表数据结构浅析 作者:mango_song 1 概述 最近学习HBase源码时发现HRegion在sotre管理上...
  • 数据结构跳表

    2020-06-26 20:32:35
    7- 13 的记录,就不用从头开始查找了,只要在上图中的二级索引开始找即可,遍历三次即可找到链表的区间位置,时间复杂度是 O(logn),非常快,这样看来,跳表是能满足我们的需求的,实际上它的结构已经和 B+ 树非常...
  • 跳表数据结构和复杂度 跳表的索引 ConcurrentSkipListMap数据结构 前面分析过二分查找的时间复杂度是O(logN),但是只能作用于数组的数据结构之上,并且有序。那么基于链表是否可以实现添加、删除、查询的时间...
  • 数据结构——跳表

    2019-01-30 14:32:45
    2、跳表是一个动态数据结构,支持快速的插入、删除、查找,具有替代红黑树的能力。 3、跳表就是链表增加多级索引的结构。通常跳表的时间复杂度为O(3logn),即O(logn)。查找的时间复杂度和二分查找相同。 4、跳表...
  • 数据结构与算法——跳表 跳表类似链表,也是一种支持动态操作的数据结构 跳表每层选取若干节点作为索引创建到上层,这样自顶向下寻路时会比链表少遍历很多节点 package com.lcy.data_structure_and_algorithm; ...
  • 跳表是一种随机化的数据结构 跳表具有如下性质: 由很多层结构组成 每一层都是一个有序的链表 最底层(Level 1)的链表包含所有元素 如果一个元素出现在 Level i 的链表中,则它在 Level i 之下的链表也都会出现。 ...
  • 数据结构跳表

    2019-05-05 14:51:08
    而实际上,我们只需要对链表稍加改造,就可以实现类似“二分”的查找算法,这种改造之后的数据结构叫作跳表(Skip List)。 1. 何为跳表? 对于一个单链表,即使链表是有序的,如果我们想要在其中查找某个数据,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,570
精华内容 628
关键字:

数据结构跳表

数据结构 订阅