redis-dict源码阅读

dict结构

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;

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;

typedef struct dictht {

    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量(注意used的数量是所有的链表中的节点，比如说key1和key2冲突hash后得到的key是0，但是这里的used要加2)

    unsigned long used;

} dictht;

typedef struct dictEntry {

    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;

dict何时进行rehash（渐进式rehash）

1. 添加节点的时候，进行单步rehash（dictAddRaw）
2. 删除节点的时候，进行单步rehash（dictGenericDelete）
3. 进行查找节点的时候（dictFind）
4. 获取随机值的时候（dictGetRandomKey）
5. dictRehashMilliseconds
6. _dictRehashStep
7. 如下代码所示，每次进行上述操作的时候，会调用dictRehash（指定执行N步rehash，不会一次性rehash所有的dict节点）,渐进式的好处在于：1、不会阻塞用户的数据返回（假如用户的操作触发了rehash，如果是全量rehash，那么要等待全量rehash完成才返回数据，时间会非常长，体验不好）2、避免了系统的集中式计算

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 */
        // 将链表中的所有节点迁移到新哈希表
        // 注意：hash的冲突解决是链地址法，所以一个rehashidx对应的是一个链表，需要将整个链表移动过去
        // 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;

            // 插入节点到新哈希表
            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;
}

dict的rehash判断标准

1. dict_can_resize标识可进行rehash
2. dictIsRehashing标识没有正在进行rehash
3. hashtable[1]的可用空间大小不能小于hashtable[0]的已用空间大小
4. hashtable[0]的used!=0

int dictResize(dict *d)
{
    int minimal;

    // 不能在关闭 rehash 或者正在 rehash 的时候调用
    if (!dict_can_resize || dictIsRehashing(d)) {
        return DICT_ERR;
    }

    // 计算让比率接近 1：1 所需要的最少节点数量
    minimal = d->ht[0].used;
    if (minimal < DICT_HT_INITIAL_SIZE) {
        minimal = DICT_HT_INITIAL_SIZE;
    }

    // 调整字典的大小
    // T = O(N)
    return dictExpand(d, minimal);
}

dict怎样进行rehash

1. 进行一系列是否能rehash的判断
2. 找到当前存在ht[0]的rehashidx,表示当前rehashidx没有进行迁移（也就是：d->ht[0].table[d->rehashidx] != NULL）
3. 分配ht[1]->table的空间，大小至少为ht[0]->usedd的两倍
4. 遍历当前的节点对应的链（hash冲突使用链表法解决的，所以一个d->ht[0].table[d->rehashidx]保存了一个链表）
5. 把节点从ht[0]移动到ht[1],移动完所有的节点后，释放ht[0],将原来的ht[1]成为新的ht[0],创建一个新的ht[1]
6. 修改rehashidx的值

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 */
        // 将链表中的所有节点迁移到新哈希表
        // 注意：hash的冲突解决是链地址法，所以一个rehashidx对应的是一个链表，需要将整个链表移动过去
        // 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;

            // 插入节点到新哈希表
            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;
}

dict如何解决hash冲突

1. hash冲突：指两个不同的键拥有相同的hash值
2. 链地址法： 使用链表将多个哈希值相同的节点串连在一起， 从而解决冲突问题
3. 如图，0号节点的key4和key1产生了hash冲突（hash冲突：key4和key1算出来的hash的值都为0，链地址法：dict使用链表把key4和key1链接起来，从而可以解决hash冲突的问题）

static int _dictKeyIndex(dict *d, const void *key)
{
    unsigned int h, idx, table;
    dictEntry *he;

    /* Expand the hash table if needed */
    // 单步 rehash
    // T = O(N)
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;

    /* Compute the key hash value */
    // 计算 key 的哈希值
    h = dictHashKey(d, key);
    // T = O(1)
    for (table = 0; table <= 1; table++) {

        // 计算索引值
        idx = h & d->ht[table].sizemask;

        /* Search if this slot does not already contain the given key */
        // 查找 key 是否存在
        // T = O(1)
        he = d->ht[table].table[idx];
        while(he) {//如果当前节点已经存在值（就是hash冲突），就计算他的链表的最后节点的指针
            if (dictCompareKeys(d, key, he->key))
                return -1;
            he = he->next;
        }

        // 如果运行到这里时，说明 0 号哈希表中所有节点都不包含 key
        // 如果这时 rehahs 正在进行，那么继续对 1 号哈希表进行 rehash
        if (!dictIsRehashing(d)) break;
    }

    // 返回索引值
    return idx;
}

安全迭代器和非安全迭代器有什么区别

1. 安全迭代器：在迭代进行过程中，可以对字典进行修改
2. 不安全迭代器：在迭代进行过程中，不对字典进行修改

redis如何保证遍历dict的时候能遍历到全部的数据

1. 还需要查看dictscan函数，算法有点复杂
2. 建议阅读以下文章

   http://chenzhenianqing.com/articles/1101.html
   http://blog.csdn.net/gqtcgq/article/details/50533336
   http://www.arthuryangcs.com/2016/12/10/Redis%E6%BA%90%E7%A0%81%E5%89%96%E6%9E%90%EF%BC%88%E4%B8%80%EF%BC%89-%E6%B7%B1%E5%85%A5%E7%90%86%E8%A7%A3dict%E5%8F%8AdictScan/

有趣的代码

1. 计算索引值
   如下代码：d->ht[table].sizemask的值为2的n次方-1（为size-1）
   其实下面代码的含义可以理解为h和sizemask”取模”（不是真正意义的取模哦）

idx = h & d->ht[table].sizemask;