Redi哈希hash底层原理

先明确一个概念叫dict，又称字典(dictionary)或映射(map)，是集合的一种；这种集合中每个元素都是KV键值对。
字典dict 在 Redis 中的应用广泛，使用频率可以说和 SDS 以及双端链表不相上下，基本上各个功能模块都有用到字典的地方。
其中，字典dict的主要用途有以下两个：

实现数据库键空间（key space）；
用作 hash 键的底层实现之一；
这里我们重点讨论 hash 键的底层实现。

Redis 的 hash 键使用以下两种数据结构作为底层实现:

压缩列表ziplist ；
字典dict；
因为压缩列表比字典更节省内存，所以程序在创建新 Hash 键时，默认使用压缩列表作为底层实现，当有需要时，才会将底层实现从压缩列表转换到字典。
ziplist 是为 Redis 节约内存而开发的、非常节省内存的双向链表。

压缩链表转成字典(ziplist->dict)的条件

同时满足以下两个条件，hash 键才会使用ziplist：

key和value 长度都小于64
键值对数小于512
以上两个条件可以在Reids配置文件中修改hash-max-ziplist-value选项和hash-max-ziplist-entries选项。

dict的结构

/*
* 字典
*
* 每个字典使用两个哈希表，用于实现渐进式 rehash
*/typedef struct dict {

    // 特定于类型的处理函数
    dictType *type;

    // 类型处理函数的私有数据
    void *privdata;

    // 哈希表（2 个）
    dictht ht[2];

    // 记录 rehash 进度的标志，值为 -1 表示 rehash 未进行
    int rehashidx;

    // 当前正在运作的安全迭代器数量
    int iterators;

} dict;

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;

结合上面的代码，可以很清楚地看出dict的结构。一个dict由如下若干项组成：

dictType *type;一个指向dictType结构的指针（type）。它通过自定义的方式使得dict的key和value能够存储任何类型的数据。
void *privdata;一个私有数据指针（privdata）。由调用者在创建dict的时候传进来。
dictht ht[2];两个哈希表（ht[2]）。只有在rehash的过程中，ht[0]和ht[1]才都有效。而在平常情况下，只有ht[0]有效，ht[1]里面没有任何数据。上图表示的就是rehash进行到中间某一步时的情况。
int rehashidx;当前rehash索引（rehashidx）。如果rehashidx = -1，表示当前没有在rehash过程中；否则，表示当前正在进行rehash，且它的值记录了当前rehash进行到哪一步了。
int iterators;当前正在进行遍历的iterator的个数。这不是我们现在讨论的重点，暂时忽略。

dictht(dict hash table)哈希表结构

/*
* 哈希表
*/typedef struct dictht {

    // 哈希表节点指针数组（俗称桶，bucket）
    dictEntry **table;

    // 指针数组的大小
    unsigned long size;

    // 指针数组的长度掩码，用于计算索引值
    unsigned long sizemask;

    // 哈希表现有的节点数量
    unsigned long used;

} dictht;

dictht 定义一个哈希表的结构，包括以下部分：

一个dictEntry指针数组（table）。key的哈希值最终映射到这个数组的某个位置上（对应一个bucket）。如果多个key映射到同一个位置，就发生了冲突，那么就拉出一个dictEntry链表。
size：标识dictEntry指针数组的长度。它总是2的指数次幂。
sizemask：用于将哈希值映射到table的位置索引。它的值等于(size-1)，比如7, 15, 31, 63，等等，也就是用二进制表示的各个bit全1的数字。每个key先经过hashFunction计算得到一个哈希值，然后计算(哈希值 & sizemask)得到在table上的位置。相当于计算取余(哈希值 % size)。
used：记录dict中现有的数据个数。它与size的比值就是装载因子。这个比值越大，哈希值冲突概率越高。

dictEntry的结构

/*
* 哈希表节点
*/typedef struct dictEntry {
    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 链往后继节点
    struct dictEntry *next;
} dictEntry;

dictEntry结构中包含k, v和指向链表下一项的next指针。k是void指针，这意味着它可以指向任何类型。v是个union，当它的值是uint64_t、int64_t或double类型时，就不再需要额外的存储，这有利于减少内存碎片。当然，v也可以是void指针，以便能存储任何类型的数据。
next 指向另一个 dictEntry 结构，多个 dictEntry 可以通过 next 指针串连成链表，从这里可以看出， dictht 使用链地址法来处理键碰撞：当多个不同的键拥有相同的哈希值时，哈希表用一个链表将这些键连接起来。

dictht和dictEntry组合

如果再加上之前列出的 dict 类型，那么整个字典结构可以表示如下：

dict的创建（dictCreate）

dictCreate为dict的数据结构分配空间并为各个变量赋初值。其中两个哈希表ht[0]和ht[1]起始都没有分配空间，table指针都赋为NULL。这意味着要等第一个数据插入时才会真正分配空间。

添加新键值对到字典(dictAdd)

根据字典所处的状态，将给定的键值对添加到字典可能会引起一系列复杂的操作：

如果字典为未初始化（即字典的 0 号哈希表的 table 属性为空），则程序需要对 0 号哈希表进行初始化；
如果在插入时发生了键碰撞，则程序需要处理碰撞；
如果插入新元素，使得字典满足了 rehash 条件，则需要启动相应的 rehash 程序；
当程序处理完以上三种情况之后，新的键值对才会被真正地添加到字典上。

添加新键值对时发生碰撞

在哈希表实现中，当两个不同的键拥有相同的哈希值时，称这两个键发生碰撞（collision），而哈希表实现必须想办法对碰撞进行处理。
字典哈希表所使用的碰撞解决方法被称之为链地址法：这种方法使用链表将多个哈希值相同的节点串连在一起，从而解决冲突问题。
假设现在有一个带有三个节点的哈希表，如下图：

对于一个新的键值对 key4 和 value4 ，如果 key4 的哈希值和 key1 的哈希值相同，那么它们将在哈希表的 0 号索引上发生碰撞。
通过将 key4-value4 和 key1-value1 两个键值对用链表连接起来，就可以解决碰撞的问题：

添加新键值对时触发了 rehash

对于使用链地址法来解决碰撞问题的哈希表 dictht 来说，哈希表的性能取决于大小（size属性）与保存节点数量（used属性）之间的比率：
哈希表的大小与节点数量，比率在 1:1 时，哈希表的性能最好；
如果节点数量比哈希表的大小要大很多的话，那么哈希表就会退化成多个链表，哈希表本身的性能优势便不复存在；
举个例子，下面这个哈希表，平均每次失败查找只需要访问 1 个节点（非空节点访问 2 次，空节点访问 1 次）：

而下面这个哈希表，平均每次失败查找需要访问 5 个节点：

为了在字典的键值对不断增多的情况下保持良好的性能，字典需要对所使用的哈希表（ht[0]）进行 rehash 操作：在不修改任何键值对的情况下，对哈希表进行扩容，尽量将比率维持在 1:1 左右。
dictAdd 在每次向字典添加新键值对之前，都会对哈希表 ht[0] 进行检查，对于 ht[0] 的 size 和 used 属性，如果它们之间的比率 ratio = used / size 满足以下任何一个条件的话，rehash 过程就会被触发：

自然 rehash ： ratio >= 1 ，且变量 dict_can_resize 为true。
强制 rehash ： ratio 大于变量 dict_force_resize_ratio （目前版本中， dict_force_resize_ratio 的值为 5 ）。

Redis dictht的负载因子

我们知道当HashMap中由于Hash冲突（负载因子）超过某个阈值时，出于链表性能的考虑、会进行扩容，Redis dict也是一样。
一个dictht 哈希表里，核心就是一个dictEntry数组，同时用size记录了数组大小，用used记录了所有记录数。
dictht的负载因子，就是used与size的比值，也称装载因子（load factor）。这个比值越大，哈希值冲突概率越高。当比值[默认]超过5，会强制进行rehash。

Rehash 执行过程

字典的 rehash 操作实际上就是执行以下任务：

创建一个比 ht[0]->table 更大的 ht[1]->table ；
将 ht[0]->table 中的所有键值对迁移到 ht[1]->table ；
将原有 ht[0] 的数据清空，并将 ht[1] 替换为新的 ht[0] ；
经过以上步骤之后，程序就在不改变原有键值对数据的基础上，增大了哈希表的大小。
dict的rehash 本质就是扩容，就是将数组+链表结构中的数组扩容；
这个过程，需要开辟一个更大空间的数组，将老数组中每个非空索引的bucket，搬运到新数组；搬运完成后再释放老数组的空间。

1. 开始 rehash

这个阶段有两个事情要做：

设置字典的 rehashidx 为 0 ，标识着 rehash 的开始；
为 ht[1]->table 分配空间，大小至少为 ht[0]->used 的两倍；
这时的字典是这个样子：

2. Rehash 进行中

在这个阶段， ht[0]->table 的节点会被逐渐迁移到 ht[1]->table ，因为 rehash 是分多次进行的（细节在下一节解释），字典的 rehashidx 变量会记录 rehash 进行到 ht[0] 的哪个索引位置上。
注意除了节点的移动外，字典的 rehashidx 、 ht[0]->used 和 ht[1]->used 三个属性也产生了变化。

3. 节点迁移完毕

到了这个阶段，所有的节点都已经从 ht[0] 迁移到 ht[1] 了：

4. Rehash 完毕

在 rehash 的最后阶段，程序会执行以下工作：

释放 ht[0] 的空间；
用 ht[1] 来代替 ht[0] ，使原来的 ht[1] 成为新的 ht[0] ；
创建一个新的空哈希表，并将它设置为 ht[1] ；
将字典的 rehashidx 属性设置为 -1 ，标识 rehash 已停止；
以下是字典 rehash 完毕之后的样子：

增量/渐进式rehash

rehash的过程，会使用两个哈希表，创建了一个更大空间的ht[1]，此时会造成内存陡增；
rehash的过程，可能涉及大量KV键值对dictEntry的搬运，耗时较长；
如果这个 rehash 过程必须将所有键值对迁移完毕之后才将结果返回给用户，这样的处理方式将不满足Redis高效响应的特性。
rehash会产生的问题，主要层面就是内存占用陡增、和处理耗时长的问题，基于这两点，还会带来其他影响。
为了解决这些问题， Redis 使用了incremental rehashing，是一种增量/渐进式的 rehash 方式：通过将 rehash 分散到多个步骤中进行，从而避免了集中式的计算/节点迁移。
dictAdd 添加键值对到dict，检查到需要进行rehash时，会将dict.rehashidx 设置为 0 ，标识着 rehash 的开始；
后续请求，在执行add、delete、find操作时，都会判断dict是否正在rehash，如果是，就执行_dictRehashStep()函数，进行增量rehash。
每次执行 _dictRehashStep ，会将ht[0]->table 哈希表第一个不为空的索引上的所有节点就会全部迁移到 ht[1]->table 。
也就是在某次dictAdd 添加键值对时，触发了rehash；后续add、delete、find命令在执行前都会检查，如果dict正在rehash，就先不急去执行自己的命令，先去帮忙搬运一个bucket；
搬运完一个bucket，再执行add、delete、find命令原有处理逻辑。

下面我们通过dict的查找（dictFind）来看渐进式rehash过程；

dict的查找（dictFind）

如果当前正在进行rehash，那么将rehash过程向前推进一步（即调用_dictRehashStep）。实际上，除了查找，插入和删除也都会触发这一动作。这就将rehash过程分散到各个查找、插入和删除操作中去了，而不是集中在某一个操作中一次性做完。
计算key的哈希值（调用dictHashKey，里面的实现会调用前面提到的hashFunction）。
先在第一个哈希表ht[0]上进行查找。在table数组上定位到哈希值对应的位置（如前所述，通过哈希值与sizemask进行按位与），然后在对应的dictEntry链表上进行查找。查找的时候需要对key进行比较，这时候调用dictCompareKeys，它里面的实现会调用到前面提到的keyCompare。如果找到就返回该项。否则，进行下一步。
判断当前是否在rehash，如果没有，那么在ht[0]上的查找结果就是最终结果（没找到，返回NULL）。否则，在ht[1]上进行查找（过程与上一步相同）。

dictAdd、dictDelete、dictFind在rehash过程中的特殊性

在哈希表进行 rehash 时，字典还会采取一些特别的措施，确保 rehash 顺利、正确地进行：

因为在 rehash 时，字典会同时使用两个哈希表，所以在这期间的所有查找dictFind、删除dictDelete等操作，除了在 ht[0] 上进行，还需要在 ht[1] 上进行。
在执行添加操作dictAdd时，新的节点会直接添加到 ht[1] 而不是 ht[0] ，这样保证 ht[0] 的节点数量在整个 rehash 过程中都只减不增。

dict的缩容

上面关于 rehash 的章节描述了通过 rehash 对字典进行扩展（expand）的情况，如果哈希表的可用节点数比已用节点数大很多的话，那么也可以通过对哈希表进行 rehash 来收缩（shrink）字典。
收缩 rehash 和上面展示的扩展 rehash 的操作几乎一样，执行以下步骤：

创建一个比 ht[0]->table 小的 ht[1]->table ；
将 ht[0]->table 中的所有键值对迁移到 ht[1]->table ；
将原有 ht[0] 的数据清空，并将 ht[1] 替换为新的 ht[0] ；

小结

Redis的dict最显著的一个特点，就在于它的rehash。它采用了一种称为增量式（incremental rehashing）的rehash方法，在需要扩容时避免一次性对所有key进行rehash，而是将rehash操作分散到对于dict的各个增删改查的操作中去。
这种方法能做到每次只对一小部分key进行rehash，而每次rehash之间不影响dict的操作。dict之所以这样设计，是为了避免rehash期间单个请求的响应时间剧烈增加，这与前面提到的“快速响应时间”的设计原则是相符的。

Redis的dict也是使用数组+链表实现；
当冲突增加、链表增长，也是采用rehash(数组扩容)来将链表变短；
dict数组扩容，也是按2的指数次幂，使用位运算，替代求余操作，计算更快；
渐进式rehash，其实是辅助式的；不是让触发rehash的一个人搬运完所有dictEntry，而是让后来者一起参与搬运。