
一文搞懂跳表原理及实现
跳表可以达到和红黑树一样的时间复杂度O(logN),且实现简单,Redis中的有序集合对象的底层数据结构就使用了跳表。本篇文章将对跳表的实现进行学习。跳表的时间复杂度与AVL树和红黑树相同,可以达到O(logN),但是AVL树要维持高度的平衡,红黑树要维持高度的近似平衡,这都会导致插入或者删除节点时的一些时间开销,所以跳表相较于AVL树和红黑树来说,省去了维持高度的平衡的时间开销,但是相应的也付出
前言
跳表可以达到和红黑树一样的时间复杂度O(logN),且实现简单,Redis中的有序集合对象的底层数据结构就使用了跳表。本篇文章将对跳表的实现进行学习。
正文
一. 跳表的基础概念
跳表,即跳跃表(Skip List),是基于并联的链表数据结构,操作效率可以达到**O(logN)**,对并发友好。跳表的示意图如下所示。
跳表的特点,可以概括如下。
-
跳表是多层(level)链表结构;
-
跳表中的每一层都是一个有序链表,并且按照元素升序(默认)排列;
-
跳表中的元素会在哪一层出现是随机决定的,但是只要元素出现在了第k层,那么k层以下的链表也会出现这个元素;
-
跳表的底层的链表包含所有元素;
-
跳表头节点和尾节点不存储元素,且头节点和尾节点的层数就是跳表的最大层数;
-
跳表中的节点包含两个指针,一个指针指向同层链表的后一节点,一个指针指向下层链表的同元素节点。
以上图中的跳表为例,如果要查找元素71,那么查找流程如下图所示。
从顶层链表的头节点开始查找,查找到元素71的节点时,一共遍历了4个节点,但是如果按照传统链表的方式(即从跳表的底层链表的头节点开始向后查找),那么就需要遍历7个节点,所以跳表以空间换时间,缩短了操作跳表所需要花费的时间。
二. 跳表的节点
已知跳表中的节点,需要有指向当前层链表后一节点的指针,和指向下层链表的同元素节点的指针,所以跳表中的节点,定义如下。
public class SkiplistNode {
public int data;
public SkiplistNode next;
public SkiplistNode down;
public int level;
public SkiplistNode(int data, int level) {
this.data = data;
this.level = level;
}
}
上述是跳表中的节点的最简单的定义方式,存储的元素data为整数,节点之间进行比较时直接比较元素data的大小。
三. 跳表的初始化
跳表初始化时,将每一层链表的头尾节点创建出来并使用集合将头尾节点进行存储,头尾节点的层数随机指定,且头尾节点的层数就代表当前跳表的层数。初始化后,跳表结构如下所示。
跳表初始化的相关代码如下所示。
public LinkedList<SkiplistNode> headNodes;
public LinkedList<SkiplistNode> tailNodes;
public int curLevel;
public Random random;
public Skiplist() {
random = new Random();
headNodes = new LinkedList<>();
tailNodes = new LinkedList<>();
curLevel = getRandomLevel();
SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0);
SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0);
for (int i = 0; i <= curLevel; i++) {
head.next = tail;
headNodes.addFirst(head);
tailNodes.addFirst(tail);
SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);
SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);
headNew.down = head;
tailNew.down = tail;
head = headNew;
tail = tailNew;
}
}
四. 跳表的添加方法
每一个元素添加到跳表中时,首先需要随机指定这个元素在跳表中的层数,如果随机指定的层数大于了跳表的层数,则在将元素添加到跳表中之前,还需要扩大跳表的层数,而扩大跳表的层数就是将头尾节点的层数扩大。下面给出需要扩大跳表层数的一次添加的过程。
初始状态时,跳表的层数为2,如下图所示。
现在要往跳表中添加元素120,并且随机指定的层数为3,大于了当前跳表的层数2,此时需要先扩大跳表的层数,如下图所示。
将元素120插入到跳表中时,从顶层开始,逐层向下插入,如下图所示。
跳表的添加方法的代码如下所示。
public void add(int num) {
int level = getRandomLevel();
if (level > curLevel) {
expanLevel(level - curLevel);
}
SkiplistNode curNode = new SkiplistNode(num, level);
SkiplistNode preNode = headNodes.get(curLevel - level);
for (int i = 0; i <= level; i++) {
while (preNode.next.data < num) {
preNode = preNode.next;
}
curNode.next = preNode.next;
preNode.next = curNode;
if (curNode.level > 0) {
SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1);
curNode.down = downNode;
curNode = downNode;
}
preNode = preNode.down;
}
}
private void expanLevel(int expanCount) {
SkiplistNode head = headNodes.getFirst();
SkiplistNode tail = tailNodes.getFirst();
for (int i = 0; i < expanCount; i++) {
SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);
SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);
headNew.down = head;
tailNew.down = tail;
head = headNew;
tail = tailNew;
headNodes.addFirst(head);
tailNodes.addFirst(tail);
}
}
五. 跳表的搜索方法
在跳表中搜索一个元素时,需要从顶层开始,逐层向下搜索。搜索时遵循如下规则。
-
目标值大于当前节点的后一节点值时,继续在本层链表上向后搜索;
-
目标值大于当前节点值,小于当前节点的后一节点值时,向下移动一层,从下层链表的同节点位置向后搜索;
-
目标值等于当前节点值,搜索结束。
下图是一个搜索过程的示意图。
跳表的搜索的代码如下所示。
public boolean search(int target) {
SkiplistNode curNode = headNodes.getFirst();
while (curNode != null) {
if (curNode.next.data == target) {
return true;
} else if (curNode.next.data > target) {
curNode = curNode.down;
} else {
curNode = curNode.next;
}
}
return false;
}
六. 跳表的删除方法
当在跳表中需要删除某一个元素时,则需要将这个元素在所有层的节点都删除,具体的删除规则如下所示。
-
首先按照跳表的搜索的方式,搜索待删除节点,如果能够搜索到,此时搜索到的待删除节点位于该节点层数的最高层;
-
从待删除节点的最高层往下,将每一层的待删除节点都删除掉,删除方式就是让待删除节点的前一节点直接指向待删除节点的后一节点。
下图是一个删除过程的示意图。
跳表的删除的代码如下所示。
public boolean erase(int num) {
SkiplistNode curNode = headNodes.getFirst();
while (curNode != null) {
if (curNode.next.data == num) {
SkiplistNode preDeleteNode = curNode;
while (true) {
preDeleteNode.next = curNode.next.next;
preDeleteNode = preDeleteNode.down;
if (preDeleteNode == null) {
return true;
}
while (preDeleteNode.next.data != num) {
preDeleteNode = preDeleteNode.next;
}
}
} else if (curNode.next.data > num) {
curNode = curNode.down;
} else {
curNode = curNode.next;
}
}
return false;
}
七. 跳表完整代码
跳表完整代码如下所示。
public class Skiplist {
public LinkedList<SkiplistNode> headNodes;
public LinkedList<SkiplistNode> tailNodes;
public int curLevel;
public Random random;
public Skiplist() {
random = new Random();
headNodes = new LinkedList<>();
tailNodes = new LinkedList<>();
curLevel = getRandomLevel();
SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0);
SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0);
for (int i = 0; i <= curLevel; i++) {
head.next = tail;
headNodes.addFirst(head);
tailNodes.addFirst(tail);
SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);
SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);
headNew.down = head;
tailNew.down = tail;
head = headNew;
tail = tailNew;
}
}
public boolean search(int target) {
SkiplistNode curNode = headNodes.getFirst();
while (curNode != null) {
if (curNode.next.data == target) {
return true;
} else if (curNode.next.data > target) {
curNode = curNode.down;
} else {
curNode = curNode.next;
}
}
return false;
}
public void add(int num) {
int level = getRandomLevel();
if (level > curLevel) {
expanLevel(level - curLevel);
}
SkiplistNode curNode = new SkiplistNode(num, level);
SkiplistNode preNode = headNodes.get(curLevel - level);
for (int i = 0; i <= level; i++) {
while (preNode.next.data < num) {
preNode = preNode.next;
}
curNode.next = preNode.next;
preNode.next = curNode;
if (curNode.level > 0) {
SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1);
curNode.down = downNode;
curNode = downNode;
}
preNode = preNode.down;
}
}
public boolean erase(int num) {
SkiplistNode curNode = headNodes.getFirst();
while (curNode != null) {
if (curNode.next.data == num) {
SkiplistNode preDeleteNode = curNode;
while (true) {
preDeleteNode.next = curNode.next.next;
preDeleteNode = preDeleteNode.down;
if (preDeleteNode == null) {
return true;
}
while (preDeleteNode.next.data != num) {
preDeleteNode = preDeleteNode.next;
}
}
} else if (curNode.next.data > num) {
curNode = curNode.down;
} else {
curNode = curNode.next;
}
}
return false;
}
private void expanLevel(int expanCount) {
SkiplistNode head = headNodes.getFirst();
SkiplistNode tail = tailNodes.getFirst();
for (int i = 0; i < expanCount; i++) {
SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);
SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);
headNew.down = head;
tailNew.down = tail;
head = headNew;
tail = tailNew;
headNodes.addFirst(head);
tailNodes.addFirst(tail);
}
}
private int getRandomLevel() {
int level = 0;
while (random.nextInt(2) > 1) {
level++;
}
return level;
}
}
总结
跳表的时间复杂度与AVL树和红黑树相同,可以达到O(logN),但是AVL树要维持高度的平衡,红黑树要维持高度的近似平衡,这都会导致插入或者删除节点时的一些时间开销,所以跳表相较于AVL树和红黑树来说,省去了维持高度的平衡的时间开销,但是相应的也付出了更多的空间来存储多个层的节点,所以跳表是用空间换时间的数据结构。
原文地址:一文搞懂跳表原理及实现
更多推荐
所有评论(0)