深入阐述Redis Hash实现原理（哈希表）

1。什么是

Redis Hash（哈希表）是一种字段值对（键值对）的集合，类似于Python中的字典和Java中HashMap中的字典。字段对应一个值。您可以使用数组以 O(1) 的时间复杂度查找相关数组。您还可以使用字段来更新或删除键值对。

Redis 哈希表由数组 + 链表组成。每个数组元素占用的槽称为哈希桶。当存在哈希冲突时，就会发生。这个桶下面挂着链表，用“拉链法”解决哈希冲突问题。

简单来说，就是使用哈希计算将键均匀映射到哈希表。 图2-18

图2-18

2.动动脑筋

Hash Hash数据类型实际上有两种基本的存储数据结构。

1. 听写结构。
2. 7.0版本之前使用ziplist，然后用listpack替换。

通常采用dict数据结构来存储数据，每个字段值对代表一个dictEntry节点进行存储。

只有同时满足以下两个条件时，才会使用listpack数据结构（7.0版本之前使用ziplist）来替代dict存储，键值对按字段优先、值排序最后，紧密相连的方法是将每个键值对放在列表的末尾。

• 每个键值对中字段和值的位大小小于hash-max-listpack-value配置的值（默认64）。
• 字段值对 键值对的数量小于hash-max-listpack-entries配置的值（默认512）。

每次将数据写入哈希表时，中的函数hashTypeConvertListpack()。 t_hash.c判断底层结构是否需要转换。

当插入和修改的数据不满足上述两个条件时，哈希表的基本存储结构转换为结构dict。需要注意的是，不能从字典退化为列表。

虽然无法使用listpack来操作O(1)时间复杂度的数据，但是使用listpack可以大大减少内存占用，而且数据量比较小，所以性能上并没有太大的差别。

为了隐藏顶层的哈希表，并在底层使用不同的数据结构存储方式，抽象了一个hashTypeIterator来实现哈希表的查询。

数据类型Hash使用listpack存储数据时的情况，如图2-19所示。 图2-19

图2-19

listpack数据结构之前已经介绍过。接下来，我将向您展示听写的样子。

Redis 数据库是一个全局哈希表。通常，我只会使用哈希表ht_table[0]。图2-20是一个没有中断的字典。 图2-20

图2-20

dict字典在源代码中由dict结构dict.h表示。

struct dict {
    dictType *type;
  // 真正存储数据的地方，分别存放两个指针
    dictEntry **ht_table[2];
    unsigned long ht_used[2];

    long rehashidx;

    int16_t pauserehash;
    signed char ht_size_exp[2];
};

• dictType *type，一个存储函数的结构体，定义了一些函数指针。通过设置自定义函数，字典键和值可用于存储任何类型的数据。
• 重点关注dictEntry **ht_table[2]，它存储了两个辅助dictEntry指针，指针指向dictEntry指针数组。
• ht_used[2]，记录每个哈希表使用了多少个槽（例如字段长度为32，则使用12个）。
• rehasidx，用于指示是否进行rehashing操作，-1表示不进行rehashing操作。如果正在执行 rehash，则其值是正在执行当前 rehash 操作的哈希表 ht_table[0] dictEntry 数组的索引。
• pauserehash 表示 rehash 状态。当大于0时，表示暂停重试。如果小于0，则表示发生了错误。

继续观看dictEntry。数组中的每个元素都是dictEntry类型，它存储键值对，代表一个字典节点。指针

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

• *key指向键值对中的一个键，它实际上指向一个SDS实例。
• v 是表示键值对中的值的联接。一次只有一个字段具有值。使用union的目的是为了节省内存。
  • *val 如果值是非数字类型，则使用该指针存储。
  • uint64_t u64，当值为无符号整数时使用此字段进行存储。
  • int64_t s64 如果该值为有符号整数，则使用此字段来存储它。
  • double d，该值为使用该字段存储的浮点数。
• *next指向下一个节点指针。当哈希表数据增加时，不同key得到的哈希值可以相同，也就是说多个key对应一个哈希段。这就是哈希值。希腊冲突。 Redis 使用 zips 方法，该方法使用链表将数据链接在一起。

MySQL：“为什么 ht_table[2] 存储两个指向哈希表的指针？一个哈希表还不够吗？”

默认情况下，ht_table 用于读取[0] 写入数据时，当哈希表中的数据越来越多，哈希冲突严重时，哈希段的链表会比较长，这会导致查询性能下降。

我找到了一种快速且牢不可破的方法。当哈希表存储的键值对过多或过少时，就需要通过重新散列（rehashing）来扩大或缩小哈希表。

扩展和缩减

1. 为了高性能和减少哈希冲突，我将创建一个哈希表ht_table[1]，其大小等于[used 2] ，即，每次扩容时，都会在哈希表ht_table [0]的基础上创建一个新的哈希表表ht_table [1]，使已用空间增加一倍。相反，如果是收缩操作，则根据 ht_table [0] 使用空间的两倍来创建新的哈希表。
2. 重新计算键值对的哈希值，获取键值对所在段在新哈希表ht_table [1]中的位置，并将键值对迁移到新的哈希表。
3. 所有键值对迁移完成后，修改指针并释放空间。具体来说，指针ht_table[0]指向扩展后的哈希表，恢复小哈希表原来的内存空间。指针ht_table[1]指向NULL。为下一次扩张或收缩做好准备。 ？这意味着当前没有 RDB 线程和 AOF 重写线程在运行。这两个操作比较容易影响性能，不扩容就会火上浇油。
4. 执行命令BGSAVE或BGREWRITEAOF且冲突严重时负载因子大于等于5。（如果太大或等于5。不会运行，查询效率会太慢）。

负载因子=哈希表存储空间dicInput节点数/哈希表桶数。理想情况下，每个哈希段中存储一个 dictEntry 节点，负载因子 = 1。

MySQL：“需要迁移大量数据。重新处理操作不会长时间阻塞主线程吗？时间？”

为了避免主线程阻塞带来的性能问题，我没有一次性迁移所有key，而是将迁移操作拆分到每个请求中多次，以避免集中rehash造成的长期阻塞。这种方法称为渐进式rehash。

在进行渐进式rehash时，dict会使用两个哈希表ht_table[0]和ht_table[1]，具体步骤为rehashing 如下：

1. 将 rehashidx 设置为 0，表示刷新开始执行。
2. 在刷新期间，每当服务器处理客户端执行添加、搜索、删除操作时，或者对听写哈希表进行更新操作，除了执行指定的操作外，还会检查当前的dict是否处于re-state，如果是，则会对该segment的所有键值对进行哈希Rehash列表ht_table[0]中索引位置为rehashidx的链表到哈希表到哈希表。这个hash当扇区数据迁移完成后，rehashidx加1，表示接下来要迁移的扇区的位置。
3. 当所有键值对迁移完毕后，将rehashidx设置为-1，表示重新处理操作已完成。 ？如果一个哈希表没有找到，则到另一个哈希表中查找。但是，追加操作只会在新的哈希表上执行。

   MySQL：“如果请求少的话，用两个哈希表用不了多久。”

   好问题，Redis Server 在初始化时，会注册并定期执行一个时间事件。

   serverCron函数除了重新哈希之外还主要处理以下任务。

   • 过期的密钥将被删除。
   • 监控服务启动状态。
   • 更新统计数据。
   • 渐进式重新哈希。
   • 运行 BGSAVE / AOF 覆盖并停止子进程。
   • 处理客户时间限制。
   • ……

   是不是很贴心，既能保证性能，又能防止浪费内存。好了，今天的基本哈希表数据结构的实现原理就到此为止。