字典在Redis中的应用相当广泛，比如Redis的数据库就是使用字典来作为底层实现的，对数据库的增、删、查、改操作也是构建在对字典的操作之上的。

除了用来表示数据库之外，字典还是哈希键的底层实现之一，当一个哈希键包含的键值对比较多，又或者键值对中的元素都比较长的字符串时，Redis就会使用字典 作为i 哈希键的底层实现。

4.1字典的实现

Redis的字典使用哈希表作为底层实现

4.1.1 哈希表

Redis字典所使用的哈希表由dict.h/dictht结构定义：

redis中哈希表的结构定义

4.1.2 哈希表节点

哈希表节点使用dictEntry结构表示

dictEntry结构

next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一起，以此来解决键冲突的问题。

4.1.3 字典

Redis中的字典由dict.h/dict结构表示：

字典结构

ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]函希表进行rehash时使用。

trehashidx，它记录了rehash目前的进度，如果目前没有在进行rehash,那么它的值为-1

dictType结构

4.2 哈希算法

当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对哈希表节点放到哈希表数组的指定索引上面。

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

hash = dict->type->hashFunction(key);;//使用字典设置的哈希函数，计算键key的哈希值

index = hash & dict->ht[x].sizemask;//使用哈希表的sizemask属性和哈希值，计算出索引值，根据情况不同，ht[x]可以是ht[0]或者ht[1]

当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。

MurmurHash算法解释：

MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。

4.3 解决键冲突

Redis的哈希表使用链地址法来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，这就解决了键冲突的问题。程序总是将新节点添加到链表的表头位置，排在其他已有节点的前面。

4.4 rehash

为了让哈希表的负载因子（装填因子）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。扩展和收缩哈希表的工作可以通过执行rehash（重新散列）操作完成。rehash步骤如下：

1）为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（ht[0].used的值）：a.如果执行的是扩展操作，那么ht[1]的大小为第一个大小等于ht[0].used*2的2^n

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

2)将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上

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

哈希表装填因子定义为：α= 填入表中的元素个数 / 哈希表的长度

哈希表的扩展与收缩

程序自动开始对哈希表执行扩展操作的条件：

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

2）服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的负载因子大于等于5

BGSAVE命令：用于在后台异步保存当前数据库的数据到磁盘

BGREWRITEAOF命令：执行一个 AOF文件 重写操作。重写会创建一个当前 AOF 文件的体积优化版本。

4.5 渐进式rehash

为了避免rehash对服务器性能造成影响，服务器不是一次性将ht[0]里面的所有键值对全部rehash到ht[1],而是分多次、渐进式地 将ht[0]里面的键值对漫漫地rehash到ht[1]

渐进式rehash的详细步骤：

1）为ht[1]分配空间，让字典同时持有ht[0]和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执行期间的哈希表操作

字典会同时使用ht[0]和ht[1]两个哈希表，所以渐进式rehash进行期间，字典的删除、查找、更新等操作都会在两个哈希表上进行。另外，在渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作。