江苏龙网

  1. 主页 > 生活百科 > >

深入理解跳表及其在Redis中的应用( 三 )

Redis

七. 跳表完整代码跳表完整代码如下所示 。
public class Skiplist {public LinkedList<SkiplistNode> headNodes;public LinkedList<SkiplistNode> tailNodes;public int curLevel;public Random random;public Skiplist() {random = new Random();//headNodes用于存储每一层的头节点headNodes = new LinkedList<>();//tailNodes用于存储每一层的尾节点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) {//从顶层开始寻找，curNode表示当前遍历到的节点SkiplistNode curNode = headNodes.getFirst();while (curNode != null) {if (curNode.next.data =https://www.isolves.com/it/sjk/Redis/2023-03-02/= target) {//找到了目标值对应的节点，此时返回truereturn true;} else if (curNode.next.data > target) {//curNode的后一节点值大于target//说明目标节点在curNode和curNode.next之间//此时需要向下层寻找curNode = curNode.down;} else {//curNode的后一节点值小于target//说明目标节点在curNode的后一节点的后面//此时在本层继续向后寻找curNode = curNode.next;}}return false;}public void add(int num) {//获取本次添加的值的层数int level = getRandomLevel();//如果本次添加的值的层数大于当前跳表的层数//则需要在添加当前值前先将跳表层数扩充if (level > curLevel) {expanLevel(level - curLevel);}//curNode表示num值在当前层对应的节点SkiplistNode curNode = new SkiplistNode(num, level);//preNode表示curNode在当前层的前一个节点SkiplistNode preNode = headNodes.get(curLevel - level);for (int i = 0; i <= level; i++) {//从当前层的head节点开始向后遍历，直到找到一个preNode//使得preNode.data < num <= preNode.next.datawhile (preNode.next.data < num) {preNode = preNode.next;}//将curNode插入到preNode和preNode.next中间curNode.next = preNode.next;preNode.next = curNode;//如果当前并不是0层，则继续向下层添加节点if (curNode.level > 0) {SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1);//curNode指向下一层的节点curNode.down = downNode;//curNode向下移动一层curNode = downNode;}//preNode向下移动一层preNode = preNode.down;}}public boolean erase(int num) {//删除节点的遍历过程与寻找节点的遍历过程是相同的//不过在删除节点时如果找到目标节点，则需要执行节点删除的操作SkiplistNode curNode = headNodes.getFirst();while (curNode != null) {if (curNode.next.data == num) {//preDeleteNode表示待删除节点的前一节点SkiplistNode preDeleteNode = curNode;while (true) {//删除当前层的待删除节点，就是让待删除节点的前一节点指向待删除节点的后一节点preDeleteNode.next = curNode.next.next;//当前层删除完后，需要继续删除下一层的待删除节点//这里让preDeleteNode向下移动一层//向下移动一层后，preDeleteNode就不一定是待删除节点的前一节点了preDeleteNode = preDeleteNode.down;//如果preDeleteNode为null，说明已经将底层的待删除节点删除了//此时就结束删除流程，并返回trueif (preDeleteNode == null) {return true;}//preDeleteNode向下移动一层后，需要继续从当前位置向后遍历//直到找到一个preDeleteNode，使得preDeleteNode.next的值等于目标值//此时preDeleteNode就又变成了待删除节点的前一节点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;}}八. 跳表在Redis中的应用ZSet结构同时包含一个字典和一个跳跃表，跳跃表按score从小到大保存所有集合元素 。字典保存着从member到score的映射 。这两种结构通过指针共享相同元素的member和score，不会浪费额外内存 。
typedef struct zset {dict *dict;zskiplist *zsl;} zset;ZSet中的字典和跳表布局：


推荐阅读


上一篇：没有了

下一篇：数据结构与算法：冒泡排序