字典(dict.h/dict.c)

Redis字典具有以下特点：

• Redis字典的底层实现为哈希表，
• 每个字典使用两个哈希表， 一般情况下只使用 0 号哈希表， 只有在 rehash 进行时， 才会同时使用 0 号和 1 号哈希表。
• 哈希表使用链地址法来解决键冲突的问题。
• 自动 Rehash 扩展或收缩哈希表。
• 对哈希表的 rehash 是分多次、渐进式地进行的。

数据结构

/*
 * hash节点
 */

typedef struct dictEntry {

    //键
    void *key;

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

    //指向下一个节点
    struct dictEntry *next;
} dictEntry;

typedef struct dictht {

    //桶
    dictEntry **table;

    //指针数组大小
    unsigned long size;

    //指针数组掩码，用于计算索引值
    unsigned long sizemask;

    //hash表现有节点数量
    unsigned long used;
} dictht;

typedef struct dict {

    //类型处理函数
    dictType *type;

    //类型处理函数私有值
    void *privdata;

    //两个hash表
    dictht ht[2];

    //rehash标示，为－1表示不在rehash，不为0表示正在rehash的桶
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    //当前正在运行的安全迭代器数量
    int iterators; /* number of iterators currently running */
} dict;

dict的结构如下：

字典中添加元素的过程

rehash介绍

字典的 rehash 操作实际上就是执行以下任务：

创建一个比 ht[0]->table 更大的 ht[1]->table ， size为大于used*2的2的指数, 开始值为4；

将 ht[0]->table 中的所有键值对迁移到 ht[1]->table ；

将原有 ht[0] 的数据清空，并将 ht[1] 替换为新的 ht[0] ；

进行rehash的条件：

自然 rehash ： ratio >= 1 ，且变量 dict_can_resize 为真。

强制 rehash ： ratio 大于变量 dict_force_resize_ratio （目前版本中， dict_force_resize_ratio 的值为 5 ）。

阶进rehash：

主动方式：databaseCron中调用dictRehashMilliseconds执行一毫秒。

被动方式：调用dictAdd，dicFind，dictDelete，dictGetRandomKey时，调用_dictRehashStep，迁移一个非空桶。