https://blog.csdn.net/xsjzn/article/details/117196010

1.字典的实现

Redis的字典使用哈希表作为底层实现。

1.1 哈希表

Redis字典所使用的哈希表结构定义如下：

typedef struct dictht {

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

    // 哈希表大小
    unsigned long size;

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

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;

table属性是一个数组，数组中的每个元素都指向一个dictEntry结构的指针，每个dictEntry结构保存着一个键值对。

如下图所示为一个空的哈希表

1.2 哈希表节点

哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存一个键值对：

typedef struct dictEntry {

    // 键
    void *key;

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

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

} dictEntry;

1.3 字典

Redis中的字典结果如下：

typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;

type属性和privdata属性是针对不同类型的键值对，而创建多态字典而设置的：

type属性是一个指向dictType结构的指针，每个dictType结构保存了一组用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同类型的特定函数。

而privadata属性则保存了需要传给那些类型特定函数的可选参数。