| 深入理解跳表及其在Redis中的应用 | 您所在的位置：网站首页 › 电脑上如何恢复出厂设置win7 › 深入理解跳表及其在Redis中的应用 |
深入理解跳表及其在Redis中的应用
|
前言
跳表可以达到和红黑树一样的时间复杂度 O(logN)，且实现简单，Redis 中的有序集合对象的底层数据结构就使用了跳表。其作者威廉·普评价：跳跃链表是在很多应用中有可能替代平衡树的一种数据结构。本篇文章将对跳表的实现及在Redis中的应用进行学习。** 一. 跳表的基础概念跳表，即跳跃链表（Skip List），是基于并联的链表数据结构，操作效率可以达到O(logN)，对并发友好，跳表的示意图如下所示。 跳表的特点，可以概括如下。 •跳表是多层（level）链表结构； •跳表中的每一层都是一个有序链表，并且按照元素升序（默认）排列； •跳表中的元素会在哪一层出现是随机决定的，但是只要元素出现在了第 k 层，那么 k 层以下的链表也会出现这个元素； •跳表的底层的链表包含所有元素； •跳表头节点和尾节点不存储元素，且头节点和尾节点的层数就是跳表的最大层数； •跳表中的节点包含两个指针，一个指针指向同层链表的后一节点，一个指针指向下层链表的同元素节点。 以上图中的跳表为例，如果要查找元素 71，那么查找流程如下图所示。 从顶层链表的头节点开始查找，查找到元素71的节点时，一共遍历了4个节点，但是如果按照传统链表的方式（即从跳表的底层链表的头节点开始向后查找），那么就需要遍历7个节点，所以跳表以空间换时间，缩短了操作跳表所需要花费的时间。跳跃列表的算法有同平衡树一样的渐进的预期时间边界，并且更简单、更快速和使用更少的空间。这种数据结构是由William Pugh(音译为威廉·普)发明的，最早出现于他在1990年发表的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。 谷歌上找到一篇作者关于跳表的论文，感兴趣强烈建议下载阅读： epaperpress.com/sortsearch/… 跳表在动态查找过程中使用了一种非严格的平衡机制来让插入和删除都更加便利和快捷，这种非严格平衡是基于概率的，而不是平衡树的严格平衡。说到非严格平衡，首先想到的是红黑树RbTree，它同样采用非严格平衡来避免像AVL那样调整树的结构，这里就不展开讲红黑树了，看来跳表也是类似的路子，但是是基于概率实现的。 二. 跳表的节点已知跳表中的节点，需要有指向当前层链表后一节点的指针，和指向下层链表的同元素节点的指针，所以跳表中的节点，定义如下。 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 headNodes; public LinkedList 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) { expanLevel(level - curLevel); } //curNode表示num值在当前层对应的节点 SkiplistNode curNode = new SkiplistNode(num, level); //preNode表示curNode在当前层的前一个节点 SkiplistNode preNode = headNodes.get(curLevel - level); for (int i = 0; i target) { //curNode的后一节点值大于target //说明目标节点在curNode和curNode.next之间 //此时需要向下层寻找 curNode = curNode.down; } else { //curNode的后一节点值小于target //说明目标节点在curNode的后一节点的后面 //此时在本层继续向后寻找 curNode = curNode.next; } } return false; } 复制代码 六. 跳表的删除方法当在跳表中需要删除某一个元素时，则需要将这个元素在所有层的节点都删除，具体的删除规则如下所示。 •首先按照跳表的搜索的方式，搜索待删除节点，如果能够搜索到，此时搜索到的待删除节点位于该节点层数的最高层； •从待删除节点的最高层往下，将每一层的待删除节点都删除掉，删除方式就是让待删除节点的前一节点直接指向待删除节点的后一节点。 •下图是一个删除过程的示意图。 •跳表的删除的代码如下所示。 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，说明已经将底层的待删除节点删除了 //此时就结束删除流程，并返回true if (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; } 复制代码 七. 跳表完整代码跳表完整代码如下所示。 public class Skiplist { public LinkedList headNodes; public LinkedList 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 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 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中的字典和跳表布局： 随机层数的实现原理： 跳表是一个概率型的数据结构，元素的插入层数是随机指定的。Willam Pugh在论文中描述了它的计算过程如下：指定节点最大层数 MaxLevel，指定概率 p， 默认层数 lvl 为1； 生成一个0~1的随机数r，若r M) { seed -= M; } return seed; } 复制代码 可以看到leveldb使用随机数与kBranching取模，如果值为0就增加一层，这样虽然没有使用浮点数，但是也实现了概率平衡。 2.跳表结点的平均层数我们很容易看出，产生越高的节点层数出现概率越低，无论如何层数总是满足幂次定律越大的数出现的概率越小。 如果某件事的发生频率和它的某个属性成幂关系，那么这个频率就可以称之为符合幂次定律。 幂次定律的表现是少数几个事件的发生频率占了整个发生频率的大部分， 而其余的大多数事件只占整个发生频率的一个小部分。 幂次定律应用到跳表的随机层数来说就是大部分的节点层数都是黄色部分，只有少数是绿色部分，并且概率很低。 定量的分析如下： •节点层数至少为1，大于1的节点层数满足一个概率分布。 •节点层数恰好等于1的概率为p^0(1-p) •节点层数恰好等于2的概率为p^1(1-p) •节点层数恰好等于3的概率为p^2(1-p) •节点层数恰好等于4的概率为p^3(1-p) 依次递推节点层数恰好等于K的概率为p^(k-1)(1-p) 因此如果我们要求节点的平均层数，那么也就转换成了求概率分布的期望问题了： 表中P为概率，V为对应取值，给出了所有取值和概率的可能，因此就可以求这个概率分布的期望了。方括号里面的式子其实就是高一年级学的等比数列，常用技巧错位相减求和，从中可以看到结点层数的期望值与1-p成反比。对于Redis而言，当p=0.25时结点层数的期望是1.33。 总结跳表的时间复杂度与AVL树和红黑树相同，可以达到O(logN)，但是AVL树要维持高度的平衡，红黑树要维持高度的近似平衡，这都会导致插入或者删除节点时的一些时间开销，所以跳表相较于AVL树和红黑树来说，省去了维持高度的平衡的时间开销，但是相应的也付出了更多的空间来存储多个层的节点，所以跳表是用空间换时间的数据结构。以Redis中底层的数据结构zset作为典型应用来展开，进一步看到跳跃链表的实际应用。 |
【本文地址】