第 4 章 字典

dictEntry，node of a map

typedef struct dictEntry{
  void *key;
  union{
    void *val;
    uint64_t u64;
    int64_t s64;
  }v;
  struct dictEntry *next;
} dictEntry;

其中键值对的值可以是一个指针，或者是一个 uint64_t 整数，又或者是一个 int64_t 整数。
next 属性是指向另一个哈希节点的指针，这个指针可以将多个哈希值相同的键值对连接在一起，以此来解决键冲突的问题。也就是说，Redis 的哈希表使用了链地址法来解决键冲突。

dictht(dict hash table)

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

map

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

ht 属性是一个包含两个项的数组，数组中的每个项都是一个 dictht 哈希表，一般情况下，字典只使用 ht[0] 哈希表，ht[1] 哈希表只会在对 ht[0] 哈希进行 rehash 时使用。
除了 ht[1] 之外，另一个与 rehash 有关的属性就是 rehashidx，它记录了 rehash 目前的进度，如果目前没有在进行 rehash，那么它的值为 -1.

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;

每个 dictType 结构保存了一簇用于操作特定类型键值对的函数，Redis 会为用途不同的字典设置不同的类型特定函数。

hashFunction

Redis 计算哈希值和索引值的方法如下：

int hash = dict->type->hashFunction(key);

int index = hash & dict->ht[x].sizemask;

Redis 使用 MurmurHash2 算法来计算键的哈希值。

rehash

为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。
Redis 对字典的哈希表执行 rehash 的步骤如下：

计算哈希表的负载因子公式：
load_factor = ht[0].used / ht[0].size

1. 为字典的 ht[1] 哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及 ht[0] 当前包含的键值对数量（ht[0].usedsize):

• 如果执行的是扩展操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used*2 的 2^n.
• 如果执行的是收缩操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n.

int getRehashSize(){
  int tag = 0;
  if(扩展){
    tag = ht[1].used * 2;
  }else{
    tag = ht[1].used;
  }
  int size = 1;
  while(size < tag){
    size *= 2;
  }
  return size;
}

2. 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面。
3. 当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后，释放 ht[0]，将 ht[1] 设置为 ht[0]，并在 ht[1] 新创建一个空白哈希表，为下一次 rehash 做准备。

When will rehash happen?

扩容

1. 服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 1.
2. 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈系表的负载因子大于等于 5.

收缩

哈希表的负载因子小于 0.1 时，进行收缩操作。

渐进式 rehash

1. 每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作意外，还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]
2. rehashidx 为 0，表示开始 rehash；每完成一次对 rehashidx 的 rehash 操作，rehashidx 增加1； rehash 完成，rehashidx 为 -1.

渐进式 rehash 执行期间的哈希表操作

1. rehash 期间的查询操作：先在 ht[0] 表上查找，如果未找到，会去 ht[1] 表里查找；
2. rehash 期间的新增键值对操作，会直接新增到 ht[1] 表中，不会新增到 ht[0] 中。