Redis 字典

用于保存键值对的抽象数据结构，同样由于 C 语言没有内置，Redis 构建了字典的实现。

通过 哈希表+哈希表 节点实现。

1 哈希表

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

2 哈希表节点

typedef struct dictEntry {
    void *key;
    
    union {
        void *val;
        uint64_tu64;
        int64_ts64
    } v;
    struct dictEntry *next;
}

key 为键值对中的键，val 为键值对中的值，值可以是指针、uint64_t、int64_t三种类型之一。通过 next 指针将多个哈希值相同的节点连接形成链表。

3 字典

typedef struct dict {
    dictType *type;
    
    void *privadata;
    
    dictht ht[2];
    
    int rehashidx;
}

type 属性指向一个 dictType 结构的指针，用来为不同类型的字典指定不同类型的特定函数，privadata 为dictType 内部函数的参数。

ht 是一个包含两个哈希表的数组，只有在 rehash 时候才会使用另外一个哈希表。

rehashidx 记录了 rehash 的进度：

4 渐进式 rehash

由于扩容或者缩容的时候，需要将 ht[0] 里面的所有键值对rehash到 h[1] 中，如果表中的键值对非常多的时候，会导致rehash时间较长，所以为了避免这个问题，Redis 不是一次性的 rehash，而是多次、渐进式的将键进行 rehash。

在 rehash 过程中字典会同时使用 ht[0] 和 ht[1] 两个哈希表，所以期间的删除、查找、更新等操作会在两个哈希表上进行，先查 ht[0] 再查 ht[1] , 而插入会保存在 ht[1] 中。