1. 什么是跳跃表？
增加了向前指针的链表叫作跳表。跳表全称叫做跳跃表。跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。（摘自百度百科）
2. Redis中跳跃表的数据结构
//zskiplistNode：跳跃表的一个节点
typedef struct zskiplistNode {
// 层：每个节点都包含很多层，每一层指向的都是同一个对象
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度：指当前这一层两个节点的距离，如上图o1和o3节点的L3层，中间跨过了o2节点，所以跨度就为2
unsigned int span;
} level[];
// 后退指针
struct zskiplistNode *backward;
// 分值：用于排序，跳跃表中的所有节点都按分值大小进行排序
double score;
// 成员对象：即真正要往链表中存放的对象
robj *obj;
} zskiplistNode;
//zskiplist：跳跃表链表
typedef struct zskiplist {
// 表头节点和表尾节点
structz skiplistNode *header, *tail;
// 表中节点的数量
unsigned long length;
// 表中层数最大的节点的层数
int level;
} zskiplist;
3. 总结
跳跃表是有序集合的底层实现之一（zset）。
-
Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度），而zskiplistNode则用于表示跳跃表节点。
-
每个跳跃表节点的层高都是1至32之间的随机数。
-
在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。
-
跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。
4. 附：跳跃表的Java实现
SkipList.java
import java.util.Random;
/**
* @author DengWeiPing
* @version 1.0
* @date 2021/5/16 10:00
*/
public class SkipList<T> {
private SkipListNode<T> head, tail;
private int nodes;//节点总数
private int listLevel;//层数
private Random random;// 用于投掷硬币
private static final double PROBABILITY = 0.5;//向上提升一个的概率
public SkipList() {
// TODO Auto-generated constructor stub
random = new Random();
clear();
}
/**
* 清空跳跃表
*/
public void clear() {
head = new SkipListNode<T>(SkipListNode.HEAD_KEY, null);
tail = new SkipListNode<T>(SkipListNode.TAIL_KEY, null);
horizontalLink(head, tail);
listLevel = 0;
nodes = 0;
}
public boolean isEmpty() {
return nodes == 0;
}
public int size() {
return nodes;
}
/**
* 在最下面一层，找到要插入的位置前面的那个key
*/
private SkipListNode<T> findNode(int key) {
SkipListNode<T> p = head;
while (true) {
while (p.right.key != SkipListNode.TAIL_KEY && p.right.key <= key) {
p = p.right;
}
if (p.down != null) {
p = p.down;
} else {
break;
}
}
return p;
}
/**
* 查找是否存在key，存在则返回该节点，否则返回null
*/
public SkipListNode<T> search(int key) {
SkipListNode<T> p = findNode(key);
if (key == p.getKey()) {
return p;
} else {
return null;
}
}
/**
* 向跳跃表中添加key-value
*/
public void put(int k, T v) {
SkipListNode<T> p = findNode(k);
//如果key值相同，替换原来的vaule即可结束
if (k == p.getKey()) {
p.value = v;
return;
}
SkipListNode<T> q = new SkipListNode<>(k, v);
backLink(p, q);
int currentLevel = 0;//当前所在的层级是0
//抛硬币，如果小于0.5，则往上一层也插入q
while (random.nextDouble() < PROBABILITY) {
//如果此次仍是正面，且当前要插入的层数超出了高度，需要重新建一个顶层
if (currentLevel >= listLevel) {
listLevel++;
SkipListNode<T> p1 = new SkipListNode<>(SkipListNode.HEAD_KEY, null);
SkipListNode<T> p2 = new SkipListNode<>(SkipListNode.TAIL_KEY, null);
horizontalLink(p1, p2);
vertiacallLink(p1, head);
vertiacallLink(p2, tail);
head = p1;
tail = p2;
}
//找到p的上一层，如果p没有上层，则找它左边节点的上一层
while (p.up == null) {
p = p.left;
}
p = p.up;//此时的p是上一层的节点
SkipListNode<T> e = new SkipListNode<T>(k, null);//只保存key就ok
backLink(p, e);//将e插入到上一层的p的右边
vertiacallLink(e, q);//将e和q上下连接
q = e;//此时就在上一层也插入了q，并且和其左边节点及下面节点相连接
currentLevel++;
}
nodes++;//节点数+1
}
//node1后面插入node2
private void backLink(SkipListNode<T> node1, SkipListNode<T> node2) {
node2.left = node1;
node2.right = node1.right;
node1.right.left = node2;
node1.right = node2;
}
/**
* 水平双向连接
*/
private void horizontalLink(SkipListNode<T> node1, SkipListNode<T> node2) {
node1.right = node2;
node2.left = node1;
}
/**
* 垂直双向连接
*/
private void vertiacallLink(SkipListNode<T> node1, SkipListNode<T> node2) {
node1.down = node2;
node2.up = node1;
}
/**
* 打印出原始数据
*/
@Override
public String toString() {
// TODO Auto-generated method stub
if (isEmpty()) {
return "跳跃表为空！";
}
StringBuilder builder = new StringBuilder();
SkipListNode<T> p = head;
while (p.down != null) {
p = p.down;
}
while (p.left != null) {
p = p.left;
}
if (p.right != null) {
p = p.right;
}
while (p.right != null) {
builder.append(p);
builder.append("\n");
p = p.right;
}
return builder.toString();
}
}
SkipListNode.java
/**
* @author DengWeiPing
* @version 1.0
* @date 2021/5/16 9:59
*/
public class SkipListNode<T> {
public int key;
public T value;
public SkipListNode<T> up, down, left, right; // 上下左右 四个指针
public static final int HEAD_KEY = Integer.MIN_VALUE; // 负无穷
public static final int TAIL_KEY = Integer.MAX_VALUE; // 正无穷
public SkipListNode(int k, T v) {
// TODO Auto-generated constructor stub
key = k;
value = v;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null) {
return false;
}
if (!(o instanceof SkipListNode<?>)) {
return false;
}
SkipListNode<T> ent;
try {
ent = (SkipListNode<T>) o; // 检测类型
} catch (ClassCastException ex) {
return false;
}
return (ent.getKey() == key) && (ent.getValue() == value);
}
@Override
public String toString() {
// TODO Auto-generated method stub
return "key-value:" + key + "-" + value;
}
}
test.java
public static void main(String[] args) {
// TODO Auto-generated method stub
SkipList<String> list = new SkipList<String>();
System.out.println(list);
list.put(2, "ping");
list.put(1, "deng");
list.put(3, "wei");
list.put(1, "d");//测试同一个key值
list.put(4, "邓");
list.put(6, "卫");
list.put(5, "平");
System.out.println(list);
System.out.println(list.size());
}
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/70000428/viewspace-2783188/ ，如需转载，请注明出处，否则将追究法律责任。
请登录后发表评论
登录
全部评论
