之前相关联文章：
redis学习之一SDS
redis学习之二链表

一 字典相干的数据结构

哈希表定义：

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_t u64;        int64_t s64;    }v;    //指向下个哈希表节点，造成链表    struct dictEntry *next;}dictEntry;

字典定义：

typedef struct dict{    //类型函数    dictType *type;    //公有数据    void *private;    //哈希表    dictht ht[2];    //rehash索引，当rehash不再进行时值为-1，    //每次进行rehash时，rehashidx的值就是对应ht[0]里dictht中dictEntry数组的索引    int rehashidx;}dict;

上面是没有进行rehash的字典意识图：

redis应用MurmurHash2算法来计算键的哈希值，应用链地址法解决键抵触。

rehash与渐进式rehash

二 扩容与缩容过程
当哈希表保留的键值对数量太多或太少的时候，哈希表会进行扩大或膨胀。rehash的步骤如下：

  1. 为字典ht[1]调配空间。
    扩容：ht[1]的大小为第一个大于等于ht[0].used*2的2的n次幂；
    缩容：ht[1]的大小为第一个大于等于ht[0].used的2的n次幂。
  2. 将保留在ht[0]中的所有键值对rehash到ht[1]下面，在这个过程中会从新计算键的哈希值与索引值。
  3. 当ht[0]所有键值都迁徙到了ht[1]之后，开释ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下次rehash做筹备。

三 扩容与缩容的机会

  1. 服务器没有执行BGSAVE或BGREWRITEAOF命令，且哈希表的负载因子大于等于1。
  2. 服务器正在执行BGSAVE或BGREWRITEAOF命令，且哈希表的负载因子大于等于5。
  3. 哈希表的负载因子小于0.1。

四 渐进式rehash

思考到redis服务性能，rehash并不是一次性集中进行而是分屡次渐进式进行的，步骤如下：

  1. 为ht[1]调配空间，让字典同时持有ht[0] ht[1]两个哈希表。
  2. 将下面定义的dict构造里的rehashidx值设置为0，示意rehash开始进行。
  3. 每次对字典进行增加、删除、查找或更新时，除了进行这些操作外，还会将ht[0]在rehashidx索引上的所有键值对rehash到ht[1]，rehash的过程上中rehashidx值为增1。
  4. ht[0]里所有键值对rehash到ht[1]后，将rehashidx值置为-1，rehash完结。

上面是两rehash的过程图：

这个还没进行rehash，所以这里的rehashidx值为-1，留神ht[0]里dictEntry里的值。

这里rehashidx值为3，这是在对ht[0]里dictEntry里第3个键值对（k1,v1）进行rehash。

此文大部分内容都来自于黄健宏《Redis设计与实现》一书