Redis常见数据结构以及使用场景分别是什么？

哈希表typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码,用于计算索引值
// 总是等于size-1
unsigned long sizemark;
// 该哈希表已有节点的数量
unsigned long used;
} dichht;
哈希算法

当字典被用作数据库的底层实现,或者哈希键的底层实现时,Redis使用MurmurHash算法。这种算法的优点在于即使输入的键是规律的,算法仍能给出一个个很好的随机分布性,并且算法的计算速度非常快。

哈希冲突的解决方式

Redis的哈希表使用链地址法来解决键冲突,每个哈希表节点都有一个next指针,多个哈希表节点可以用这个单向链表连接起来,这就解决了键冲突的问题。

特性字典被广泛用于实现Redis的各种功能,其中包括数据库和哈希键。Redis中的字典使用哈希表作为底层结构实现,每个字典带有两个哈希表,一个平时使用,另一个仅在进行rehash时使用。Redis使用MurmurHash2算法来计算键的哈希值。哈希表使用链地址法来解决键冲突。跳跃表

先看这样一张图:

如上图,我们要查找一个元素,就需要从头节点开始遍历,直到找到对应的节点或者是第一个大于要查找的元素的节点(没找到)。时间复杂度为O(N)。

这个查找效率是比较低的,但如果我们把列表的某些节点拔高一层,如下图,例如把每两个节点中有一个节点变成两层。那么第二层的节点只有第一层的一半,查找效率也就会提高。

查找的步骤是从头节点的顶层开始,查到第一个大于指定元素的节点时,退回上一节点,在下一层继续查找。

比如我们要查找16:

从头节点的最顶层开始,先到节点7。7的下一个节点是39,大于16,因此我们退回到7从7开始,在下一层继续查找,就可以找到16。

这个例子中遍历的节点不比一维列表少,但是当节点更多,查找的数字更大时,这种做法的优势就体现出来了。还是上面的例子,如果我们要查找的是39,那么只需要访问两个节点(7、39)就可以找到了。这比一维列表要减少一半的数量。

为了避免插入操作的时间复杂度是O(N),skiplist每层的数量不会严格按照2:1的比例,而是对每个要插入的元素随机一个层数。

随机层数的计算过程如下:

每个节点都有第一层那么它有第二层的概率是p,有第三层的概率是p*p不能超过最大层数zskiplistNodetypedef struct zskiplistNode {
// 后退指针
struct zskiplistNode *backward;
// 分值权重
double score;
// 成员对象
robj *obj;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} leval[];
} zskiplistNode;

一般来说,层的数量越多,访问其他节点的速度越快。

zskipListtypedef struct zskiplist {
// 表头节点和表尾节点
struct zskiplistNode *header, *tail;
// 表中节点的数量
unsigned long length;
// 表中层数最大的节点的层数
int leval;
} zskiplist;
特性跳跃表是有序集合的底层实现之一Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成,其中zskiplist用于保存跳跃表信息(比如表头节点、表尾节点、长度),而zskiplistNode则用于表示跳跃表节点每个跳跃表节点的层高都是1至32之间的随机数在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的成员对象必须是唯一的。跳跃表中的节点按照分值大小进行排序,当分值相同时,节点按照成员对象的大小进行排序。跳表是一种实现起来很简单,单层多指针的链表,它查找效率很高,堪比优化过的二叉平衡树,且比平衡树的实现。压缩列表“

压缩列表(ziplist)是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做列表键的底层实现。