Redis数据结构（三）字典

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

  我们在很多高级编程语言中都能找到字典的踪迹，比如说java中的Map数据结构。一个键（key）可以和一个值（value）进行关联，可以用过key来对value值进行修改删除。Redis采用C语言实现，然而C语言中并没有内置这种数据结构，但是这种数据结构又是非常必要的，所以Redis自己构建了这种数据结构。
  字典对于Redis来说可以说是非常非常重要的数据结构了，我们常用的Redis数据库，创建一个键值对的时候，就是保存在代表数据库的字典里面的。而且，字典还是哈席键的底层实现之一（当数据量较小时，hash键采用ziplist实现）。

一、结构

1. 我们先来瞅瞅字典数据结构的定义

typedef struct dict {// 类型的特定函数，封装了一些用于操作特定类型键值对的函数。    dictType *type;    // 私有数据    void *privdata;    // 哈希表数组，大小为2    dictht ht[2];    // rehash时的索引，当没有进行reshash或者rehash完成后，值为-1；该值在2.8及之前为int    long rehashidx; /* rehashing not in progress if rehashidx == -1 */ int iterators; /* number of iterators currently running */} dict;

我们可以看出，字典的底层数据结构是哈希表实现（dicht），有同学会疑惑，为啥是一个大小为2的哈表表数组呢？

这其实，是为了当节点数量增加到一定的数量，或者加少到一定的数量，程序就会自动的进行rehash操作，以保证哈希表的负载因子维持在一个合理的范围内。而在rehash的时候将会用到ht[1]这个哈希表，而平时的时候都是用的ht[0]这个哈希表，而rehashidx也是在rehash的时候用于标记索引位置的。

  在面的结构中定义中我们可以看到type属性是指向dictType结构的指针，每个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;

2. 我们再来瞅瞅哈希表的数据结构定义

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

我们从上面对哈希表的数据结构定义可以看出，哈希表的底层为一个dictEntry的数据结构数组，而在每个dictEntry结构中保存着一个键值对。size属性记录了哈希表的大小，也就是table数组的大小。used属性则记录了hash表已有的节点的数量。如图展示了一个空的哈希表结构：

3. 我们再看看哈希表节点dictEntry

typedef struct dictEntry {// 键    void *key;    // 值    union { void *val; uint64_t u64; int64_t s64; double d;    } v;    // 指向下一个哈希表节点    struct dictEntry *next;} dictEntry;

我们可以看出，key中保存着键值对中的键，而v属性可以是一个指针，或者unit64_t证书，又或者是一个int64_t类型的整数。为什么会有next指针指向另一个dictEntry节点呢，这是由于，可能发生hash冲突，为了解决hash冲突，就把hash值相同的键值对链接在一起。这就有点类似于java的hashMap的底层了，只是没有那么复杂。当然，由于dictEntry没有指向链表尾部的指针，所以为了提升效率，每次新增的时候都会插入到头部。如图所示：

我们由此可以了解到，字典的底层数据结构为hash表，hash表的底层数据结构为dictEntry，这样我们就可以表示出字典的整体结构图：

二、rehash

  之前我们提到过，字典定义中有一个rehashidx属性以及h[1]是用于rehash的时候使用的，下面我们来看看rehash的过程。
  之所以需要rehash是因为随着操作的不断执行，哈希表所保存的键值对会逐渐的增多或减少，为了让哈希表的负载因子维持在一个合理的范围内，当哈希表保存的键值对数量太多或者太少的时候，程序需要对哈希表进行相应的扩展或者收缩。而这个动作就是rehash。
具体需要执行的步骤如下：

1. 为字典h[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前所包含的键值对数量（扩展或缩小后的大小必须是2ⁿ）；
2. 将保存在ht[0]中的所有键值对rehash（也就是重新计算哈希值和索引值）到ht[1]上面；
3. 当h[0]包含的所有键值对都迁移到了ht[1]后，释放h[0]，将h[1]设置为ht[0]，原h[0]设置为ht[1]，并在ht[1]创建一个空白的哈希表。为下一次rehash做准备。

当然，由ht[0]rehash到ht[1]这个过程示渐进式的，而不是一次性的。步骤如下：

1. 为ht[1]分配空间，让字典同时持有ht[1]和ht[0]两个空间表
2. 在字典中维持一个索引计数器变量rehashidx,并将其值设置为0，表示rehash工作正式开始
3. 在rehash期间每次对字典进行的添加、删除、修改式，程序出了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],然后值+1
4. 所有值rehash完毕，rehashidx重置为-1；
   在整个过程中，如果有新的键值对添加，就会直接添加到ht[1]中，所有的删除、查找、更新会在两个哈希表中进行
   我们可以通过图示来看一下具体过程：
   如图所示，一个待rehash的字典。已使用4.
   

我们可以看到，used当前的值为4，4*2=8满足2ⁿ。所以，程序将会为h[1]哈希表的大小设置为8，并分配内存空间。如下：

我们依此先将0号为上的键值对rehash到ht[1]上

我们可以看出，当进行一次rehash后，rehashidx变为了0，而ht中相应的used属性也随之变化。我们依次将所有节点都rehash后如图所示

然后，我们将释放h[0]，将h[1]设置为ht[0]，原h[0]设置为ht[1]，并在ht[1]创建一个空白的哈希表，且将rehashidx重置为-1，如图所示：

冰雪之城