1.简介
字典是一种用于保存键值对(key-value)的数据结构，其中每个键都是唯一的。Redis构建了自己的字典实现。
字典在Redis中应用相当广泛，Redis的数据库就是使用字典作为底层实现的，对数据库的增、删、改、查操作也够基于字典的操作上的。
除了数据库外，字典还是哈希键的底层实现之一，当一个hash键包含的键值对比较多，或者键值对中的元素都是比较长的字符串时，Redis就会使用字典作为哈希键的底层实现。
2.实现
2.1 哈希表的定义：
typedef struct dictht{
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小的掩码，用于计算索引值，总是等于 size-1
unsigned long sizemark;
//哈希表已有的节点数量
unsigned long used;
} dictht;- table属性是一个数据，其中每个元素都是指向 dictEntry结构的指针，每个dictEntry结构保存着一个键值对；
- size属性记录了哈希表的大小，也即table数据的大小；
下图是一个大小为4的空的哈希表：
2.2 哈希表的节点，dictEntry的结构如下：
typedef struct dictEntry{
//键
void *key;
//值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
//指向下个哈希表节点
struct dictEntry *next;
} dictEntry;- key保存键值对的键；
- 而v属性保存着键值对的值，其中值可能是一个指针，或者是一个uint64_t的整数，又或者是一个int64_t的整数；
- next指向下一个哈希表节点，形成一个链表，以此来解决键冲突的问题。如下图展示了如何通过next指针将索引值相同的键k0与k1连接起来：
2.3 字典的结构
typedef struct dict{
//类型特定函数
dictType *type;
//私有数据
void *privdata;
//哈希表
dictht ht[2];
//rehash索引；当rehash不在进行时，值为-1
int rehashidx;
} dict;type和privdata属性是针对不同类型的键值对，为创建多态字典而设置的：
- type的每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数。
- privdata保存了需要传给类型特定函数的可选参数。
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;- ht属性是一个把汗两个元素的数组，每个元素都是一个dictht哈希表，一般情况下，字典只使用ht[0]，ht[1]哈希表只会在对ht[0]进行rehash时使用。
- rehashidx记录了rehash目前的进度，如果当前没有在进行rehash，那么它的值为-1.
下图展示了一个普通状态(没有进行rehash)下的字典：
3.哈希算法
当一个新的键值对要加入字典时，首先需要根据键值对的键计算出哈希值和索引值，然后再根据索引值将键值对放到哈希表数组指定的索引上。**
//使用字典设置的哈希函数，计算key的hash值
hash = dict -> type -> hashFunction(key);
//使用哈希表的sizemask和哈希值，计算出索引
//根据不同情况，ht[x]可以是ht[0]和ht[1]
index = hash & dict -> ht[x].sizemask;当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。
4.解决键冲突
当有两个或以上的键被分配到哈希表数组的同一个索引上时，我们称这些键发生了冲突。
哈希表使用链地址法来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，这就解决了键冲突问题。
因为节点组成的链表没有指向链表表尾的指针，所以为了速度考虑，总是将新节点添加到链表的表头位置(时间复杂度(O(1)))。
如下图所示，展示了存在键冲突的hash表(k1和k2键存在冲突)：
5.哈希表什么时候开始扩展时收缩
当满足下列任意条件，哈希表会自动开始进行扩展操作：**
- 服务器目前没有在执行BGSAVE或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1；
- 服务器目前正在执行BGSAVE或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。
负载因子计算公式：
load_factor = ht[0].used / ht[0].size根据BGSAVE或者BGREWRITEAOF命令是否正在执行，服务器执行扩展操作的负载因子并不相同，这是因为在执行BGSAVE或者BGREWRITEAOF命令的过程中，Redis'需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免子在进程存在期间进行哈希表的扩展操作，这可以避免不必要的内存写入操作，最大限度地节约内存。
当哈希表的负载因子小于0.1时，会自动执行收缩操作。**
6.rehash
随着操作的不断执行，哈希表保存的键值对会逐渐的增多或者减少，为了让哈希表的负载因子维持在一个合理的范围内，当哈希表保存的键值对数量太多或者太少时，要对哈希表的大小进行相应的扩展或者收缩。
扩展或者收缩哈希表可以通过执行rehash（重新散列）来完成，步骤如下：
1） 为字典ht[1]哈希表分配空间，其大小的计算方式如下：
- 如果是扩展操作，大小为第一个大于等于ht[0].used*2的2^n^ ;
- 如果是收缩操作，大小为 第一个大于等于ht[0].used的2^n^。
2） 将保存在ht[0]中的所有键值对rehash（指重新计算键的哈希值和索引值，然后将键值对放到ht[1]指定位置上，rehashidx属性会记录当前正在rehash的索引）到ht[1]上面；
3） 当ht[0]中所有的键值对都迁移到ht[1]之后，释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白的哈希表（rehashidx需要设置为-1，表示rehash执行完毕），为下一次rehash做准备。
7.渐进式的rehash
7.1 步骤
哈希表的rehash操作不是一次性、集中式地完成的，而是分多次、渐进式地完成。
原因在于，如果ht[0]只有两三个或者很少的键值对，那么可以在瞬间就将这些键值对全部rehash到ht[1]；但是，如果哈希表里保存的键值对是四百万、四千万甚至四亿个，那么要一次性将这些键值对全部rehash到ht[1]的话，庞大的计算量可能会导致服务器在一段时间内停止服务。
因此，为了避免rehash对服务器性能造成影响，服务器不是一次性将ht[0]里面的所有键值对全部rehash到ht[1]，而是分多次、渐进式地将ht[0]里面的键值对慢慢得rehash到ht[1]。
渐进式rehash的步骤如下：
1） 为字典ht[1]哈希表分配空间，让字典同时持有ht[0]和ht[1]两个哈希表，ht[1]的大小算法见上一节；
2） 在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始；
3） 在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，除了执行制定的操作外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash完成后，rehashidx属性的值加一；
4） 随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash到ht[1]，这时会将rehashidx属性的值设置为-1，表示rehash操作已经完成。
渐进式rehash的好处在于它采取分而治之的方法，将rehash所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash带来的庞大计算量。
虽然redis实现了在读写操作时，辅助服务器进行渐进式rehash操作，但是如果服务器比较空闲，redis数据库将很长时间内都一直使用两个哈希表。所以在redis周期函数中，如果发现有字典正在进行渐进式rehash操作，则会花费1毫秒的时间，帮助一起进行渐进式rehash操作。前提是配置了activerehashing，允许服务器在周期函数中辅助进行渐进式rehash，该参数默认值是1。
7.2 渐进式rehash期间的哈希表操作
在执行渐进式rehash期间，字典会同时使用ht[1]和ht[0]两个哈希表，所以在此期间，查找、删除、更新操作会先在ht[0]上执行，如果没有，就会继续到ht[1]执行。添加操作会在ht[1]上执行，ht[0]上不执行任何添加操作，这一措施保证了ht[0]包含的键值对数量只减不增，并随着rehash的进行最终变成空表。
7.3 渐进式rehash带来的问题
渐进式rehash避免了redis阻塞，可以说非常完美，但是由于在rehash时，需要分配一个新的hash表，在rehash期间，同时有两个hash表在使用，会使得redis内存使用量瞬间突增，在Redis 满容状态下由于Rehash会导致大量Key驱逐。