Redis面试（三）：底层数据结构（二）

2.6.5 跳表

1. 介绍

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。

跳跃表在 Redis 的唯一作用， 就是实现 有序集合zset 数据类型。

跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。 在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。

Redis使用跳跃表作为有序集合(zset)键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。

跳跃表就是在链表的基础上，增加多级索引提升查找效率。

跳跃表由 zskiplistNode 和 zskiplist 两个结构定义，其中 zskiplistNode 表示跳跃表节点，用于 zskiplist 结构保存跳跃表节点的相关信息。

跳表的底层数据结构如下：

最左侧是zskiplist结构，结构包含以下属性：

 typedef struct zskiplist {
     struct zskiplistNode *header, *tail; // 表头节点、表尾节点
     unsigned long length;// 表中节点数量
     int level;// 表中层数最大的节点的层数
 } zskiplis

• header和tail指针分别指向跳跃表的表头和表尾节点，通过这两个指针，程序定位表头节点和表尾节点的复杂度为O(1)。
• 通过使用length属性来记录节点的数量，程序可以在O(1)复杂度内返回跳跃表的长度。
• level属性则用于在O(1)复杂度内获取跳跃表中层高最大的那个节点的层数量，注意表头节点的层高并不计算在内。
  • 层：保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针，为了提高查找的效率，程序总是从高层先开始访问，然后随着元素值范围的缩小，慢慢降低层次。

图中四个 zskiplistNode 结构，包含如下属性：

 typedef struct zskiplistNode {
     robj *obj;
     double score;
     struct zskiplistNode *backward;
     struct zskiplistLevel {
         struct zskiplistNode *forward;//每一层中的前向指针
         unsigned int span;//x.level[i].span 
     } level[];
 } zskiplistNode;

• obj：各节点中的o1,o2,o3是节点所保存的成员对象 节点的成员对象是一个指针，指向一个字符串对象，而字符串对象则保存着一个SDS值。
• score：各节点的1.0,2.0,3.0是节点所保存的分值，在跳跃表中，节点按各自所保存的分值从小到大排列。 节点的分值是一个double类型浮点数，跳跃表中所有节点都按分值从小到大排序。
• backward：后退指针，指向位于当前节点的前个节点。 节点的后退指针(backward属性)用于从表尾向表头方向访问节点 跟可以一次跳过多个节点的前进指针不同，因为每个节点只有一个后退指针，所以每次只能后退至前一个节点。
• level[]：图中用 L1,L2,L3等字样标记节点的各个层，L1代表第一层，L2代表第二层... 每个层带有两个属性： forward前进指针 和 span跨度，前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。
  • level[i].forward：每个层都有一个指向表尾方向的前进指针(level[i].forward属性)，用于从表头向表尾方向访问节点
  • level[i].span：表示节点x在第i层到其下一个节点需跳过的节点数。 注：两个相邻节点span为1; 指向NULL的所有前进指针的跨度都为0，因为它们没有连向任何节点

2. (优点)为何不使用红黑树等平衡树？

1. 高效的查找操作：跳表通过建立多层索引，可以在有序集合中实现快速的查找操作。相比于传统的平衡树结构（如红黑树），跳表的查找操作具有更低的时间复杂度，平均情况下为O(log n)。
2. 简单且易于实现：相对于其他复杂的数据结构（如红黑树或AVL树），跳表的实现相对简单且容易理解。它没有复杂的平衡调整操作，只需通过维护索引层来保持有序性和高效性。
3. 空间效率较高：跳表通过层级结构来建立索引，每个节点只需额外存储少量的指针信息。相比于一些平衡树结构，跳表在空间使用上通常更加高效。

2.6.6 哈希表

1. 介绍

HashMap 的应用非常广泛，最主要的原因就是能够以O(1)的复杂度快速查询。那么是如何实现的呢？

一个最简单的 HashMap 就是一个数组，数组里的每个元素是一个哈希桶（也叫做Bucket），第一个数组元素被编为哈希桶 0，以此类推。当一个键值对的键经过 Hash 函数计算后，再对数组元素个数取模，就能得到该键值对对应的数组元素位置，也就是第几个哈希桶。

字典的底层结构：

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

如下图，key1 经过哈希计算和哈希值取模后，就对应哈希桶 1，类似的，key3 和key16 分别对应哈希桶 7 和桶 4。

2. 哈希冲突

从图上我们还可以看到，需要写入 Hash 表的键空间一共有 16 个键，而 Hash 表的空间大小只有 8 个元素，这样就会导致有些键会对应到相同的哈希桶中。这种情况就是哈希冲突。

为了解决哈希冲突，Redis采用 链式哈希 的方法不同的键对应到相同的哈希桶中。

解决 hash 冲突（哈希冲突）有以下四种方法：

1. 链地址法（Chaining） 使用链表来存储哈希冲突的元素。每个哈希桶维护一个链表，发生冲突时将新元素添加到链表中。（HashMap 使用此法）
2. 再哈希法（Rehashing） 当发生冲突时，使用另一个哈希函数重新计算哈希值，以尝试找到一个不冲突的位置。
3. 建立公共溢出区（Overflow Area） 将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。这个溢出区可以是一个单独的数据结构，如链表或树。
4. 开放定址法（Open Addressing） 在哈希表中尝试找到另一个空槽来存储冲突的元素，而不是使用额外的数据结构，只要哈希表足够大，空的哈希地址总能找到。常见的开放地址法包括线性探测、二次探测和双重散列等。
   1. 线性探测法： Hi = (Hash(Key)+di) \% m ,(1<=i<m)
      • Hash(Key)：哈希函数
      • m：哈希表长度
      • di：为递增序列 1,2,3,4...m-1 且di=i
      • \%：取模
   2. 二次探测法： Hi= (Hash(Key)+di) \% m,(i=1,2...k, k<=m/2)
      • Hash(Key)：哈希函数
      • m：哈希表长度，m要求是某个4k+3的质数
      • di为递增序列 12,-12,22,-22,...k2,-k2

当有相同的键需要插入时，在哈希桶中，就会行成一个链表，链表的节点上记录的就是每个键的值。当查询一个键时，如果对用的哈希桶中存储的是一个链表，就会再次根据键值找到对用的哈希项，这样就避免了哈希冲突。

采用链式哈希解决哈希冲突有一个问题，根据链表的结构，查询非链表头或链表尾的数据复杂度比较高，如果链表太长，会导致查询变慢，因此同一个哈希桶内的链表长度，需要控制。

如果哈希桶内的链表太长怎么处理呢？Redis采用rehash的方式解决，直白一点就是进行扩容。

3. redis为什么选链地址法

1. 简单且易于实现：链地址法是一种简单直观的冲突解决方法，不需要进行大量的计算和移动元素。这使得实现和维护哈希表变得相对简单。
2. 灵活性：链地址法可以存储任意数量的冲突元素，而不受固定槽位数量的限制。这使得哈希表可以根据需要动态地调整大小，而不需要重新哈希整个表。
3. 低装载因子：Redis的哈希表实现中，采用了较低的装载因子（load factor），即在哈希表中保持较多的空槽，以减少冲突的可能性。这可以降低链表的长度，提高查找效率。
4. 内存效率：链地址法相对于其他冲突解决方法，可以更好地利用内存空间。当冲突发生时，只需分配额外的链表节点，而不是需要连续的存储空间。

4. rehash

当哈希表保存的键值对太多或者太少时，就要通过 rerehash(重新散列）来对哈希表进行相应的扩展或者收缩。具体步骤如下：

1. 如果执行扩展操作，会基于原哈希表创建一个大小等于 ht[0].used * 2n 的哈希表（也就是每次扩展都是根据原哈希表已使用的空间扩大一倍创建另一个哈希表）。相反如果执行的是收缩操作，每次收缩是根据已使用空间缩小一倍创建一个新的哈希表。
2. 重新利用上面的哈希算法，计算索引值，然后将键值对放到新的哈希表位置上。
3. 所有键值对都迁徙完毕后，释放原哈希表的内存空间。

扩容的条件：

负载因子 = 哈希表已保存节点数量 / 哈希表大小；

• 当负载因子 >= 1，并且 redis 没有执行 RDB 快照或者 AOF 重写的时候，就会进行 rehash 操作；
• 当负载因子 >= 5，说明哈希冲突已经非常严重了，不管有没有在执行 RDB 快照或者 AOF 重写都会强制进行 rehash 操作；

渐进式rehash：

扩容和收缩操作不是一次性、集中式完成的，而是分多次、渐进式完成的。

如果保存在 Redis 中的键值对只有几个几十个，那么 rehash 操作可以瞬间完成，但是如果键值对有几百万，几千万甚至几亿，那么要一次性的进行 rehash，势必会造成 Redis 一段时间内不能进行别的操作。所以 Redis 采用渐进式 rehash。

在数据迁移的时候不是一次性将大量数据拷贝进入新的 hash 表，而是在 rehash 期间，每次哈希表元素进行新增、删除、查找或者更新操作操作时，redis 除了会执行对应的操作之外，还会顺序将旧的 hash 表中的索引位置上所有的 key - value 迁移到新的哈希表上；会在最终的某个时间完成哈希表的 rehash 操作；

这样在进行渐进式 rehash 期间，字典的删除查找更新等操作可能会在两个哈希表上进行，第一个哈希表没有找到，就会去第二个哈希表上进行查找。但是进行增加操作，一定是在新的哈希表上进行的。

我正在参与2023腾讯技术创作特训营第二期有奖征文，瓜分万元奖池和键盘手表