Redis 字典(dict.h/dict.c)（4）

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

Paste_Image.png

1.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，迁移一个非空桶。

2.数据结构

//dict 元素
typedef struct dictEntry {
    void *key;
    //共同体，只会存在一个值，按照最长的变量开辟一个空间
    //场景：各数据类型各变量占用空间差不多并且对各变量同时使用要求不高的场合
    union {
        void *val;
        uint64_t u64;//无符号
        int64_t s64;
        double d;
    } v;//值
    struct dictEntry *next;
} dictEntry;

//类型描述
typedef struct dictType {
    unsigned int (*hashFunction)(const void *key); //hash函数
    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;

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
//hash table 结构
typedef struct dictht {
    dictEntry **table;
    unsigned long size;//大小
    unsigned long sizemask; //模数
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;