(三分钟系列)详解Redis中字典的内部原理和使用方法

前言

在 Redis 中，字典是一种运用特别广泛的数据结构，基本上各个功能模块都有使用到。

主要用途是两个方面
- 作为数据库键空间
- 作为 Hash 类型键的底层实现之一

1. 字典使用示例

1.1 实现数据库键空间

清除数据库里面的所有键值对

redis> FLUSHDB
OK

获得数据库里面所有键值对的数量

redis> DBSIZE
(integer) 0

设置键值对空间

redis> set space dong
OK

redis> get space 
"dong"

以上的这三种就是字典在 Redis 数据库里面作为键空间的示例，操作数据库的命令，实际上就是在字典上操作的。

1.2 Hash 类型键的底层实现

在 Hash 键底层是有两种数据结构来实现的，一种是压缩列表，一种是字典
默认是由压缩列表来实现，等到符合条件后才会实现转换。

条件：

哈希表中的某个键或者某个值的长度大于 64 的时候
哈希表中的节点（entry）数量大于 512 的时候

使用示例：

redis> HSET spacedong redis "redis"
(integer) 1

redis> HSET spacedong mysql "mysql"
(integer) 1

redis>HSET spacedong memcached "memcached"
(integer) 1

redis> HGETALL spacedong
 1)  "mysql"
 2)  "mysql"
 3)  "redis"
 4)  "redis"
 5)  "memcached"
 6)  "memcached"

2. 字典的底层结构和源码解析

2.1 字典的结构

/*
 * 字典
 *
 * 每个字典使用两个哈希表，用于实现渐进式 rehash
 */
typedef struct dict {

    // 特定于类型的处理函数
    dictType *type;

    // 类型处理函数的私有数据
    void *privdata;

    // 哈希表（2 个）
    dictht ht[2];

    // 记录 rehash 进度的标志，值为 -1 表示 rehash 未进行
    int rehashidx;

    // 当前正在运作的安全迭代器数量
    int iterators;

} dict;

这里的哈希表有两个指针，分别指向的是两个hash表。ht[0] 指向的是 0 号 hash 表，0 号 hash 表是正在使用的那张表，1 号 hash 表是当 0 号 hash 表正在 rehash 的时候才会使用的到，稍后会详细讲解 rehash 的过程。

2.2 Hash表的结构

/*
 * 哈希表
 */
typedef struct dictht {

    // 哈希表节点指针数组（俗称桶，bucket）
    dictEntry **table;

    // 指针数组的大小
    unsigned long size;

    // 指针数组的长度掩码，用于计算索引值
    unsigned long sizemask;

    // 哈希表现有的节点数量
    unsigned long used;

} dictht;

(三分钟系列)详解Redis中字典的内部原理和使用方法

Hash 表中的 table 是一个数组来的，是由一个个dictEntry组成，在图中所示的就是一个长度为 4 的空 table 。

2.3 DictEntry的结构

typedef struct dictEntry {

    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;

key中保存的是键，在v中保存的可能是指针，或者是 unit64_t 的整数，或者是 int64_t 的整数。next 指针指向的是下一个 hash 表节点，形成链表的结构，如下图。

(三分钟系列)详解Redis中字典的内部原理和使用方法

2.3 解决键冲突

当 hash 表出现键冲突的时候，Redis中的处理是直接把插入进来的这个键的 next 指针指向当前的键，通俗的理解就是直接插入到这个节点的头部，形成链表。

3. Rehash 过程

先是 Hash 表进行判断是否需要扩展或者是收缩
其次是在 ht[1] 中进行扩展或者收缩，每次的扩展或者收缩为原来的hash表的量的一倍或者一半，比如原本的hash表节点是8，扩展完成的话就是16，收缩完成的话就是4.
接着就是 Rehash 的过程

3.1 满足以下 ReHash 的前提条件任意一个，就会进行扩展 Hash 表

服务器目前没有在执行 BGSAVE 或者是 BGREWRITEAOF 命令的时候，当前的负载因子大于等于 1
服务器目前在执行 BGSAVE 或者是 BGREWRITAOF 的命令时候，当前的负载因子大于等于 5

补充：

当服务器在进行执行 BGSAVE 或者是 BGREWRITEAOF 的命令时，这个时候服务器在创建子进程完成备份，操作系统一般都是使用写时复制的(copr-on-write) 来优化子进程的效率，所以在子进程执行期间就会扩大负载因子，这样就可以尽可能地避免存在子进程期间进行扩展表，减少不必要的内存消耗。

负载因子(load_factor) = 已存在的节点数量 \ 能容纳的节点数量

如果是收缩的话，只需要负载因子小于 0.1 即可

3.2 Rehash 过程

先进行 Hash 表扩展
接着就是 Hash 表中的表 0 向表 1 迁移的过程

(三分钟系列)详解Redis中字典的内部原理和使用方法

ReHash 过程结束后

4.实际运用场景分析

存储对象的信息

根据以上字典的特性，我们知道，字典和 HashMap 的特性是差不多的，也是基于数组和链表的组合，所以一般都是用来存储键值对的。不过在实际运用场景中，我们会经常用来存储一个对象的信息。例如：一个对象的属性如 name ，age ，weight 等属性，可以直接当做一个个键值对存储在这个字典下，这样做的好处是，在需要用到这个对象的属性时，不用把这个对象全部序列化，只需要取出特定的就可以，而在传统的需要全部序列化，相比来讲就比较消耗资源。

参考书籍：Redis设计与实现

(三分钟系列)详解Redis中字典的内部原理和使用方法

前言

目录

1. 字典使用示例

1.1 实现数据库键空间

1.2 Hash 类型键的底层实现

使用示例：

2. 字典的底层结构和源码解析

2.1 字典的结构

2.2 Hash表的结构

2.3 DictEntry的结构

2.3 解决键冲突

3. Rehash 过程

3.1 满足以下 ReHash 的前提条件任意一个，就会进行扩展 Hash 表

3.2 Rehash 过程

4.实际运用场景分析

相关推荐