redis字典 - 969251639/study GitHub Wiki

redis的哈希表结构如下

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

table的每个元素都是只想dictEntry的结构

typedof struct dictEntry {
    //key
    void* key;
    //value
    union {
        void* val;
        uint64_tu64;
        int64_tu64;
    };
    //指向下一个哈希表节点，形成链表（哈希冲突）
    struct dictEntry* next;
}dictEntry;

redis的字典结构如下：

typedof struct dict {
    //类型特定函数
    dictType* type;
    //私有数据
    void* privdata;
    //哈希表
    dictht ht[2];
    //rehash索引，当rehash不在进行时为-1
    int trehashidx;
}dict;

这里要注意的是ht是一个包含了2个项的dictht数组，一般情况下都是用ht[0]来作为哈希表使用，ht[1]在rehash时使用，trehashidx进行记录rehash的进度，没有rehash时该值为-1

redis的rehash和java的rehash不太一样，java是一次性的搬，而redis是渐进式的搬，其主要步骤如下：

1. 为字典的ht[1]哈希表分配空间，大小取决于要执行的操作，以及ht[0]当前包含的键值对数量，不管是扩容还是缩容都是已2的n次方进行
2. 将保存在ht[0]中的所有键值对rehash到ht[1]上
3. 当ht[0]包含的所有键值对都迁移到了ht[1]之后，释放ht[0]，并将ht[1]设置为ht[0]，并在ht[1]新创建一个空白的哈希表，为下一次rehash做准备

渐进式rehash

1. 为ht[1]分配空间，让字典同事持有ht[0]和ht[1]两个哈希表
2. 在字典zho维持一个索引计数器变量rehashidx，并将它的值置为0，表示rehash开始
3. rehash期间，删改都会在两个哈希表上操作，新增则放到ht[1]这个新的哈希表中，获取也是一样，在两个哈希表中找