哈希表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就会使用压缩列表来做列表键的底层实现。

特性

看他的名字就能看出来,是为了节省内存造的列表结构。

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

String

String数据结构是简单的key-value类型,value其实不仅可以是String,也可以是数字。常规key-value缓存应用;常规计数:微博数,粉丝数等。

Hash

Hash 是一个 string 类型的 ?eld 和 value 的映射表,hash 特别适合用于存储对象,后续操作的时候,你可以直接仅 仅修改这个对象中的某个字段的值。比如我们可以Hash数据结构来存储用户信息,商品信息等。

List

list 就是链表,Redis list 的应用场景非常多,也是Redis最重要的数据结构之一,比如微博的关注列表,粉丝列表, 消息列表等功能都可以用Redis的 list 结构来实现。

Redis list 的实现为一个双向链表,即可以支持反向查找和遍历,更方便操作,不过带来了部分额外的内存开销。

另外可以通过 lrange 命令,就是从某个元素开始读取多少个元素,可以基于 list 实现分页查询,这个很棒的一个功 能,基于 Redis 实现简单的高性能分页,可以做类似微博那种下拉不断分页的东西(一页一页的往下走),性能高。

Set

set 对外提供的功能与list类似是一个列表的功能,特殊之处在于 set 是可以自动排重的。

当你需要存储一个列表数据,又不希望出现重复数据时,set是一个很好的选择,并且set提供了判断某个成员是否在 一个set集合内的重要接口,这个也是list所不能提供的。可以基于 set 轻易实现交集、并集、差集的操作。

比如:在微博应用中,可以将一个用户所有的关注人存在一个集合中,将其所有粉丝存在一个集合。Redis可以非常 方便的实现如共同关注、共同粉丝、共同喜好等功能。这个过程也就是求交集的过程,具体命令如下:sinterstore key1 key2 key3将交集存在key1内。

Sorted Set

和set相比,sorted set增加了一个权重参数score,使得集合中的元素能够按score进行有序排列。

举例:在直播系统中,实时排行信息包含直播间在线用户列表,各种礼物排行榜,弹幕消息(可以理解为按消息维 度的消息排行榜)等信息,适合使用 Redis 中的 SortedSet 结构进行存储。