跳跃表的原理和实现(Java)_跳表的原理java实现-程序员宅基地

技术标签: Java开发  java  链表  数据结构  

一、高效查找算法

我们在实际开发中经常会有在一堆数据中查找一个指定数据的需求,而常用的支持高效查找算法的实现方式有以下几种:

  1. 有序数组:这种方式的存储结构,优点是支持数据的随机访问,并且可以采用二分查找算法降低查找操作的复杂度。缺点同样很明显,插入和删除数据时,为了保持元素的有序性,需要进行大量的移动数据的操作。
  2. 二叉查找树:如果需要一个既支持高效的二分查找算法,又能快速的进行插入和删除操作的数据结构,那首先就是二叉查找树莫属了。缺点是在某些极端情况下,二叉查找树有可能变成一个线性链表。
  3. 平衡二叉树:二叉树表示不服,于是基于二叉查找树的优点,对其缺点进行改进,引入了平衡的概念。根据平衡算法的不同,具体实现有AVL树、B树(B-Tree)、B+树(B+Tree)、红黑树 等等。但是平衡二叉树的实现多数比较复杂,较难理解。
  4. 跳跃表:同样支持对数据进行高效的查找,插入和删除数据操作也比较简单,最重要的就是实现比较平衡二叉树真是轻量几个数量级。缺点就是存在一定数据冗余。

二、跳跃表

跳跃表(SkipList)是一种可以替代平衡树的数据结构。跳跃表让已排序的数据分布在多层次的链表结构中,默认是将 Key 值升序排列的,以 0-1 的随机值决定一个数据是否能够攀升到高层次的链表中。它通过容许一定的数据冗余,达到 “以空间换时间” 的目的。

跳跃表的效率和 AVL 相媲美,查找、添加、插入、删除操作都能够在 O(LogN) 的复杂度内完成。讲了那么多,下面就直接进入主题,详细的看一看跳跃表是怎么实现的。

三、跳跃表的实现

在这里插入图片描述

上面这张图就是一个跳跃表的实例,先说一下跳跃表的构造特征:

  • 一个跳跃表应该有若干个层(Level)链表组成;

  • 跳跃表中最底层的链表包含所有数据; 每一层链表中的数据都是有序的;

  • 如果一个元素 X 出现在第i层,那么编号比 i 小的层都包含元素 X;

  • 第 i 层的元素通过一个指针指向下一层拥有相同值的元素;

  • 在每一层中,-∞ 和 +∞ 两个元素都出现(分别表示 INT_MIN 和 INT_MAX);

  • 头指针(head)指向最高一层的第一个元素;

1、定义链表中节点的模型

在这里插入图片描述


Java 代码实现如下:

public class SkipListEntry<T> {
    
    // data
    public Integer key;
    public T value;

    // links
    public SkipListEntry up;
    public SkipListEntry down;
    public SkipListEntry left;
    public SkipListEntry right;

    // constructor
    public SkipListEntry(Integer key, T value) {
    
        this.key = key;
        this.value = value;
    }
    
    // methods...
}

可以看到节点模型主要分为2个部分。

data 部分包含具体的存储数据,这里为了不引入其他杂乱的问题,使用 Integer 作为 key 的类型,Object 作为value 的类型。

links 部分包含4个指针,分别是 up、down、left、right,单从名字上就能够明白它们的作用。

2、跳跃表本身的模型

public class SkipList {
    // 节点数量
    public int n;
    // 节点最大层数
    public int h;
    
    // 第一个节点
    SkipListEntry head;
    // 最后一个节点
    SkipListEntry tail;
    
    public Random r;
}

Note: Random 类的实例对象 r 用来决定新添加的节点是否能够向更高一层的链表攀升。

3、初始化跳跃表的实例

构造函数将初始化一个空的跳跃表看起来像下面这样:

在这里插入图片描述
构造函数的 Java 代码:

public SkipList() {
    // 创建 head 节点
    this.head = new SkipListEntry(Integer.MIN_VALUE, null);
    // 创建 tail 节点
    this.tail = new SkipListEntry(Integer.MAX_VALUE, null);

    // 将 head 节点的右指针指向 tail 节点
    this.head.right = tail;
    // 将 tail 节点的左指针指向 head 节点
    this.tail.left = head;

    this.h = 0;
    this.n = 0;
    this.r = new Random();
}

4、基本操作


跳跃表需要实现查找、插入、移除这些基本操作:

  • get(Integer key) : 根据 key 值查找某个元素

  • put(Integer key, Object value) :插入一个新的元素,元素已存在时为修改操作

  • remove(Integer key): 根据 key 值删除某个元素


虽然看似是 3 个不同的操作,但是究其本质,要实现这 3 个操作,都得先找到某个元素或是定位到一个元素,好在下一个位子插入新元素。那么,我们就先把这个 findEntry 的方法实现吧。

在这里插入图片描述

上面的图示使用紫色的箭头画出了在一个 SkipList 中查找 key 值 50 的过程。简述如下:

  1. 从 head 出发,因为 head 指向最顶层(top level)链表的开始节点,相当于从顶层开始查找;

  2. 移动到当前节点的右指针(right)指向的节点,直到右节点的 key 值大于要查找的 key 值时停止;

  3. 如果还有更低层次的链表,则移动到当前节点的下一层节点(down),如果已经处于最底层,则退出;

重复第 2 步和第 3 步,直到查找到 key 值所在的节点,或者不存在而退出查找;

Java 代码实现如下:

private SkipListEntry findEntry(Integer key) {
    
    // 从head头节点开始查找
    SkipListEntry p = head;

    while (true) {
    
        // 从左向右查找,直到右节点的key值大于要查找的key值
        while (p.right.key <= key) {
    
            p = p.right;
        }

        // 如果有更低层的节点,则向低层移动
        if (p.down != null) {
    
            p = p.down;
        } else {
    
            break;
        }
    }

    // 返回p,!注意这里p的key值是小于等于传入key的值的(p.key <= key)
    return p;
}


注意以下几点:

  1. 如果传入的 key 值在跳跃表中存在,则 findEntry 返回该对象的底层节点;

  2. 如果传入的 key 值在跳跃表中不存在,则 findEntry 返回跳跃表中 key 值小于 key,并且 key 值相差最小的底层节点;


示例,在跳跃表中查找 key=42 的元素节点,将返回 key=39 的节点。如下图所示:


在这里插入图片描述
基于 findEntry 方法,我们就能很容易的实现前面所说的一些操作了。

get方法

public Object get(Integer key) {
    
    SkipListEntry p = findEntry(key);

    if (p.key.equals(key)) {
    
        return p.value;
    } else {
    
        return null;
    }
}

put方法

一些需要注意的步骤:

  1. 如果 put 的 key 值在跳跃表中存在,则进行修改操作;

  2. 如果 put 的 key 值在跳跃表中不存在,则需要进行新增节点的操作,并且需要由 random 随机数决定新加入的节点的高度(最大level);

  3. 当新添加的节点高度达到跳跃表的最大 level,需要添加一个空白层(除了-oo 和 +oo 没有别的节点)

下面我们一步一步的通过图示看一下插入节点的过程:

在这里插入图片描述
第一步,查找适合插入的位子在这里插入图片描述
第二步,在查找到的p节点后面插入新增的节点q

在这里插入图片描述
第三步,重复下面的操作,使用随机数决定新增节点的高度

  1. 从p节点开始,向左移动,直到找到含有更高level节点的节点;

  2. 将p指针向上移动一个level;

  3. 创建一个和q节点data一样的节点,插入位子在跳跃表中p的右方和q的上方;

  4. 直到随机数不满足向上攀升的条件为止;

图示如下:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述


只要随机数满足条件,key=42 的节点就会一直向上攀升,直到它的 level 等于跳跃表的高度(height)。这个时候我们需要在跳跃表的最顶层添加一个空白层,同时跳跃表的 height+1,以满足下一次新增节点的操作。

在这里插入图片描述
Java代码实现如下:

public Object put(Integer key, Object value) {
    

    SkipListEntry p, q;
    int i = 0;

    // 查找适合插入的位子
    p = findEntry(key);

    // 如果跳跃表中存在含有key值的节点,则进行value的修改操作即可完成
    if (p.key.equals(key)) {
    
        Object oldValue = p.value;
        p.value = value;
        return oldValue;
    }

    // 如果跳跃表中不存在含有key值的节点,则进行新增操作
    q = new SkipListEntry(key, value);
    q.left = p;
    q.right = p.right;
    p.right.left = q;
    p.right = q;

    // 再使用随机数决定是否要向更高level攀升
    while (r.nextDouble() < 0.5) {
    

        // 如果新元素的级别已经达到跳跃表的最大高度,则新建空白层
        if (i >= h) {
    
            addEmptyLevel();
        }

        // 从p向左扫描含有高层节点的节点
        while (p.up == null) {
    
            p = p.left;
        }
        p = p.up;

        // 新增和q指针指向的节点含有相同key值的节点对象
        // 这里需要注意的是除底层节点之外的节点对象是不需要value值的
        SkipListEntry z = new SkipListEntry(key, null);

        z.left = p;
        z.right = p.right;
        p.right.left = z;
        p.right = z;

        z.down = q;
        q.up = z;

        q = z;
        i = i + 1;
    }

    n = n + 1;

    // 返回null,没有旧节点的value值
    return null;
}

remove方法

删除节点的操作相对 put 就比较简单了,首先查找到包含 key 值的节点,将节点从链表中移除,接着如果有更高 level 的节点,则 repeat 这个操作即可。

Java代码实现如下:

public Object remove(Integer key) {
    
    SkipListEntry p, q;

    p = findEntry(key);

    if (!p.key.equals(key)) {
    
        return null;
    }

    Object oldValue = p.value;
    while (p != null) {
    
        q = p.up;
        p.left.right = p.right;
        p.right.left = p.left;
        p = q;
    }
    return oldValue;
}

跳跃表的原理和实现到这里就结束了。

还有需要说明的一点是:跳跃表每次运行的结果是不一样的,这就是为什么说跳跃表是属于随机化数据结构。(Random的存在导致的)

四、跳跃表在Java中的应用

  • ConcurrentSkipListMap:在功能上对应HashTable、HashMap、TreeMap;

  • ConcurrentSkipListSet : 在功能上对应HashSet;

确切的说,SkipList 更像 Java 中的 TreeMap ,TreeMap 基于红黑树(一种自平衡二叉查找树)实现的,时间复杂度平均能达到 O(log n)。

HashMap 是基于散列表实现的,查找时间复杂度平均能达到 O(1)。ConcurrentSkipListMap 是基于跳跃表实现的,查找时间复杂度平均能达到 O(log n)。

ConcurrentSkipListMap 具有 SkipList 的性质 ,并且适用于大规模数据的并发访问。多个线程可以安全地并发执行插入、移除、更新和访问操作。与其他有锁机制的数据结构在巨大的压力下相比有优势。

TreeMap 插入数据时平衡树采用严格的旋转操作(比如平衡二叉树有左旋右旋)来保证平衡,因此 SkipList 比较容易实现,而且相比平衡树有着较高的运行效率。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lujianhao_ios/article/details/108372005

智能推荐

Mybatis工作流程,附带mybatis的mapper文件和config配置文件模板。mapper文件和dao接口的关系——xml中的namespace和sql标签id命名要求。_使用dao、domain、mapper.xml的关系-程序员宅基地

文章浏览阅读486次。1. Mybatis工作流程1.1 使用MySQL创建数据库并生成一个表,如下图。_使用dao、domain、mapper.xml的关系

余弦相似度和欧氏距离_欧氏距离和余弦相似度-程序员宅基地

文章浏览阅读365次。余弦相似度和欧氏距离Photo by Markus Winkler on Unsplash Markus Winkler在Unsplash上拍摄的照片 This is a quick and straight to the point introduction to Euclidean distance and cosine similarity with a focus on NLP. 这是对欧..._in the graph below

解决Flutter 中的 Android sdkmanager tool not found 问题_flutter android sdkmanager not found-程序员宅基地

文章浏览阅读2.7k次。解决 Flutter 中的 Android sdkmanager tool not found 问题1. 问题2.解决1. 问题1.1 flutter doctorPS C:\Windows\system32> flutter doctorDoctor summary (to see all details, run flutter doctor -v):[√] Flutter (..._flutter android sdkmanager not found

区块链的应用_传统证明体系受权威机构人为影响较大-程序员宅基地

文章浏览阅读3.4k次。一,资产及其区块链化1,资产的核心要素包括:控制权,价值,流动性。2,传统资产管控体系与模式存在问题:资产所有权失控流动性缺失品质保证依赖品牌供需失衡区块链与传统信任,物联网的有机结合,可解决区块链链上资产与链下资产的一一匹配。二,商业模式与区块链三,区块链存证传统证明体系具有如下问题:1,受权威机构人为影响较大2,假证泛滥3,证明成本较高4,防伪成本高,携带不便。5,假冒,借用。区块链存证具有:防伪性,便捷性,低廉性,安全性的优点。区_传统证明体系受权威机构人为影响较大

坎坎坷坷的深度学习之路(三)-Hello world(2)-------MNIST数据集1-MNIST格式_mnist-1, mnist-2, mnist-3-程序员宅基地

文章浏览阅读358次。上一次说了些来自官网,无聊透顶的tf介绍,这次开始研究MNIST。识别之前先来关注一下MNIST的文件格式。MNIST的数据集可以从 官网 处下载,一共包含4个文件(点击下面的文件名可直接下载)train-images-idx3-ubyte.gz: training set images (9912422 bytes) train-labels-idx1-ubyte.gz: tr_mnist-1, mnist-2, mnist-3

Linux修改用户名(主机名)-程序员宅基地

文章浏览阅读1.2k次,点赞2次,收藏7次。centos 7修改方式:hostnamectl set-hostname james_bobo reboot 或者直接vi /etc/hostname添加内容:james_bobo 检查修改效果

随便推点

Navicat 连接远程服务器失败_navicat连不上远程数据库-程序员宅基地

文章浏览阅读1.2k次。Navicat 连接远程服务器失败_navicat连不上远程数据库

nginx 设置开机自启动_nginx自启动-程序员宅基地

文章浏览阅读1w次,点赞2次,收藏23次。一、下载在windows下实现开机自启动需要一个开源项目Windows Service Wrapper 来实现。我用的是这个版本。下载下来,放在Nginx根目录下下载下来,放在Nginx根目录下,名字改为start-nginx.exe,再新建一个txt文件,名字改为start-nginx.xml,注意拓展名前面的名字要保持一致。二、配置文件在start-nginx.xml文件中添加如下代码:复制代码如注释所示,三个路径地方要修改。三、安装打开cmd进入到nginx根目录,输入start-nginx.e_nginx自启动

Java8通过Function获取字段名称_sfunction java-程序员宅基地

文章浏览阅读2.0k次,点赞2次,收藏5次。Java8通过Function获取字段名称_sfunction java

利用LNMP环境搭建属于自己的第一个个人博客_lnmp部署个人博客网站,要求提交个人博客首页在线-程序员宅基地

文章浏览阅读600次。利用LNMP环境搭建属于自己的个人博客一.引子:相对与LAMP,LNMP环境搭建就显得简单的多了,其中不同便是Apache和Nginx服务的不同,接下来笔者会重点整理我们网络服务的重点Apache和Nginx服务。现在让我们愉快地搭建属于我们的第二个技术博客吧。记得准备换下面环境的软件哦,可以去官网下载,我们还是进行源码包安装。二.搭建博客第一步:Nginx 安装:1.下载LNMP镜像:rz -e2.创建挂载目录:mkdir /mut/iso -p3.挂载:mount -o loop L_lnmp部署个人博客网站,要求提交个人博客首页在线

《深入理解C++11》笔记–右值引用:移动语义和完美转发_深入理解c++11 is_lvalue_reference-程序员宅基地

文章浏览阅读5.4k次,点赞9次,收藏56次。上一篇:《深入理解C++11》笔记–构造函数 这篇文章介绍的了第三章中右值引用相关的内容。在介绍该内容之前,会对一些相关问题进行解释,便于理解后面的内容。 指针成员和拷贝构造 当一个类中含有指针成员时,由于默认的拷贝构造函数只会进行浅拷贝,所以当我们写出一下代码时:class Base{public: Base():data(new int(0)){} //Base..._深入理解c++11 is_lvalue_reference

华南X79 在Windows server 2022下HyperV启用 SRIOV_hyper sriov-程序员宅基地

文章浏览阅读195次。华南X79 在Windows server 2022下HyperV启用 SRIOV_hyper sriov

推荐文章

热门文章

相关标签