02-Redis 数据结构之 字典的数据结构

一、Redis 字典结构

内部结构

Redis 字典的结构和 Java 中的 HashMap 有点类似，都是存放键值对，在底层都是使用数组加链表（称为一个哈希表）的形式来实现的，但与 HashMap 不同的是，在 Redis 中，它由两个哈希表组成，它的结构大致如下图所示：

由上图可以看到，它使用两个 hashtable ，姑且称之为 0 号哈希表和 1 号哈希表，每次只会使用 0 号哈希表，那么 1 号哈希表有什么用呢？后面慢慢解释。

复制扩容

如果哈希表为空，即第一次添加元素的时候，需要初始化哈希表，哈希表的大小为 4 ，如下所示：

还有一种情况是，如果哈希表的已有的节点和哈希表的大小的比例超过阈值 dict_force_resize_ratio 即 5 的时候，需要对哈希表进行扩展，

扩展的哈希表大小为已使用节点的2倍，如果哈希表的大小为 4 ，已使用节点数量为24， 则 24/4 > 5 ，就需要对哈希表进行扩展，此时哈希表的大小为 24*2 = 48。

rehash

接下来看下字典的 rehash，字典为什么需要 rehash，随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，如果保存的键值很多，哈希表较小，则哈希表中每一项的链表就会很长，而链表的查找速度较慢，所以为了让哈希表的负载因子（load factor）维持在一个合理的范围之内， 当哈希表保存的键值对数量太多或者太少时， 程序需要对哈希表的大小进行相应的扩展或者收缩。

而在 Redis 的字典扩展或缩小的过程中，是一个渐进式的过程，为什么不是一次性进行操作，而是渐进式的方式？因为如果字典较大，在扩展的时候，需要重新申请空间，再把旧字典的值 copy 到新的字典中取，这是一个 O(n) 的操作，很费时，所有，采用的是渐进式的方式，在字典进行扩展的过程中，还可以进行其他的操作，如添加，查找等。

rehash 的过程就是根据 0 号哈希表的已有节点来计算需要扩展的大小，根据该大小创建 1 号哈希表，再把 0 号哈希表的数据慢慢移动到 1 号哈希表上，rehash 指的是重新计算键的哈希值和索引值， 然后将键值对放置到 ht[1] 哈希表的指定位置上。当移到完成后，再把 1 号哈希表赋给 0 号哈希表，之后清空 1 号哈希表，为下次 rehash 做准备。