[数据结构与算法]Redis源码阅读—数据结构之字典 dict.c/dict.h

一、 dict的定义

??字典，是一种用于实现键值对（key-value pair）保存的抽象数据结构，通过字典，可以在单个键（key）与单个值（value）之间进行关联（或者说是将键映射成值），而这些关联的键与值即为键值对。

??在字典中，每一个键都是独一无二的，所以程序可以在字典中通过键来对值，甚至是键值对进行操作。

??在一些高级编程语言中，字典经常作为一种内置的数据结构出现，但是可惜的是，C语言并不在此列，所以 Redis 自己实现了字典这种数据结构。

??在 Redis 中，字典使用哈希表作为底层实现，而一个哈希表可以有多个哈希结点，每一个哈希节点保存了一组键值对。下图是一个典型的字典：

??下面依次是哈希节点、哈希表、字典、迭代器的实现。

哈希节点（dictEntry ）

哈希节点，在 dict.h/dictEntry 中进行了定义：

// 哈希表节点
typedef struct dictEntry {
    
    // 键
    void *key;

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

    // 指向下一个哈希节点，构成单向链表，用以解决键冲突（链地址法）
    struct dictEntry *next;

} dictEntry;

• key 属性用来保存键值对中的键，联合体（union）v 属性用来保存键值对中的值。由于 v 属性使用 union 关键字进行定义，所以键值对中的值可以是一个指针，一个 uint64_t 类型的整数，或者是一个 int64_t 类型的整数。

• * next 属性是指向下一个哈希节点的指针，用来将多个哈希值相同的键值对连接起来，构成一个单向链表，用以解决键冲突（collision）即通过链地址法解决键冲突。

哈希表（dictht ）

哈希表，在 dict.h/dictht 中进行了定义：

//哈希表
typedef struct dictht {
    
    // 哈希字节数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩码，总是等于 size - 1
    unsigned long sizemask;

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

} dictht;

• table 属性是一个数组，数组中的每一个元素都是一个指向 dict.h/dictEntry 结构的指针。

• size 属性记录了哈希表的大小，也即是 table 数组的大小。

• used 属性记录了哈希表已有结点，即键值对的数量。

• sizemask 属性的值总是等于 size-1 ，是用来和哈希值一起决定一个键应该被放在 table 数组的哪一个索引上面的。

字典（dict）

字典，在 dict.h/dict 中进行了定义：

//字典
typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx;

    // 目前正在运行的迭代器的数量
    int iterators;
    
} dict;

• ht属性：每一个字典（dict）都有两个哈希表（dictht），用来实现 渐进式 rehash ，保存在 ht 数组当中。并且，在字典当中，一般只会使用 ht[0] 哈希表，只有在对 ht[0] 哈希表进行 rehash 时才会用到 ht[1]。

• rehashidx 属性用来记录 rehash 进度，当 rehash 没有在进行的时候，rehashidx = -1 。

• iterators 属性用来记录目前正在运行的迭代器的数量。

• type 属性和 privdata 属性是用来针对不同类型的键值对，创建多态字典的。

  • type 属性是一个指向 dictType 结构的指针，每个 dictType 结构保存了一组用于操纵特定类型键值对的函数，而 Redis 会为不同用途的字典设置不同的类型特定函数。
  • privdata 属性保存了要传给那些类型特定函数的可选参数。

其中，字典类型特定函数在 dict.h/dictType 中进行了定义：

// 字典类型特定函数
typedef struct dictType {

    // 计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);

    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);

    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);

    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);

    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
    
    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);

} dictType;


/* 外部变量 Hash table types */
extern dictType dictTypeHeapStringCopyKey;
extern dictType dictTypeHeapStrings;
extern dictType dictTypeHeapStringCopyKeyValue;

字典迭代器（dictIterator ）

字典迭代器，在 dict.h/dictIterator 中进行了定义：

// 字典迭代器
typedef struct dictIterator {
        
    // 被迭代的字典
    dict *d;

    // table ：正在被迭代的哈希表，值可以是 0 或 1。
    // index ：迭代器当前所指向的哈希表的索引位置
    // safe ：标识这个迭代器是否安全
    int table, index, safe;

    // entry ：当前迭代到的哈希节点
    // nextEntry ：当前迭代到的哈希节点的下一个哈希节点
    dictEntry *entry, *nextEntry;

    long long fingerprint; /* unsafe iterator fingerprint for misuse detection */
    
} dictIterator;

• d 属性是一个指向 dict 结构的指针，保存了当前迭代器正在处理的字典。

• table 属性用来标识当前正在被迭代的哈希表，即 dict 结构中的 dictht 数组 ht 的下标，值可以为 0 或 1 。

• index 属性用来标识迭代器当前所指向的哈希表的索引位置。

• safe 属性用来标识这个迭代器是否是安全的迭代器，这对该迭代器后续能调用的 API 有影响。其中，safe = 1 表示该迭代器可以在迭代时进行增删改等操作，对字典进行修改，即调用 dictDelete、dictFind 等函数，如若不然，则只能使用 dictNext 遍历函数，而不能对字典进行修改。

• entry 属性是一个指向 dictEntry 结构的指针，指向当前迭代到的哈希节点。

• nextEntry 属性是一个指向 dictEntry 结构的指针，指向当前迭代到的哈希节点的下一个哈希节点。这个属性存在的原因是，在安全迭代器运行时，entry 指针所指向的节点可能会被修改，所以需要一个指针来保存下一节点的位置，来防止指针丢失。

• fingerprint 属性是字典的指纹，用于误用检测，即在不安全的迭代器对字典进行操作后，与操作前的指纹值进行对比，若不同，则说明在迭代过程中有对字典进行增删操作，而这些操作在不安全的迭代器中是不被允许的。

宏定义常量

在 dict.h 中，对一些对常量的定义：

/*
 * 字典的操作状态
 */
// 操作成功
#define DICT_OK 0
// 操作失败（或出错）
#define DICT_ERR 1


/*
 * 哈希表的初始大小
 */
#define DICT_HT_INITIAL_SIZE     4

即：

• DICT_OK：字典操作状态，表示操作成功

• DICT_ERR：字典操作状态，表示操作失败或出错

• DICT_HT_INITIAL_SIZE：哈希表的初始大小，值为 4

二、 dict 的 API

dict 的函数实现分为两种，一种是通过宏定义的函数，一种是在 dict.c 内实现的函数。

1. 宏定义函数

2. dict.c 中实现的函数

在 dict.c 中定义了几个静态变量：

// 表示字典是否启用 rehash 
static int dict_can_resize = 1;

// 强制 rehash 的比率
static unsigned int dict_force_resize_ratio = 5;

// 哈希种子，用于 dictGenCaseHashFunction() 函数中
static uint32_t dict_hash_function_seed = 5381;

• dict_can_resize
  ??表示字典是否启用 rehash ，程序可以通过后续在API 实现提及的dictEnableResize() 和 dictDisableResize() 函数，来手动地允许或阻止哈希表进行 rehash。但是，即使该值为零，也不是所有的 rehash 都会被阻止，这种情况与下列的 dict_force_resize_ratio 变量有关。

• dict_force_resize_ratio
  ??字典强制 rehash 比率。当某个哈希表的已有哈希节点的数量和字典大小之间的比率大于字典强制 rehash 比率，即 size / used > dict_force_resize_ratio 时，即使 dict_can_resize = 0 也会强制执行 rehash。

• dict_hash_function_seed
  ??哈希种子，用于哈希函数之一的 dictGenCaseHashFunction() 函数中。

而在 dict.c 中实现的函数，有以下几种类型：

（1）私有函数

（2）哈希函数

具体实现与分析日后单开一篇进行学习与分析。

（3）其余 API 实现

三、 dict 的特性

1. 每个字典带有两个哈希表 ht[0] 与 ht[1]
   ??由于随着操作的进行，哈希表中保存的键值对数量会随之不断地变化，为了使哈希表的负载因子保持在一个合理的范围，会对哈希表进行相应的扩展或者收缩，所以需要进行 rehash 操作。
   ??所以每个字典都会带有两个哈希表 ht[0] 与 ht[1]，其中，ht[0] 用于在平时使用，而 ht[1] 用于在 rehash 进行时使用：将 ht[0] 上的所有结点 rehash 到 ht[1] 上。
   ??rehash，指的是对键的哈希值与索引值重新计算，然后将键值对放到 ht[1] 的指定位置。
   ??在 rehash 进行时，新添加的哈希节点会被添加到哈希表 ht[1] 当中，确保哈希表 ht[0] 当中的结点只减不增。当 ht[0] 表中的结点全部迁移到 ht[1] 表中后，会释放 ht[0] 表，将 ht[1] 设置为 ht[0]，并重置 ht[1]。

2. 渐进式 Rehash
   ??对于上述提到的 rehash 操作，并不是一次性全部迁移完成，而是分多次、渐进式地完成的，因为在实际环境中，哈希表中保存的节点实际上是非常多的，如果一次性全部迁移的话，会对服务器的性能造成很大影响，甚至会导致服务器服务停止。
   ??具体来说，就是在对字典进行添加、删除、查找和更新操作时，会在需要 rehash 操作时进行单步 rehash，从而将庞大的工作量分摊开来。

3. 键冲突
   ??哈希表使用链地址法来解决键冲突，即被分配到同一索引的多个键值会拉成一个单向链表，正因为如此，在查找操作时难免会用到循环结构，而新的哈希节点插入时也是采用头插法来实现的。