Redis数据库字典大概介绍

Redis dict 笔记

字典的实现

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

hash表

  • Redis的hash表有dict.h中的dictht结构定义。
    1
    2
    3
    4
    5
    6
    7
    typedef struct dictht
    {
    dictEntry **table; //哈希表数组
    unsigned long size; //哈希表大小
    unsigned long sizemask; //哈希表大小掩码 用于计算索引值 总是等于size-1
    unsigned long used; //表示已有节点的数量
    }

hash表节点

  • Redis的hash表节点在dict.h中定义
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    typedef stuct dictEntry
    {
    void *key; //键
    union {
    void *val;
    uint64_t u64;
    int64_t s64;
    double d;
    } v; //值
    struct dictEntry *next; //指向下一个hash表节点 形成链表 开链法解决hash冲突
    }

字典

  • Redis中的字典在dict.h中由dict结构表示
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    typedef struct dict {
    dictType *type; //类型特点函数
    void *privdata; //私有数据 保存需要传给类型特定函数的可选参数
    dictht ht[2]; //hash表 一般使用ht[0] ht[1]用于rehash
    long rehashidx; //rehash索引 记录rehash进度 当rehash不在进行时,值为-1
    int iterators; // number of iterators currently running
    } dict;
    //保存用于操作特定类型键值对的函数
    typedef struct dictType {
    //hash值计算函数
    unsigned int (*hashFunction)(const void *key);
    //复制键函数
    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;

哈希算法 键位冲突 rehash

  • 先使用hashFunction函数算出hash值,再由hash值算出索引值,索引冲突使用开链法解决。当字典被用作数据库的底层实现或hash键的底层实现时,Redis使用MurmurHash算法计算键的hash值 该算法优点在于即使输入的键有规律, 仍然可以给出很好的随机分布性, 并且算法的计算速度也很快。
  • hash表保存的值会随操作不断变大或变小,为了让hash表的负载因子在合理范围,需要对hash表rehash。扩展操作后的大小为 第一次大于等于used*2的2^n(2的n次幂)。缩小操作后的大小为 第一次大于等于used的2^n(2的n次幂)
  • rehash 在ht[0]和ht[1]中渐进进行,即每次操作时才rehash ht[0]中的键到ht[1]等ht[0]空了 就可以将ht[0]释放将ht[1]设置ht[0],然后为ht[1]重新生成空hash表,为下次rehash做准备.
  • hash表负载因子计算 负载因子=ht[0].used/ht[0].size
  • hash表扩展操作
    1. 当服务器当前没有执行BGSAVE命令或者BGREWRITEAOF命令, 并且hash表的负载大于等于1
    1. 当服务器当前执行BGSAVE命令或者BGREWRITEAOF命令, 并且hash表的负载大于等于5
  • hash表收缩操作 hash表负载因子小于0.1