Redis 入门-第三篇-数据结构与对象-字典

字典在 Redis 中的应用相当广泛，比如 Redis 的数据库就是使用字典来作为底层实现的，对数据库的增删改查操作也是建立在对字典的操作之上的。

除了用来表示数据库之外，字典还是哈希键的底层实现之一，当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时，Redis 就会使用字典作为哈希键的底层实现。

字典的实现：

Redis 的字典中使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

哈希表

typedef struct dictht {
dictEntry **table;      // 哈希表数组
unsigned long size;     // 哈希表大小，总是等于 2^n 
unsigned long sizemask; // 哈希大小掩码，用于计算索引值，总是等于 size - 1，可以直接与键值的哈希相与得到该键值相应的索引
unsigned long used;     // 该哈希表已有节点的数量
}

table 属性是一个数组，数组中的每一个元素都是一个指向 dict.h/dictEntry 结构的指针，每个 dictEntry 结构保存着一个键值对。size 属性记录了哈希表的大小，也即是 table 数组的大小，而 used 属性则记录了哈希表当前已有键值对的数量。sizemask 属性的值总是等于 size - 1 ，这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。

typedef struct dictEntry {
void *key;              // 键
union{
  void *val;            // 指针类型
  uint64_t u64;         // 无符号 64 位整型
  int64_t s64;          // 有符号 64 位整型
}v;                     // 值
struct dictEntry *next; // 指向下一个哈希节点，哈希冲突时，形成链表
}dictEntry;

typedef struct dict {
dictType *type; // 类型特定函数
void *privdata; // 私有数据
dictht ht[2];   // 哈希表
int rehashidx;  // rehash 动作标记
}dict;

type 属性和 privdata 属性是针对不同类型的键值对，为创建多态字典而设置的：

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

typedef struct dictType {
unsigned int (*hashFunction)(const void *key);                         // 计算哈希值的函数  
void *(*keyDup)(void *privdata, const void *key);                      // 复制键的函数
void *(*keyDup)(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;                          

ht 属性是一个包含两个项的数组，数组中的每一个项都是一个 dictht 哈希表，一般情况下，字典只使用 ht[0] 哈希表，ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 的时候才会用。

除了 ht[1] 之外，另一个和 rehash 有关的属性就是 rehashidx，它记录了 rehash 目前的进度，如果目前还没有进行 rehash ，那么它的值就是 -1 。

随着操作的不断执行，哈希表保存的键值对会主键的增多或减少，为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多或太少时，程序需要对哈希表的大小进行相应的扩展或收缩。

扩展或收缩通过 rehash(重新散列) 操作来完成，Redis 对字典的哈希表执行 rehash 的步骤如下：

1）为字典的 ht[1] 哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及 ht[0] 当前包含的键值对数量：

• 如果执行的是扩展操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used*2 的 2^n 。
• 如果执行的是收缩操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n。

2）将保存在 ht[0] 上的所有键值对 rehash 到 ht[1] 上面：rehash 指的是重新计算键的哈希值和对应哈希表中的索引值，然后将键值对放置到 ht[1] 哈希表对应的位置上。

3）当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后，释放 ht[0] , 将 ht[1] 设置为 ht[0] , 并在 ht[1] 新建一个空白哈希表，为下一次 rehash 做准备。

哈希表的扩展与收缩

当下列条件任意一个被满足时，程序会自动开始对哈希表执行扩展操作：

1）服务器目前没有在执行 BGSAVE 或 BGREWRITEAOF 命令，且哈希表的负载因子大于等于 1

2）服务器目前在执行 BGSAVE 或 BGREWRITEAOF 命令，且哈希表的负载因子大于等于 5

其中，负载因子 = 哈希表已保存节点数量 / 哈希表大小 (load_factor = ht[0].used / ht[0].size)

当哈希表的负载因子小于 0.1 时，程序会自动开始对哈希表执行收缩操作。

渐进式 rehash：

rehash 动作不是一次性、集中式的完成的而是分多次、渐进式的完成，这样做的原因是如果哈希表中的数据量很庞大的话，一次性将 ht[0] 的值对全部 rehash 到 ht[1] 的话，庞大的计算量可能会导致服务器在一段时间内停止服务。以下是哈希表渐进式 rehash 的详细步骤：

1. 为 ht[1] 分配空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表
2. 在字典中维持一个索引计数器 rehashidx ，并将它的值设置为 0 ，表示 rehash 工作正式开始
3. 在 rehash 进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作之外，还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]，当 rehash 工作完成之后，程序将 rehashidx 属性的值加 1 
4. 随着字典操作的不断执行，最终在某个时间点上，ht[0] 的所有键值对都会被 rehash 到 ht[1] 上。这时程序将 rehashidx 属性的值设置为 -1 ，表示 rehash 操作已完成

渐进式 rehash 的好处在于它采取分而治之的方式，将 rehash 键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式 rehash 庞大的计算量带来的弊端。