Redis 字典(dict)

• Redis的字典和Java里的HashMap类似，不过HashMap在Java1.8是尾插法，Redis字典是头插法。
• Redis中常见字典的用处就是服务本身，还有基本类型的hash

字典的实现

哈希表

• 先把用到的四个结构体列出来，后面用到某些字段时会详细介绍

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

哈希表节点

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union{
        void *val;
        uint64_tu64;
        int64_ts64;
    } v;
    // 指向下个哈希表节点，冲突时形成链表
    struct dictEntry *next;
} dictEntry;

字典

typedef struct dictEntry {
    typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash索引
    //当rehash不在进行时，值为-1
    in trehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

typedef struct dictType {
    // 计算哈希值的函数
    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）的字典

  
  《Redis设计与实现》

哈希算法

// 通过字典设置的哈希函数，计算键key的哈希值
hash = dict -> type -> hashFunction(key);
// 使用哈希表的sizemask属性和哈希值，计算出索引值
// 根据情况不同，ht[x]可以是ht[0]或者ht[1]，数据迁移时会用
index = hash & dict-> ht[x].sizemask;

• 通过调用指定的hashFunction(key)获得key的hash码，然后和"当前容量-1"也就是sizemask，通过位运算取余得到索引，然后放入哈希表。

解决键冲突

• 链地址法。解决键冲突就是上一步取余得到的索引相同，槽位被占用，解决办法就是冲突的元素用链表连接起来，不同的是Redis的hash结构中没有记录尾元素地址，所以用头插法，也就是冲突的新元素会放到链表头部。

rehash

• hash表元素增多、减少到一定阈值（根据负载因子计算），就会触发rehash，其实就是hash表数组扩容和元素位置重排，从上面普通情况结构图得知，平时情况使用的ht[0]记录元素，ht[1]是rehash时才会用的，具体流程：
  • ht[1]申请空间：扩容时，就近取大于扩容后的元素数2^n，例如扩容后17，ht[1]就申请32的内存空间。
  • ht[0]元素移到ht[1]：这个过程要重新计算索引，因为hash表的容量变了。
  • 所有元素移动完成：释放ht[0]，把ht[0]指到ht[1]的hash表，ht[1]为null，rehash完成。
• 正常情况下扩容负载因子是1，收缩负载因子是0.1，负载因子 = 已用节点(ht[0].used) / 哈希表大小。在执行BGSAVE、BGREWRITEAOF命令时扩容的负载因子是5，这两个命令需要创建子进程，需要尽量避免内存操作。

渐进式rehash

• 如果哈希表元素过多，rehash集中转移会导致效率问题，Redis使用渐进式分次完成rehash。
• 渐进式不同于普通rehash直接完成，渐进式会持续一段时间，ht[0]ht[1]同时工作，中间可能会有用户操作数据，例如新增操作就直接在ht[1]进行，查询操作因为两个表都有元素，两个表都查。还会有一些其他辅助迁移的渠道，这样一直下去，直到渐进式rehash完成，但缺点是会导致内存浪费。