Redis 源码--字典P3 初始化和Rehash。

一个字典所要做的最重要的工作就是保证快速的查找，删除和修改值。

首先可以来看一下Redis的初始化过程。

Redis的字典的初始方法是

dict *dictCreate(dictType *type,
        void *privDataPtr)
{
 // 为dict结构体分配内存
    dict *d = zmalloc(sizeof(*d));
//初始化
    _dictInit(d,type,privDataPtr);

    return d;
}

通过调用 _dictInit(d,type,privDataPtr)来实现初始化。

int _dictInit(dict *d, dictType *type,
        void *privDataPtr)
{
    // 初始化两个哈希表的各项属性值
    // 但暂时还不分配内存给哈希表数组
    _dictReset(&d->ht[0]);
    _dictReset(&d->ht[1]);

    // 设置类型特定函数
    d->type = type;

    // 设置私有数据
    d->privdata = privDataPtr;

    // 设置哈希表 rehash 状态
    d->rehashidx = -1;

    // 设置字典的安全迭代器数量
    d->iterators = 0;

    return DICT_OK;
}

这个方法对于dict结构的各个配置做了初始化。应该注意_dictReset()方法并未分配内存给dictht结构中的entry数组，只是简单的初始化（赋给null）。

static void _dictReset(dictht *ht)
{
  // 只赋值 ht->table  为null。
    ht->table = NULL;
    ht->size = 0;
    ht->sizemask = 0;
    ht->used = 0;
}

此时的核心数组还没有初始化，这个过程是通过dictExpand方法来实现的。
这个方法遵循这样一个规则，在方法体内初始化一个长度大于等于我们所要SIZE的TABLE，（通过_dictNextPower(size)来实现），如果此时第一个table还没有初始化，那么通过将table赋给ht[0],dictExpand实现的是数组的初始化，如果已经初始化了，那么dictExpand将其赋给第二个table数组ht[1]，通过将rehashindex置零，来实现之后的rehash过程。

int dictExpand(dict *d, unsigned long size)
{
    // 新哈希表
    dictht n; /* the new hash table */

    // 根据 size 参数，计算哈希表的大小
    // T = O(1)
    unsigned long realsize = _dictNextPower(size);

    /* the size is invalid if it is smaller than the number of
     * elements already inside the hash table */
    // 不能在字典正在 rehash 时进行
    // size 的值也不能小于 0 号哈希表的当前已使用节点
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */
    // 为哈希表分配空间，并将所有指针指向 NULL
    n.size = realsize;
    n.sizemask = realsize-1;
    // T = O(N)
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    // 如果 0 号哈希表为空，那么这是一次初始化：
    // 程序将新哈希表赋给 0 号哈希表的指针，然后字典就可以开始处理键值对了。
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }
  /* Prepare a second hash table for incremental rehashing */
    // 如果 0 号哈希表非空，那么这是一次 rehash ：
    // 程序将新哈希表设置为 1 号哈希表，
    // 并将字典的 rehash 标识打开，让程序可以开始对字典进行 rehash
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;

下面来看一下dict的rehash过程，Redis的rehash不是一蹴而就的，而是以桶为单步进行的单步式渐进型rehash。对于键值对数量非常庞大的情况，如果一下子将所有的键值对都进行hash，那么大部分CPU时间都将花在rehash过程中，此时的响应是非常差的。所以Redis采取分步式的逐步渐进。
这里使用了一个宏来#define dictIsRehashing(ht) ((ht)->rehashidx != -1) ，简单的判断rehashindex是否是-1来判断是否在rehash，后面也会大量的出现这个宏。
我对这个函数稍微有点疑问，主要在于

  // 确保 rehashidx 没有越界
        assert(d->ht[0].size > (unsigned)d->rehashidx);

        // 略过数组中为空的索引，找到下一个非空索引
        while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;

这个部分，疑问是 这里是否在while之中也应该加入一句防御性语句（d->ht[0].size > (unsigned)d->rehashidx)，改为 while(（d->ht[0].size > (unsigned)d->rehashidx)&&（d->ht[0].table[d->rehashidx] == NULL）)保证rehashidx小于等于d->ht[0].size-1。

int dictRehash(dict *d, int n) {

    // 只可以在 rehash 进行中时执行
    if (!dictIsRehashing(d)) return 0;

    // 进行 N 步迁移
    // T = O(N)
    while(n--) {
        dictEntry *de, *nextde;

        /* Check if we already rehashed the whole table... */
        // 如果 0 号哈希表为空，那么表示 rehash 执行完毕
        // T = O(1)
        if (d->ht[0].used == 0) {
            // 释放 0 号哈希表
            zfree(d->ht[0].table);
            // 将原来的 1 号哈希表设置为新的 0 号哈希表
            d->ht[0] = d->ht[1];
            // 重置旧的 1 号哈希表
            _dictReset(&d->ht[1]);
            // 关闭 rehash 标识
            d->rehashidx = -1;
            // 返回 0 ，向调用者表示 rehash 已经完成
            return 0;
        }

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        // 确保 rehashidx 没有越界
        assert(d->ht[0].size > (unsigned)d->rehashidx);

        // 略过数组中为空的索引，找到下一个非空索引
        while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;

        // 指向该索引的链表表头节点
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        // 将链表中的所有节点迁移到新哈希表
        // T = O(1)
        while(de) {
            unsigned int h;

            // 保存下个节点的指针
            nextde = de->next;

            /* Get the index in the new hash table */
            // 计算新哈希表的哈希值，以及节点插入的索引位置
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;

            // 首部插入节点到新哈希表，效率更高O(1)
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;

            // 更新计数器
            d->ht[0].used--;
            d->ht[1].used++;

            // 继续处理下个节点
            de = nextde;
        }
        // 将刚迁移完的哈希表索引的指针设为空
        d->ht[0].table[d->rehashidx] = NULL;
        // 更新 rehash 索引
        d->rehashidx++;
    }

    return 1;
}

Redis的rehash过程只有在不存在安全迭代器的情况下才可以进行。如果存在一个安全迭代器，我们没有办法保证在两种不同的迭代和修改操作（迭代器和Rehash过程）不会弄乱字典。而非安全迭代器被限定为只能迭代，不能改变或者插入值。所以没有关系。
所以Redis的单步Rehash过程是这样定义的：

static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1);
}

这个函数被大量的查找、更新操作调用时，在不存在安全迭代器的条件下，
可以让字典在被使用的同时进行 rehash 。