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

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
深入探索协同过滤：从原理到推荐模块案例

深入探索协同过滤：从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤（UserCF）2. 基于物品的协同过滤（ItemCF）3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代，推荐系统成为连接用户与内容的桥梁。本文聚焦于
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2