首页 > 编程语言 >详解Java中跳跃表的原理和实现

详解Java中跳跃表的原理和实现

时间:2023-07-01 22:46:34浏览次数:43  
标签:Node Java forwards int private curLevel 详解 value 跳跃

原文链接及讲解: 详解Java中跳跃表的原理和实现

java跳表实现

import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * java跳表实现
 *
 * @author lyn
 * @date 2023/6/30 18:50
 */
public class OwnSkipList {
    private static final int MAX_LEVEL = 16;
    private static final float P = 0.5f;
    private static final int MAX_INT = 0x7fffffff;

    class Node {
        int val;
        Node[] forwards = new Node[MAX_LEVEL];
    }

    private Node head;
    private int curLevel;
    private Node[] upData;

    public OwnSkipList() {
        init();
    }

    /**
     * 初始化
     */
    private void init() {
        curLevel = 0;
        head = getNewNode(-MAX_INT);
        upData = new Node[MAX_LEVEL];
        for (int i = 0; i < MAX_LEVEL; i++) {
            upData[i] = new Node();
        }
    }


    private Node getNewNode(int value) {
        Node node = new Node();
        for (int i = 0; i < MAX_LEVEL; i++) {
            node.forwards[i] = null;
        }
        node.val = value;
        return node;
    }

    /**
     * 插入元素
     *
     * @param value 值
     */
    public void insert(int value) {
        int lev = randomLevel();
        if (lev > curLevel) {
            curLevel = lev;
        }
        //寻找每层最接近的元素
        find(value);
        //创建一个新节点
        Node newNode = getNewNode(value);
        //插入操作
        for (int i = 0; i <= lev; i++) {
            newNode.forwards[i] = upData[i].forwards[i];
            upData[i].forwards[i] = newNode;
        }
    }

    public void delete(int value) {
        Node zeroLevelNode = find(value);
        //如果零层都没有,则结束
        if (zeroLevelNode.forwards[0] == null || zeroLevelNode.forwards[0].val != value) {
            return;
        }
        System.out.println("删除元素 " + value + "\n");
        // 删除操作
        for (int i = curLevel; i >= 0; i--) {
            if (upData[i].forwards[i] != null && upData[i].forwards[i].val == value) {
                upData[i].forwards[i] = upData[i].forwards[i].forwards[i];
            }
        }
        //删除空链
        while (curLevel > 0 && head.forwards[curLevel] == null) {
            curLevel--;
        }
    }

    /**
     * 查找最接近val的元素
     *
     * @param value 值
     */
    private Node find(int value) {
        Node tem = head;
        for (int i = curLevel; i >= 0; i--) {
            while (tem.forwards[i] != null && tem.forwards[i].val < value) {
                tem = tem.forwards[i];
            }
            //记录搜索过程中各级走过的最大节点位置
            upData[i] = tem;
        }
        return tem;
    }

    /**
     * 随机产生插入元素高度
     *
     * @return 高度
     */
    private int randomLevel() {
        int lev = 0;
        while (Math.random() < P && lev < MAX_LEVEL - 1) {
            lev++;
        }
        return lev;
    }

    public void print(int i) {
        // 遍历
        Node p = head.forwards[i];
        if (p == null) {
            return;
        }
        while (p != null) {
            System.out.printf("%d  ", p.val);
            p = p.forwards[i];
        }
        System.out.printf("\n");
    }

    /**
     * 遍历所有层
     */
    public void printAll() {
        for (int i = curLevel; i >= 0; i--) {
            System.out.printf("curLevel %d:  ", i);
            print(i);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        OwnSkipList skipList = new OwnSkipList();
        List<Integer> list = Stream.iterate(1, s -> s + 1).limit(50).collect(Collectors.toList());
        Collections.shuffle(list);
        for (Integer element : list) {
            skipList.insert(element);
        }
        skipList.printAll();

        skipList.delete(21);

        skipList.printAll();
    }
}

标签:Node,Java,forwards,int,private,curLevel,详解,value,跳跃
From: https://www.cnblogs.com/lyn8100/p/17515362.html

相关文章

  • 什么是 CSR、SSR、SSG、ISR - 渲染模式详解
    本文以React、Vue为例,介绍下主流的渲染模式以及在主流框架中如何实现上述的渲染模式。前置知识介绍看渲染模式之前我们先看下几个主流框架所提供的相关能力,了解的可跳到下个章节。挂载组件到DOM节点这是主流框架最基本的能力,就是将组件渲染到指定的DOM节点上。在React......
  • Map详解
    背景介绍我们在日常的开发的过程中,一直都有在使用Map存储数据。但是Map的底层原理,以及Map的Key值为什么不能重复,Map中的key值和Hash有什么关系大家都清楚吗,如果我们把这些内容都搞清楚了我们在使用Map的时候才会得心应手,排查关于Map相关的问题才会更加的容易,才会更快的去定位问题出......
  • 暑假Java学习第一周
    6.25先跟着黑马了解认识了一下Java的历史、现状、火爆的原因等。然后开始正式学习Java的编程。安装Oracle的JDK在电脑上配置环境变量,下载之后自动配置完成。然后编写HelloWorld.java程序,win+r——cmd调用命令面板来编译程序,但是未运行成功。具体问题是javac运行不报错(并且没有......
  • paging_init 详解
    建立二级页表项由set_pte_ext宏实现,实际上底层调用的是在内核启动之初获取的list->processor->set_pte_ext,这是处理器相关的处理函数,对应的函数实现为cpu_v7_set_pte_ext,在arch/arm/mm/proc-v7-2level.S中。ENTRY(cpu_v7_set_pte_ext)#ifdefCONFIG_MMUstrr1,[......
  • Java使用joml计算机图形学库,将3D坐标旋转正交投影转为2D坐标
    最近遇到了一个困扰我许久的难题,现将解决方案分享出来由于我们的项目侧重点在前端绘图,导致了前后端工作量不协调,我后端接口很快就能写完,而前端一个图要画好久,领导见状将前端的任务分到后端一部分用Java代码来实现,然后给前端提供接口而我接到的任务就是将Echarts中绘制三维图形的......
  • Java基础-Day08
    Java基础-Day08面向对象Java面向对象学习的三条主线packagecom.chenteng.java;/**Java面向对象学习的三条主线*1.Java类及类的成员:属性、方法、构造器;代码块、内部类*2.面向对象的三大特征:封装性、继承性、多态性、抽象性*3.其他关键字:this、super、sta......
  • 【狂神说Java】Java零基础学习笔记-预料
    【狂神说Java】Java零基础学习笔记-预料预料01:学习准备:博客博客,英文名为Blog,它的正式名称为网络日记为什么要写博客?需要总结和思考。有时候我们一直在赶路,却忘了放慢脚步提升文笔组织能力提升学习总结能力提升逻辑思维能力帮助他人,结交朋友冰冻三尺非一日之寒,写......
  • 从头学Java17-Lambda表达式
    Lambda表达式这一系列教程,旨在介绍lambda的概念,同时逐步教授如何在实践中使用它们。回顾表达式、语句表达式表达式由变量、运算符和方法调用组成,其计算结果为单个值。您已经看到了表达式的示例,如下面的代码所示:intcadence=0;anArray[0]=100;System.out.println("......
  • 从头学Java17-Modules模块
    模块Modules了解module系统如何塑造JDK,如何使用,使项目更易于维护。烧哥注从头讲JDK17的文章比较少,英文为主,老外虽能讲清原理,但写的比较绕,所以决定翻译一下,也有个别细节完善。原文关注点主要在java生态,以及类库的维护者如何过渡到module,对新用户也同样适用。module简介......
  • JAVA调RFC接口
    packagecom.swift.oa;/***@Author:Wriprin*@Date:2022/11/2517:04*@Version1.0*/publicclassSapConn{//SAPserverprivateStringJCO_ASHOST;//SAPsystemnumberprivateStringJCO_SYSNR;//SAPclientprivateSt......