您当前的位置:首页 > 电脑百科 > 程序开发 > 语言 > JAVA

跳表在Java中的实现

时间:2022-07-08 11:06:37  来源:  作者:java程序猿

跳表是一种数据结构,用于借助连接到元素子序列的链表层次结构来存储元素的排序列表。跳表允许以有效的方式处理项目查找。跳表是一种概率数据结构,这意味着它跳过整个列表中的几个元素,因此称为跳表。我们可以将跳表作为链表的扩展版本。与链表允许插入、删除和搜索元素的方式类似,跳表也允许搜索元素、从列表中删除元素和插入元素。它将包含一个基本列表,其中包含一组元素,这些元素将维护后续元素的链接层次结构。

语法:

跳表没有特定的语法,但它有一个算法。在研究算法之前,我们需要检查基本跳表操作的类型。

  1. 插入操作:在跳表中,用于在特定情况下向特定位置添加新节点
  2. 搜索操作:在跳表中,用于搜索特定节点
  3. 删除操作:在跳表中,用于删除特定情况下的节点

让我们看看跳表是如何以算法的方式工作的。

插入算法:

步骤1:确定节点级别,因为列表中的每个元素都有节点表示,并且在插入列表时随机选择节点的级别

步骤2:根据以下步骤确定节点的级别

步骤3:找到最大级别是跳表中级别计数的上限,该上限由 L(N)=logp/2N 确定。这确保了随机级别将大于最大级别

步骤4:插入从最高级别开始,并比较当前节点的下一个节点

步骤5:如果“下一个节点关键点”小于“插入的关键点”,则可以使用相同级别继续前进

步骤6:如果next node key大于inserted key,那么我们需要存储一个指向当前节点I的指针,并向下移动一级继续搜索。

搜索算法:

步骤1:因为搜索元素非常类似于搜索一个点以在跳表中插入元素。

步骤2:如果下一个节点键小于搜索键,那么我们可以在同一级别上前进

步骤3:如果next node key大于inserted key,那么我们需要存储一个指向当前节点I的指针,并向下移动一级继续搜索。

步骤4:在最低级别,如果最右侧元素的下一个元素具有与搜索键相等的键,那么我们已经找到了键,否则这是一个失败。

删除算法:

步骤1:要删除任何元素,比如k,首先我们需要使用搜索算法在跳表中定位该元素。

第2步:一旦我们使用搜索算法找到了元素,指针重新排列将从列表中删除该元素,就像我们在单个链接列表中所做的那样。

步骤3:我们需要从跳过列表的最低级别开始,重新排列I not元素k旁边的元素。

步骤4:删除元素后,可能会出现没有元素的级别的情况,因此我们需要通过减少跳表级别来删除这些级别。

示例:JAVA中的跳表

import java.util.Iterator;
import java.util.Random;
import java.util.NoSuchElementException;
public class SkipListJava<K extends Comparable<K>, V> implements Iterable<K> {
private int listsize;
private double pb;
protected static final Random randomGen = new Random();
protected static final double DEFAULT_PB = 0.5;
private NodeKeyValue<K, V> head;
public SkipListJava() {
this(DEFAULT_PB);
}
public SkipListJava(double pb) {
this.head = new NodeKeyValue<K, V>(null, null, 0);
this.pb = pb;
this.listsize = 0;
}
public V get(K key) {
checkKeyValid(key);
NodeKeyValue<K, V> listnode = findNode(key);
if (listnode.getKey().compareTo(key) == 0)
return listnode.getValue();
else
return null;
}
public void add(K key, V value) {
checkKeyValid(key);
NodeKeyValue<K, V> listnode = findNode(key);
if (listnode.getKey() != null && listnode.getKey().compareTo(key) == 0) {
listnode.setValue(value);
return;
}
NodeKeyValue<K, V> newlistNode = new NodeKeyValue<K, V>(key, value, listnode.getLevel());
horizontalInsertList(listnode, newlistNode);
int curLevel = listnode.getLevel();
int headlistLevel = head.getLevel();
while (isBuildLevel()) {
if (curLevel >= headlistLevel) {
NodeKeyValue<K, V> newHeadEle = new NodeKeyValue<K, V>(null, null, headlistLevel + 1);
verticalLink(newHeadEle, head);
head = newHeadEle;
headlistLevel = head.getLevel();
}
while (listnode.getUp() == null) {
listnode = listnode.getPrevious();
}
listnode = listnode.getUp();
NodeKeyValue<K, V> tmp = new NodeKeyValue<K, V>(key, value, listnode.getLevel());
horizontalInsertList(listnode, tmp);
verticalLink(tmp, newlistNode);
newlistNode = tmp;
curLevel++;
}
listsize++;
}
public void remove(K key) {
checkKeyValid(key);
NodeKeyValue<K, V> listnode = findNode(key);
if (listnode == null || listnode.getKey().compareTo(key) != 0)
throw new NoSuchElementException("Key does not exist!");
while (listnode.getDownList() != null)
listnode = listnode.getDownList();
NodeKeyValue<K, V> previous = null;
NodeKeyValue<K, V> next = null;
for (; listnode != null; listnode = listnode.getUp()) {
previous = listnode.getPrevious();
next = listnode.getNext();
if (previous != null)
previous.setNext(next);
if (next != null)
next.setPreviousVal(previous);
}
while (head.getNext() == null && head.getDownList() != null) {
head = head.getDownList();
head.setUp(null);
}
listsize--;
}
public boolean contains(K key) {
return get(key) != null;
}
public int listsize() {
return listsize;
}
public boolean empty() {
return listsize == 0;
}
protected NodeKeyValue<K, V> findNode(K key) {
NodeKeyValue<K, V> listnode = head;
NodeKeyValue<K, V> next = null;
NodeKeyValue<K, V> down = null;
K nodeKey = null;
while (true) {
next = listnode.getNext();
while (next != null && lessThanEqual(next.getKey(), key)) {
listnode = next;
next = listnode.getNext();
}
nodeKey = listnode.getKey();
if (nodeKey != null && nodeKey.compareTo(key) == 0)
break;
down = listnode.getDownList();
if (down != null) {
listnode = down;
} else {
break;
}
}
return listnode;
}
protected void checkKeyValid(K key) {
if (key == null)
throw new IllegalArgumentException("Key must be not null!");
}
protected boolean lessThanEqual(K a, K b) {
return a.compareTo(b) <= 0;
}
protected boolean isBuildLevel() {
return randomGen.nextDouble() < pb;
}
protected void horizontalInsertList(NodeKeyValue<K, V> a, NodeKeyValue<K, V> b) {
b.setPreviousVal(a);
b.setNext(a.getNext());
if (a.getNext() != null)
a.getNext().setPreviousVal(b);
a.setNext(b);
}
protected void verticalLink(NodeKeyValue<K, V> a, NodeKeyValue<K, V> b) {
a.setDown(b);
b.setUp(a);
}
@Override
public String toString() {
StringBuilder stringbuild = new StringBuilder();
NodeKeyValue<K, V> listnode = head;
while (listnode.getDownList() != null)
listnode = listnode.getDownList();
while (listnode.getPrevious() != null)
listnode = listnode.getPrevious();
if (listnode.getNext() != null)
listnode = listnode.getNext();
while (listnode != null) {
stringbuild.Append(listnode.toString()).append("n");
listnode = listnode.getNext();
}
return stringbuild.toString();
}
@Override
public Iterator<K> iterator() {
return new SkipListIterator<K, V>(head);
}
protected static class SkipListIterator<K extends Comparable<K>, V> implements Iterator<K> {
private NodeKeyValue<K, V> listnode;
public SkipListIterator(NodeKeyValue<K, V> listnode) {
while (listnode.getDownList() != null)
listnode = listnode.getDownList();
while (listnode.getPrevious() != null)
listnode = listnode.getPrevious();
if (listnode.getNext() != null)
listnode = listnode.getNext();
this.listnode = listnode;
}
@Override
public boolean hasNext() {
return this.listnode != null;
}
@Override
public K next() {
K result = listnode.getKey();
listnode = listnode.getNext();
return result;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
protected static class NodeKeyValue<K extends Comparable<K>, V> {
private K key;
private V value;
private int skiplevel;
private NodeKeyValue<K, V> up, down, next, previous;
public NodeKeyValue(K key, V value, int skiplevel) {
this.key = key;
this.value = value;
this.skiplevel = skiplevel;
}
@Override
public String toString() {
StringBuilder stringbuild = new StringBuilder();
stringbuild.append("Node[")
.append("key:");
if (this.key == null)
stringbuild.append("None");
else
stringbuild.append(this.key.toString());
stringbuild.append(", value:");
if (this.value == null)
stringbuild.append("None");
else
stringbuild.append(this.value.toString());
stringbuild.append("]");
return stringbuild.toString();
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public int getLevel() {
return skiplevel;
}
public void setLevel(int skiplevel) {
this.skiplevel = skiplevel;
}
public NodeKeyValue<K, V> getUp() {
return up;
}
public void setUp(NodeKeyValue<K, V> up) {
this.up = up;
}
public NodeKeyValue<K, V> getDownList() {
return down;
}
public void setDown(NodeKeyValue<K, V> down) {
this.down = down;
}
public NodeKeyValue<K, V> getNext() {
return next;
}
public void setNext(NodeKeyValue<K, V> next) {
this.next = next;
}
public NodeKeyValue<K, V> getPrevious() {
return previous;
}
public void setPreviousVal(NodeKeyValue<K, V> previous) {
this.previous = previous;
}
}
public static void main(String[] args) {
SkipListJava<Integer, String> skip = new SkipListJava<>();
for (int i = 20; i < 35; i++) {
skip.add(i, String.valueOf(i));
}
System.out.println(skip);
assert skip.listsize() == 10;
int count = 0;
for (Integer i : skip)
assert i.equals(count++);
skip.remove(23);
System.out.println(skip);
skip.remove(25);
skip.remove(33);
skip.remove(30);
System.out.println(skip);
skip.remove(28);
skip.add(25, "25");
System.out.println(skip);
assert skip.listsize() == 0;
assert skip.empty();
}
}

输出:

跳表在Java中的实现

 

我们编写了此代码,用于添加到跳表、在跳表中搜索以及从跳表中删除。

小结

跳表的概念在任何编程语言中都是相同的,它是数据结构中的主要算法之一



Tags:跳表   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
前言在头条创作了一个月左右的时间,收获了50+粉丝,很是开心,我会把数据结构与算法的文章更新到底,第一次看我文章的同仁如果觉得不错的话就关注一下我哦,你的支持就是我创作的动...【详细内容】
2022-10-10  Tags: 跳表  点击:(12)  评论:(0)  加入收藏
跳表是一种数据结构,用于借助连接到元素子序列的链表层次结构来存储元素的排序列表。跳表允许以有效的方式处理项目查找。跳表是一种概率数据结构,这意味着它跳过整个列表中的...【详细内容】
2022-07-08  Tags: 跳表  点击:(90)  评论:(0)  加入收藏
在我们的印象中,mysql数据表里无非就是存储一行行的数据。跟个excel似的。直接遍历这一行行数据,性能就是O(n),比较慢。为了加速查询,使用了B+树来做索引,将查询性能优化到了O(lg...【详细内容】
2022-05-09  Tags: 跳表  点击:(220)  评论:(0)  加入收藏
承接上文Redis底层字符串编码设计思想简介ziplist数据结构 内存会一次性开辟一块大的连续的空间,来存放ziplist。 &bull; zlbytes32bit内存空间,表示ziplist占用的字节总数 &b...【详细内容】
2022-05-09  Tags: 跳表  点击:(87)  评论:(0)  加入收藏
在我们的印象中,mysql数据表里无非就是存储一行行的数据。跟个excel似的。直接遍历这一行行数据,性能就是O(n),比较慢。为了加速查询,使用了B+树来做索引,将查询性能优化到了O(lg...【详细内容】
2022-04-18  Tags: 跳表  点击:(560)  评论:(0)  加入收藏
聊聊Mysql索引和redis跳表 ---redis的有序集合zset数据结构底层采用了跳表原理 时间复杂度O(logn)(阿里)redis使用跳表不用B+数的原因是:redis是内存数据库,而B+树纯粹是为了m...【详细内容】
2021-02-05  Tags: 跳表  点击:(287)  评论:(0)  加入收藏
▌简易百科推荐
本文将介绍接下来的技巧和主题: 在包装器上使用基元字段(例如,布尔值 ->布尔值) 减少形成平面结构的类的数量(在一个或多个类中折叠类) 尽可能使用窄数据类型(例如,代替,代替等)short...【详细内容】
2022-11-02  一个即将退役的码农  今日头条  Tags:Java   点击:(1)  评论:(0)  加入收藏
原因:最近在用Sqlite存储数据,因涉及数据安全,所以需要数据库加密,Sqlite库默认不带加密功能 目前已知的对 SQLite 加密的工具主要有「[SQLite Encryption Extension (SEE)]、[S...【详细内容】
2022-11-01  水中影子621  今日头条  Tags:Java   点击:(17)  评论:(0)  加入收藏
对于数据抓取技术,本文介绍了java相关抓取工具,并附上demo源码供感兴趣的朋友测试!1)JDK自带HTTP连接,获取页面或Json 2) JDK自带URL连接,获取页面或Json 3)HttpClient Get工具,获取...【详细内容】
2022-10-31  MYJ2C混淆  今日头条  Tags:   点击:(6)  评论:(0)  加入收藏
前言说到java内部类,想必大家首先会想到比较常用的“匿名内部类”,但实际上,这只是内部类的其中一种使用方式而已。内部类的使用方式实际上总共包括:成员内部类, 方法局部类,匿名...【详细内容】
2022-10-27  马士兵Java架构  今日头条  Tags:java   点击:(9)  评论:(0)  加入收藏
在项目开发中,后端服务对外提供API接口一般都会关注响应时长。但是某些情况下,由于业务规划逻辑的原因,我们的接口可能会是一个聚合信息处理类的处理逻辑,比如我们从多个不同的...【详细内容】
2022-10-26  架构悟道  今日头条  Tags:JAVA   点击:(16)  评论:(0)  加入收藏
与 PHP 或 JavaScript 不同,Java 是一种强类型编程语言。这实质上意味着每个变量都必须使用预定义的数据类型声明,之后不能更改。Java中有两种数据类型: 原始数据类型 - int、...【详细内容】
2022-10-26   qaseven    Tags:Java   点击:(6)  评论:(0)  加入收藏
1、原理:基于javaAgent和Java字节码注入技术的java探针工具技术原理 2、原理分析动态代理功能实现说明,我们利用javaAgent和ASM字节码技术开发java探针工具,实现原理如下:jdk1.5...【详细内容】
2022-10-24  马士兵Java架构  今日头条  Tags:Java探针   点击:(13)  评论:(0)  加入收藏
简介前面在密码学入门一文中讲解了各种常见的密码学概念、算法与运用场景,但没有介绍过代码,因此,为作补充,这一篇将会介绍使用Java语言如何实现使用这些算法,并介绍一下使用过程...【详细内容】
2022-10-22  扣钉日记  今日头条  Tags:Java   点击:(4)  评论:(0)  加入收藏
简单描述java虚拟机内存分配与GC触发场景堆内存中,新生代和老年代分区图解 堆空间的参数设置-XX: +PrintFlagsInitial :查看所有的参数的默认初始值-XX: +PrintFlagsFinal :...【详细内容】
2022-10-21  chost-jie    Tags:java虚拟机   点击:(6)  评论:(0)  加入收藏
概述最近项目上反馈某个重要的定时任务突然不执行了,很头疼,开发环境和测试环境都没有出现过这个问题。定时任务采用的是 ScheduledThreadPoolExecutor,后来一看代码发现踩了一...【详细内容】
2022-10-21  Java架构学习指南  今日头条  Tags:   点击:(8)  评论:(0)  加入收藏
站内最新
站内热门
站内头条