Redis底层数据结构-Dict

1. Dict基本结构

---

Redis的键与值的映射关系是通过Dict来实现的。

Dict是由三部分组成，分别是哈希表（DictHashTable），哈希节点（DictEntry），字典（Dict）

哈希表结构如下图所示：由于会发生哈希冲突，所以entry个数可能会大于size
size总是2的n次方

哈希节点的结构如下图所示：

当我们向Dict添加键值对时，Redis首先根据key计算出hash值（h），然后利用h&sizemask（其实就是h对数组长度取余）计算元素应该存储到数组中哪个索引位置

建立一个哈希表，以及哈希节点，数组【1】中存入的是dictEntry的地址

如果遇到哈希冲突之后，就会进行头插法将新插入的节点放入首节点位置（因为新放入的数据预计会在较近的时间被访问，其次头插法的时间复杂度低）

dictEntry中的key和value大部分都是指针，指向String类型的对象

Dict（字典）的结构如下图所示：核心是dictht ht【2】用于在rehash时

所以整体Dict结构如下图所示：

2. Dict渐进式rehash

---

Dict中的hashtable就是数组结合单向链表的表现，当集合中元素较多时，必然会导致哈希冲突变多，链表过长，则查询效率大大降低。

Dict在每次新增键值对时都会检查负载因子（LoadFactor=used/size），满足以下两种情况就会出发哈希表扩容：

• 哈希表的LoadFactor>=1，并且服务器并没有执行BGSAVE或者BGREWRITEAOF等后台进程
• 哈希表的LoadFactor>=5；
  Dict除了扩容以外，每次删除元素时，也会对负载因子做检查，当LoadFactor<0.1时&&size>4，会做哈希表收缩

Dict的rehash并不是一次性完成的，如果Dict中包含数百万的entry，要在依次rehash完成，极有可能导致主线程阻塞。因此Dict的rehash是分多次，渐进式的完成，因此称为渐进式rehash，流程如下：

1. 计算新hash表的size，值取决于当前要做的是扩容还是收缩

• 如果是扩容，则新size为第一个大于等于dict.ht[0].used+1的2^n
• 如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n（不得小于4）

2. 按照新的size申请内存空间，创建dictht，并赋值给dict.ht[1]
3. 设置dict.rehashidx=0，标示开始rehash
4. 每次执行新增，查询，修改，删除操作时（也就是说每次访问dict时执行一次rehash），都检查一下dict.rehashidx是否大于-1，如果是，则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1]，并且将rehashidx++，直到dict.ht[0]的所有数据都rehash到dict.ht[1]
5. 将dict.ht[1]赋值给dict.ht[0],给dict.ht[1]初始化为空的哈希表，释放原来的dict.ht[0]
6. 将rehashidx赋值为-1，代表rehash结束
7. 在rehash过程中，新增操作，直接写入ht[1]，查询，修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行，这样可以确保ht[0]的数据只减不增，随着rehash最终为空