改造之后的数据结构叫做跳表,支持类似”二分“的查找算法。
怎么提高链表查找效率?
正常链表的查询,因为要从头开始遍历,所以时间复杂度是O(n)。
截屏2020-03-09下午2.44.51.png试想一下给链表建立一个索引,我们先按照每2个节点提取1个节点,那么就可
以建立这样的节点索引
如果我们要查找某个节点,比如8,我们可以现在第一层索引遍历,找到8所在的区间节点,8比节点7大,比9节点小,那么从7的down指针找到原链表这一层,继续往后遍历就找到8所在的节点位置了。这样,原来如果查找8需要遍历8个节点,现在只需要遍历5个节点。
我们还可以在第一层的索引基础上,继续按每两个节点抽取一个节点来建立索引。
截屏2020-03-09下午2.55.24.png跳表查询有多快?
按每两个节点抽一个节点来算,第一级索引的节点个数为:n_2,第二级的节点个数为:n/4,以此类推,第k级的节点个数为:n_(2^k)。
假设索引有h级,最高级的索引有2个节点,则可以得到这样一个公式:
n/(2^h) = 2
=>
h = log(2)n - 1
如果包含原始链这一层,那么h的高度就是log(2)n。
如果每一层都要遍历m个节点,那么跳表中查询一个数据的时间复杂度为O(m*logn)。
那么m的值是多少呢?
按照前面每2个取1一个节点的规则,那么m的值应为3。当遍历到某个层级的某个节点x时,除了要和x比较,还要和x的下一级节点y比较,如果在x和y之间,那么到x的down指向的下一级,根据之前的规则,x和y分别对应的下一级节点之间只有一个节点,所以每一层最多只需要遍历3个。
所以,在跳表中,查询一个数据的时间复杂度为O(logn),和二分查找的时间复杂度是一样的。
跳表消耗多少内存?
我觉得所有时间复杂度低的算法,在空间复杂度上一定是有抵消的。跳表也是如此,它查询快的原因,是建立在增加了很多层索引的基础上。每层索引的节点数减半,知道减少到2个节点为止,就是一个等比数列。
原始链表大小为n,每2个节点抽1个节点,每层索引的节点数为:
n/2, n/4, n/8, ..., 8, 4, 2
节点总和就是
n/2+n/4+n/8…+8+4+2 = n-2
也就是说,我们需要额外增加n个节点的空间。
关于跳表的插入和删除
关于插入操作和链表是一样的,都是O(1)的时间复杂度,区别在于定位的查找上,跳表在查找上是O(logn)的时间复杂度,而链表是O(n)。
关于删除,跳表不光要删除原链表中的,还需要删除索引中的。
跳表索引动态更新
如果我们不停的往跳表中插入数据,不更新索引,就又可能出现某2个节点间数据非常多的情况下,极端情况下,还会退化成单链表。
所以需要某种手段来维护索引与原始链表大小间的平衡,如果链表中节点多了,索引节点就相应增加。
和红黑树、AVL树这样的平衡二叉树,通过左右旋的方式保持左右子树的大小平衡不同,跳表是通过随机函数来维护前面提到的”平衡性“。
当我们往跳表中插入数据的时候,通过一个随机函数,来决定将这个节点插入到哪几级索引中,比如随机函数生成了值K,就将这个节点添加到第1级到第k级的索引中。
截屏2020-03-09下午4.13.06.png这里的随机函数选择,以后再研究。。。
Redis为什么要用跳表来实现有序集合,而不是红黑树
Redis中的有序集合支持的核心操作主要有下面这几个:
- 插入一个数据
- 删除一个数据
- 查找一个数据
- 按照区间查找数据
- 迭代输出有序序列
其中插入、删除、查找以及迭代输出有序序列红黑树也可以完成,效率是一样的,但是按照区间查找这个操作,跳表可以做到O(logn)的时间复杂度定位区间的起点,然后在原始链表中顺序往后遍历就可以了,非常高效。
而且,跳表更容易代码实现,相比红黑树来说更易懂,跳表更加灵活,可以通过改变索引构建策略,有效平衡执行效率和内存消耗。
网友评论