redis学习之三字典 redis

之前相关联文章：
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的步骤如下：

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

三扩容与缩容的时机

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

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

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

下面是两rehash的过程图：