跳表的简单原理及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

相关文章

pandas中位数填充空值的实现示例

《pandas中位数填充空值的实现示例》中位数填充是一种简单而有效的方法,用于填充数据集中缺失的值,本文就来介绍一下pandas中位数填充空值的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是中位数填充?为什么选择中位数填充?示例数据结果分析完整代码总结在数据分析和机器学习过程中,处理缺失数

Golang HashMap实现原理解析

《GolangHashMap实现原理解析》HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持高效的插入、查找和删除操作,:本文主要介绍GolangH... 目录HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

Pandas使用AdaBoost进行分类的实现

《Pandas使用AdaBoost进行分类的实现》Pandas和AdaBoost分类算法,可以高效地进行数据预处理和分类任务,本文主要介绍了Pandas使用AdaBoost进行分类的实现,具有一定的参... 目录什么是 AdaBoost?使用 AdaBoost 的步骤安装必要的库步骤一:数据准备步骤二:模型

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

使用Pandas进行均值填充的实现

《使用Pandas进行均值填充的实现》缺失数据(NaN值)是一个常见的问题,我们可以通过多种方法来处理缺失数据,其中一种常用的方法是均值填充,本文主要介绍了使用Pandas进行均值填充的实现,感兴趣的... 目录什么是均值填充?为什么选择均值填充?均值填充的步骤实际代码示例总结在数据分析和处理过程中,缺失数

Java对象转换的实现方式汇总

《Java对象转换的实现方式汇总》:本文主要介绍Java对象转换的多种实现方式,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Java对象转换的多种实现方式1. 手动映射(Manual Mapping)2. Builder模式3. 工具类辅助映

SpringBoot请求参数接收控制指南分享

《SpringBoot请求参数接收控制指南分享》:本文主要介绍SpringBoot请求参数接收控制指南,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring Boot 请求参数接收控制指南1. 概述2. 有注解时参数接收方式对比3. 无注解时接收参数默认位置

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾