20、redis底层实现跳表

一、简单介绍

1、我们为什么要使用跳表？

当我们使用对一个链表进行查找的时候，我们需要的时间复杂度是O(n)。我们没有办法对一个有序的链表进行二分查找。

当我们使用跳表实现，我们查找效率会很高，是O(logn)。

2、跳表的时间复杂度分析

每两个结点会抽出一个结点作为上一级索引的结点，那第一级索引的结点个数大约就是 n/2，第二级索引的结点个数大约就是 n/4，第三级索引的结点个数大约就是 n/8，依次类推，也就是说，第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2，那第 k级索引结点的个数就是 n/(2 )。
假设索引有 h 级，最高级的索引有 2 个结点。通过上面的公式，我们可以得到 n/(2 )=2，从而求得 h=log n-1。如果包含原始链表这一层，整个跳表的高度就是 log n。我们在跳表中查询某个数据的时候，如果每一层都要遍历 m 个结点，那在跳表中查询一个数据的时间复杂度就是O(m*logn)。并且m 的最大值是3.所以在跳表中查询任意数据的时间复杂度就是 O(logn)。

3、跳表的空间复杂度分析

这几级索引的结点总和就是 n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空间复杂度是 O(n)。也就是说，如果将包含 n 个结点的单链表构造成跳表，我们需要额外再用接近 n 个结点的存储空间。

二、跳表的代码实现

package com.ipp.test;
import java.util.Random;
public class SkiptList {
private class SkipListEntry {
// data
public String key;
public Integer value;
// links
public SkipListEntry up;
public SkipListEntry down;
public SkipListEntry left;
public SkipListEntry right;
// special
public static final String negInf = "-oo";
public static final String posInf = "+oo";
// constructor
public SkipListEntry(String key, Integer value) {
this.key = key;
this.value = value;
}
}
public SkipListEntry head;
// First element of the top level
public SkipListEntry tail;
// Last element of the top level
public int n;
// number of entries in the Skip List
public int h;
// Height
public Random r;
// Coin toss
public SkiptList() {
// 创建一个 -oo 和一个 +oo 对象
SkipListEntry p1 = new SkipListEntry(SkipListEntry.negInf, null);
SkipListEntry p2 = new SkipListEntry(SkipListEntry.posInf, null);
//p1 和 p2 相互连接
p1.right = p2;
p2.left = p1;
// 给 head 和 tail 初始化
head = p1;
tail = p2;
//初始化其他的对象
n = 0;
h = 0;
r = new Random();
}
/**
* 查找小于等于它的元素下标
*
* @param key
* @return
*/
private SkipListEntry findEntry(String key) {
SkipListEntry node = head;
while (true) {
// 从左向右查找，直到右节点的key值大于要查找的key值
while (node.right.key != SkipListEntry.posInf && node.right.key.compareTo(key) <= 0) {
//如果右边有元素，并且是右边的元素小于等于要找的key
node = node.right;
}
//如果下面还有元素，我们继续往下找知道到最底层的元素
if (node.down != null) {
node = node.down;
} else// if(node.right.key!=SkipListEntry.posInf&&node.right.key.compareTo(key)>0)
{
break;
}
}
// 返回p，！注意这里p的key值是小于等于传入key的值的（p.key <= key）
return node;
}
/**
* 根据key 去寻找value 值
*/
public Integer get(String key) {
SkipListEntry node = findEntry(key);
if (key.equals(node.key)) {
return node.value;
} else {
return null;
}
}
public Integer put(String key, Integer value) {
SkipListEntry p, q;
int i = 0;
// 查找适合插入的位子
p = findEntry(key);
// 如果跳跃表中存在含有key值的节点，则进行value的修改操作即可完成
if (p.key.equals(key)) {
Integer oldValue = p.value;
p.value = value;
return oldValue;
}
// 如果跳跃表中不存在含有key值的节点，则进行新增操作
q = new SkipListEntry(key, value);
//链表的插入操作
q.left = p;
p.right.left = q;
q.right = p.right;
p.right = q;
// 再使用随机数决定是否要向更高level攀升
while (r.nextDouble() < 0.5) {
// 如果新元素的级别已经达到跳跃表的最大高度，则新建空白层
if (i >= h) {
addEmptyLevel();
}
// 从p向左扫描含有高层节点的节点
while (p.up == null) {
p = p.left;
}
p = p.up;
// 新增和q指针指向的节点含有相同key值的节点对象
// 这里需要注意的是除底层节点之外的节点对象是不需要value值的
SkipListEntry z = new SkipListEntry(key, null);
//双链表的添加操作
z.left = p;
p.right.left = z;
z.right = p.right;
p.right = z;
//上下进行关联
z.down = q;
q.up = z;
i = i + 1;
q = z;
}
n = n + 1;
// 返回null，没有旧节点的value值
return null;
}
/**
* 添加层
*/
private void addEmptyLevel() {
SkipListEntry p1, p2;
p1 = new SkipListEntry(SkipListEntry.negInf, null);
p2 = new SkipListEntry(SkipListEntry.posInf, null);
p1.right = p2;
p2.left = p1;
//对p1 进行操作
p1.down = head;
head.up = p1;
//对p2 进行操作
p2.down = tail;
tail.up = p2;
//进行重新赋值
head = p1;
tail = p2;
h = h + 1;
}
/**
* 链表的移除包含键值得某个元素
*
* @param key
* @return
*/
public Integer remove(String key) {
SkipListEntry p, q;
p = findEntry(key);
if (!p.key.equals(key)) {
return null;
}
Integer oldValue = p.value;
//表示的是查到了 从下往上查找
while (p != null) {
q = p.up;
//双链表的删除
p.left.right = p.right;
p.right.left = p.left;
p = q;
}
return oldValue;
}
}

三、总结

1、为什么redis 底层用跳表实现而不是使用红黑树？

插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的按照区间来查找数据这个操作，红黑树的效率没有跳表高。还有就是跳表更容易实现，安全性比较高。

2、跳跃表在Java中的应用

ConcurrentSkipListMap：在功能上对应HashTable、HashMap、TreeMap；

ConcurrentSkipListSet ： 在功能上对应HashSet；

确切的说，SkipList更像Java中的TreeMap，TreeMap基于红黑树（一种自平衡二叉查找树）实现的，时间复杂度平均能达到O(log n)。 
HashMap是基于散列表实现的，查找时间复杂度平均能达 
到O(1)。ConcurrentSkipListMap是基于跳跃表实现的，查找时间复杂度平均能达到O(log n)。

ConcurrentSkipListMap具有SkipList的性质 ，并且适用于大规模数据的并发访问。多个线程可以安全地并发执行插入、移除、更新和访问操作。与其他有锁机制的数据结构在巨大的压力下相比有优势。

TreeMap插入数据时平衡树采用严格的旋转操作（比如平衡二叉树有左旋右旋）来保证平衡，因此SkipList比较容易实现，而且相比平衡树有着较高的运行效率。
 

最后

以上就是优秀美女为你收集整理的20、redis底层实现跳表的全部内容，希望文章能够帮你解决20、redis底层实现跳表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。