第四章 字典

字典是哈希键的底层实现之一，Redis数据库的底层实现也是使用字典。

image.png
image.png

redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

相关的数据结构

哈希表dict的数据结构：

image.png

一个空的哈希表如图所示：

image.png

哈希节点使用dictEntry来表示，每个dictEntry结构都保存着一个键值对：

image.png

包含2个哈希节点的哈希表如图所示：

image.png

字典dict的数据结构如图所示：

image.png

type和privdata属性是针对不同类型的键值对，为创建多态字典而设置的。
type属性是一个指向dictType结构的指针，每个dictType结构保存了一组用于操作特定类型键值对的函数；privdata属性则保存了需要传给那些类型特定函数的可选参数
ht是2个哈希表数组，用于rehash时使用，一般情况下只是用ht[0]。
trehashidx用于表示rehash的进度，如果没有rehash，则为-1。

一个普通状态下的字典结构如图所示：

image.png

当要在字典中插入键值对的时候，先计算key的hash值，再与上sizemask，定位相应的槽位置即可。

哈希冲突

同时，对于哈希表中的键冲突，会采用链地址法的解决方案，但是因为dictEntry节点没有指向链表表尾的指针，因此采用头插法O（1）（感觉HashMap1.7采用头插法也可能是为了插入效率吧）。

rehash

哈希表rehash的时候会使用在ht[1]上进行扩容，然后交换ht[0]和ht[1]。满足以下任意一个条件的时候，程序会自动对哈希表进行扩容操作：

1. 服务器目前没有执行BGSAVE或者BGREWRITEAOF命令，且哈希表负载因子大于等于1
2. 服务器目前正在执行BFSAVE或者BGREWRITEAOF命令，且哈希表负载因子大于等于5
   其中load_factor = ht[0].used / ht[0].size
   当哈希表的负载因子小于0.1的时候，程序胡自动开始对哈希表执行收缩操作。

渐进rehash

rehash的动作并不是一次性集中完成的，而是分多次渐进完成的，通过rehashidx的值可以观察到当前rehash的进度。
在渐进rehash的过程中，字典会同时使用ht[0]和ht[1]两个哈希表，因此渐进rehash进行期间，字典的删除、查找、更新等操作会在2个哈希表上进行。如果要在字典里面查找一个键的话，会现在ht[0]里面找，找不到再在ht[1]里面找。
另外，渐进rehash期间，新添加到字典的键值对一律会被保存到ht[1]里面，来保证ht[0]包含的键值对数量只减不增，并随着rehash操作的执行而最终变成空表。

image.png