Redis中字典(Dictionary)的实现

末蓝、 2022-10-02 13:00 122阅读 0赞

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

在字典里面，一个键(key)可以和一个值(value)进行关联(将键映射为值)

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

Redis所使用的C语言里面没有内置这种数据结构，所以Redis构建了自己的字典实现。

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

几个例子，当我们执行命令

![20180517160507519][]

在数据库中创建了一个键为msg，值为 hello world的键值对，这个键值对就是保存在代表数据库的字典里面的。

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

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

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

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

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

typedef struct dictEntry\{  
   void \*key;  
   union\{  
      void \*val;  
      uint\_64\_tu64;  
      int64\_ts64;  
     \} v  
     struct dictEntry \*next;  
\}dictEntry;  
key属性保存着键值对中的键，而v属性则保存着键值对中的值，其中键值对的值可以是一个指针，或者一个整数。  
next属性是指向下一个哈希表节点，这个指针可以将多个哈希值相同的键值对链接在一起，以此来解决键冲突问题。

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

typedef struct dict\{  
   //类型特定函数  
   dictType \*type;  
   //私有数据  
   void \*privdata;  
   //哈希表  
   dictht ht\[2\];  
   //rehash索引  
   //当rehash不在进行时，值为-1  
   int trehashidex  
\}  
type属性和privdata属性是针对不同类型的键值对，为创建多态字典而设置的。

type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为不同用途的字典设置不同类型的特定函数。  
而private属性则保存了需要传给那些类型特定函数的可选参数  
typedef struct dictType\{  
       unsigned int \*(hashFunction)(const void \*key);  
   
       void \*(\*keyDup)(void \*privdata,const void \*key);  
   
       void \*(\*valDup)(void \*privdata,const void \*obj);  
   
       ....  
   
   
   
\}  
ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一边情况下，字典除了只使用ht\[0\]哈希表，ht\[1\]哈希表只会在对ht\[0\]哈希表进行rehash是使用。

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

![20180517164557410][]

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

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

index= hash&dict->ht\[x\].sizemask;

**解决键冲突**  
   当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时，我们称这些键发生了冲突，拉链法解决冲突。具体的解决方法可以参考hashmap的实现原理。这里就不具体赘述了。着重讲解下面的Rehash和渐进式hash。

**Rehash**  
    随着操作的不断增加，哈希表保存的键值对会逐渐的增多或者减少，为了让哈希表的负载保存在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序对hash表的大小进行动态的扩展或者收缩。

拓展和收缩哈希表的工作可以通过执行Rehash操作来完成，Redis的字典的Rehash过程如下：

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

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

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

下面举个例子，架设程序要对图4-8所示字典的ht\[0\]进行拓展操作，那么程序将执行以下步骤：

![20180517171347276][]

![20180517171407143][]

[20180517160507519]: /images/20220112/9e89c5d146c24b8aa42aba26054ddfd0.png
[20180517164557410]: /images/20220112/6f724fd6f48f48fbbae8a02bebeceef8.png
[20180517171347276]: /images/20220112/8ef0b0c7bc2f4c7a996cb6445949e450.png
[20180517171407143]: /images/20220112/a3ec4d9be2c742a18fe3e7a77c14400d.png