【Redi设计与实现】第四章：字典-阿里云开发者社区

字典，又称符号表、关联数组、映射，是一种用于保存键值对的抽象数据结构。

在字典中，一个键和一个值进行关联，这些关联的键和值就被称为键值对。

字典中的每个键都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除某个键值对，等等。

字典经常作为一种数据结构内置在很多高级编程语言当中，但是Redis使用的是C语言并没有内置这种数据结构，因此 Redis 构建来自己的字典实现。

4.1 字典的实现

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

4.1.1 哈希表

Redis字典所使用的哈希表由 dictht 结构定义:

typedef struct dictht{
  // 哈希表数组
  dictEntry **table;
  // 哈希表大小
  unsigned long size;
  // 哈希表的大小掩码，用于计算索引值，总是等于 size - 1
  unsigned long sizemask;
  // 该哈希表已有节点的数量
  unsigned long used;
} dictht;

table 属性是一个数组，数组中的每个元素都是一个指向 dictEntry 结构的指针，每一个 dictEntry 结构都保存着一个键值对。

size 属性记录来哈希表的大小，也就是 table 的大小，而 used 属性则记录哈希表当前被使用的节点数量。

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

基本结构如图 4-1 所示：

4.1.2 哈希表节点

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

typedef struct dictEntry{
  // 键
  void *key;
  // 值
  union{
    void *val;
    uint64_tu64;
    int64_ts64;
  }v;
  // 指向下一个哈希表节点，形成链表
  struct dictEntry *next;
}dictEntry;

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

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

解决方法如图 4-2 所示：

4.1.3 字典

Redis中的字典由 dict 结构表示：

typedef struct dict {
  // 类型特定的函数
  dictType *type;
  // 私有数据
  void *privdata;
  // 哈希表
  dictht ht[2];
  // rehash索引
  // 当rehash不在进行时，值为-1
  int rehashidx; /* rehashing not in progress if rehashidx == -1 */
}dict;

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

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

typedef struct dictTtpe {
  // 计算哈希值的函数
  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 哈希表，一般情况下，字典只能使用 ht[0] 哈希表，ht[1] 哈希表只会对 ht[0] 哈希表进行rehash时使用。

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

如图 4-3 所示，代表一个普通状态下的字典。

4.2 哈希算法

当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新建的哈希表节点放到哈希表数组的指定索引上面。

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

计算字典设置的哈希函数，计算键key的哈希值
hash = dict -> type -> hashFunction(key);
使用哈希表的sizemask属性和哈希值，计算出索引值
根据情况不同，ht[x]可以是ht[0]或者ht[1]
index = hash & dict -> ht[x].sizemask;

举个例子，对于图 4-4 所示的字典来说，如果我们要将一个键值对K0和V0添加到字典里面，那么程序会优先使用语句：

hash = dict -> type -> hashFunction(K0);

计算出键K0的哈希值。

假设计算得出的哈希值为8，那么程序会继续使用语句：

index = hash&dict -> ht[0].sizemask = 8 & 3 = 0;

对于这里的 sizemask 值，必须是 2^n - 1，原因在于：2^n - 1 每一个二进制的位置都是1，这样我们的哈希值 & sizemask 的话，会落在 0 ～ sizemask 之间，防止越界。

当然，在我们的 Redis 中采用的是 MurmurHash2。

4.3 解决键冲突

当有两个或两个以上数量的键被分配到了哈希表数组的同一个索引上，我们称这些键发生了冲突。

Redis的哈希表使用链地址法来解决键冲突，每个哈希表节点都有一个 next 指针，多个哈希表节点可以用 next 指针构成一个单向链表。

注意：这里在进行插入的时候，采用的是头插法，时间复杂度为O(1)，假如采用尾插法的话，会进行链表的遍历，造成性能的浪费。

4.4 rehash

随着操作的不断执行，哈希表保存的键值会逐渐的增多或者减少，为了让哈希表的负载因子维持在一个合理的范围，当哈希表保存的键值过多或者过少时，都需要对哈希表进行相应的扩展或缩小。

负载因子 = ht[0].used / ht[0].size();

扩展和收缩都可以通过rehash操作来完成，Redis对字典的哈希表执行rehash的步骤如下：

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

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

将保存在ht[0]中的所有键值对rehash到ht[1]上面，rehash指的是重新计算键的哈希值和索引值，然后将键值对放置在ht[1]哈希表的指定位置上。
当ht[0]包含的所有键值对都迁移到ht[1]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。

4.5 渐进式rehash

我们知道，在进行扩展和收缩的过程中，要进行rehash，但是这个rehash并不是一次性完成的，而是要经过多次、渐进式完成的。

这样做的原因在于，如果ht[0]只保存4个键值对，那么一次性rehash完全可以，但是如果我们的键值对达到了上亿的级别，一次性的rehash会带来极大的负载，可能会造成我们的服务器停止服务。

以下是rehash的详细步骤：

为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表；
在我们字典中有一个 rehashidx ，将他的值设置为0，代表rehash已经开始；
在rehash期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作之外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1];
随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1]，这时候程序将 rehashidx 属性设为-1，表示rehash操作已经完成。

优点：采取分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的添加、删除、查找操作上，从而避免了集中式rehash而带来庞大的计算量。

在进行渐进式rehash的过程中，字典会同时使用ht[0]和ht[1]两个哈希表，所以，在渐进式rehash期间，字典的删除、查找、更新等操作会在两个哈希表上进行。

进行添加操作的时候，一律会被添加保存到ht[1]里面，而ht[0]则不再进行任何添加操作。这保证了ht[0]包含的键值对数量会只增不减，并随着rehash操作的执行逐渐变成空表。