字典

字典，又称符号表(symbol table)、关联数组(associative array)或映射(map)，是一种用于保存键值对(key-value pair)的抽象数据结构。

字典实现

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

哈希表

Redis字典所使用的哈希表由dict.h/dictht结构定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
 * 哈希表
 *
 * 每个字典都使用两个哈希表，从而实现渐进式 rehash 。
 */
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

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

Screenshot_20211221_220354.png

图中为一个空的哈希表，没有包含任何键值对

哈希表节点

哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 * 哈希表节点
 */
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

key属性保存着键值对中的键，而v保存键值对中的值，其中键值对的值可以是一个指针，或者一个uint64_t整数，又或者是个int64_t整数。

next属性是指向是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一起，以此来解决键冲突(collision)问题

字典

Redis中的字典由dict.h/dict结构表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
 * 字典
 */
typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */
} dict;

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

  • type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特性类型键值对的函数，redis会为用途不同的字典设置不同类型特性函数
  • 而privdata属性则保存了需要传给那些类型特定函数的可选参数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 * 字典类型特定函数
 */
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;

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

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

哈希算法

Redis计算hash值和索引值的方法如下：

1
2
3
4
5
6
// 计算给定键的哈希值
#define dictHashKey(d, key) (d)->type->hashFunction(key)

// 使用哈希表的sizemask属性和哈希值计算出索引值
// 根据情况不同,ht[x]可以是h[0]或h[1]
index = hash & dict->h[t].sizemask

如，讲一个键值对k0和v0添加到字典里面，则会先使用hash = dict→type→hashFunction(k0)计算键k0的哈希值。假设计算出来的哈希值为8，则会继续使用 index = hash & dict->h[0].sizemask = 8 & 3 = 0 计算出键k0的索引值0，这表示包含键值对k0和v0的节点应该被放置到哈希表数组的索引0位置上

Screenshot_20211224_225905.png

解决键冲突

Redis的哈希表使用链地址法(separate chaining)来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表可以组成一个单向链表，被分配到同一个索引上的多个节点 可以用这个单向链表连接起来，这样就解决的键冲突问题

Rehash

为了让哈希表的负载因子(load factor)维持在一个合理的范围内，当哈希表保存的键值对数量过多或过少时，程序需要对哈希表的大小进行相应的扩展或者收缩

Rehash步骤如下：

  1. 为字典ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以ht[0]当前包含的键值对数量（h[0].used属性的值）。如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2^n；如果是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2^n
  2. 讲保存在ht[0]中的所有键值对rehash到ht[1]上面；rehash指的是重新计算哈希和索引值，然后讲键值对放置到h[1]哈希表的指定位置上
  3. 当h[0]包含的所有键值对都迁移到ht[1]上之后，释放h[0]，将ht[1]设置成h[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备

哈希表的扩展与收缩

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

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

其中哈希表的负载因子可以通过

1
2
# 负载因子 = 哈希表已保存节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size

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

渐进式rehash

渐进式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过程中，字典会同时使用ht[0]和ht[1]两个哈希表，所以在这期间字典删除、查找。更新等操作，会在两个哈希表执行