跳表的简单原理及Java实现

2024-04-04 21:38
文章标签 java 简单 实现 原理 跳表

本文主要是介绍跳表的简单原理及Java实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 

跳表

跳表是一种简单,高效的快速查找结构,实现起来成本最小,并且速度也很快,只需要一个图就可以完美的解释跳跃表的样子,而且对于编程人员来说,要实现一个跳跃表看着图就能实现,以下就是跳跃表的结构图,没有什么难度。

图片描述

跳跃表有几个特点,这种特点对于某些类型的查询是有相当的效率提升的。

  • 它是有序的,跳跃表的特点就是有序的,所以对于一些有序类型的数据,比如整数,日期这种,用跳跃表可以进行范围查找。

  • 在构建跳跃表和查询跳跃的复杂度一致,所以也比较适合于在线的实时索引,可以来一个文档,一边查找就一边知道要如何进行插入操作了。

  • 保存到磁盘和从磁盘载入也比较简单,因为本质上是几个链表,所以保存的时候可以按照数组的方式分别保存几个数组就可以了。

在lucene中,跳跃表并没有用来存储字典,而是用来存储docid链,这里后面我们说lucene底层和Elasticsearch的时候再说具体结构吧,这篇我们仅用来讨论用跳跃表存字典的情况。

对于跳跃表,我们看看有一些什么样的优化方式可以让其更加适应一些场景。优化的话,我们一般从空间时间两个方面来考虑一个优化,对于空间的话,又分成内存空间优化和磁盘空间优化,当然一般首先考虑内存的优化,对于时间来说,也分成构建时间查询时间两个方面来优化,空间和时间是两个相互矛盾的优化,具体到实际操作上如何取舍就要看具体的场景了。

空间优化

  • 如果我们的内存空间不够或者说跳跃表存储的序列太长了,那么我们可以把跳跃表的最底层的链表存储在磁盘上,这是一次优化情况,那么检索的时候需要一次到多次磁盘才能检索到数据,相当于用一部分性能来获得更大的数据加载能力。

  • 如果还需要继续优化的话,那么可以把上面几层的节点的数据项变成指针,都指向磁盘的偏移地址上,那么就更加的节省空间了,这样又牺牲了一部分检索性能,因为每一次读取一个节点,不管是不是底层节点,都需要读取一次磁盘来获得数据,对于上面两个优化方式,对应的数据结构的图如下,可以看到这样优化下去,内存的使用量会变得很小了。

图片描述

但是上图这种存储方式不适合动态的增加或者删除节点,因为一次这样的更新操作需要操作好几次磁盘,并且会导致磁盘上各个节点是不连续的,非常影响效率,所以比较适合那种写入以后就不会变化的跳跃表的情况。

时间优化

  • 最简单的时间优化,那就是把数据全部加载到内存,直接查询速度就快起来了,这个没什么难度,当然也可用用LRU这种缓存算法来折中一下,不消耗太大的空间并且也比直接放磁盘要快一些,或者用mmap让操作系统来帮你做这个事情也可以,不过使用LRU或者mmap的话,编程的难度和数据结构的设计难度就会要变难不少,得看你实现出来的成本了。

  • 还有一种方式就是在查找算法上优化一下,用二分查找代替直接遍历,这也只适合静态的情况,需要修改一下数据结构,将每一层的链表变成数组载入到内存中,这样查找的时候可以通过二分快速的定位到节点上。

图片描述

  • 跳跃表的层级的增加,一般情况下是通过一个概率来计算是否要增加层级节点的,但是对于一些特殊的类型,其实在构建跳跃表的时候是可以特殊处理的,比如跳跃表用来存储时间序列,那么我们其实可以每当时间过去了一分钟或者一小时或者一天就增加一个层级,假设最小的时间维度是秒,如果一分钟和一小时增加层级的话,那么一天的数据就是三层,而且第一层最多24个节点,第二层最多1440个节点,最底层86400个节点,把第一层和第二层完全载入内存的话应该说没有任何压力,甚至为了查询速度,第一层和第二层节点数固定下来,就是24和1440,这样查询的话都不用遍历链表了,直接可以通过运算就能求出下标然后直接跳到最底层上面来了。这是个典型的用了一定的内存空间来交换出更快的查询时间。

图片描述

上图中的底层表示秒,第二层表示分钟,第一层表示小时,那个红色的节点表示那一分钟其实是没数据的,为了把节点数固定下来虚拟出来的节点,这样可以提高查询的效率。

优化的取舍

上面两个大类型的优化,其实很多地方是矛盾的,具体取舍的时候就要看你的业务场景了,假设需要用跳跃表来存储你的主键,你的业务场景是更新操作很少,查询操作主要针对其他字段而非主键的话,那么底层存磁盘上,上面几层的数据项也存磁盘上,并且通过LRU或者mmap交换内存和磁盘空间的跳跃表比较适合你。如果用来存储分词后的关键字的话,因为中文分词以后关键词的量级一般在几十万这个级别,那么直接载入内存的话也能接受,所以直接加载到内存的方式可能更适合你。

Java实现

/** * Licensed to the Apache Software Foundation (ASF) under one or more* contributor license agreements.  See the NOTICE file distributed with* this work for additional information regarding copyright ownership.* The ASF licenses this file to You under the Apache License, Version 2.0* (the "License"); you may not use this file except in compliance with* the License.  You may obtain a copy of the License at**     http://www.apache.org/licenses/LICENSE-2.0** Unless required by applicable law or agreed to in writing, software* distributed under the License is distributed on an "AS IS" BASIS,* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.* See the License for the specific language governing permissions and* limitations under the License.**/
package com.tompai.skiplist3;
import java.util.Random;
import java.util.Iterator;
import java.util.NoSuchElementException;
/*** @desc: demo* @name: SkipList.java* @author: tompai* @email:liinux@qq.com* @createTime: 2020年1月1日 下午10:59:30* @history:* @version: v1.0*/
public class SkipList<T extends Comparable<? super T>> {static final int POSSIBLE_LEVELS = 33;// Dummy header & tail is created.private Entry<T> head, tail;// maxLevel is the level equal to the longest next[]public int size, maxLevel;// last[i]: Entry at which search came down from level iprivate Entry<T>[] last; // used by find// distanceTraversed[i]: distance traversed on level i,// as search came down from last[i] to level i-1private int[] distanceTraversed; // used for updating span[]private Random rand; // for random height (like using coin-flip)static class Entry<E> {E element;Entry<E>[] next;Entry<E> prev; // prev is optional? NOPE!private int height;// span[i]: storing distance of the Entry in next[i]// from the current Entryint[] span; // for indexing// Parameterized Constructor:public Entry(E x, int level) {element = x;next = new Entry[level];height = level;span = new int[level];}// Returns the element of this Entrypublic E getElement() {return element;}}// Default Constructorpublic SkipList() {head = new Entry<T>(null, POSSIBLE_LEVELS);tail = new Entry<T>(null, POSSIBLE_LEVELS);size = 0;maxLevel = 1;last = new Entry[POSSIBLE_LEVELS];distanc

这篇关于跳表的简单原理及Java实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/876881

相关文章

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4