关于后端:Redis数据结构四之字典和哈希表

本文首发于公众号：Hunter 后端

原文链接：Redis 数据结构四之字典和哈希表

字典在 Redis 中利用相当宽泛，在介绍字典之前，先来介绍一下字典、哈希表、哈希表节点的几个概念。

Redis 中，字典是用哈希表及额定的一些属性实现的，而哈希表则由多个哈希表节点形成，咱们援用根底命令笔记中介绍的哈希命令中的一个例子来做介绍，一个哈希构造如下：

{
    "student":
        {
            "name": "Hunter",
            "number": "00001",
            "rank": 1
        }
}

其中，student: {} 的底层就是一个哈希表

student 下的 {"name": "Hunter"}、{"number": "00001"}、{"rank": 1} 就是组成哈希表的各个哈希表节点

对于 Redis，哈希表和哈希表节点两个数据结构就能够实现咱们对 key-value 数据的操作，然而随着哈希表保留的键值对减少或者缩小，咱们就须要对哈希表进行扩大或者膨胀操作，因而就额定引入了字典构造来做一些额定的辅助操作，具体的实现咱们接下来介绍。

以下是本篇笔记目录：

1. 哈希表
2. 哈希表节点
3. 字典
4. 哈希算法和键抵触
5. rehash
6. 渐进式 rehash

1、哈希表

哈希表构造如下：

typedef struct dictht{
    // 哈希表数组
    dictEntry **table;
    
    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

在下面的构造中，table 属性是一个数组，每个元素都是一个指向哈希表节点的指针

size 属性记录了哈希表的大小，也就是 table 数组的大小

used 属性记录了记录了哈希表目前已有节点（键值对）的数量

sizemask 属性总是等于 size - 1，这个属性和哈希值一起决定一个键该被放到 table 数组中的第几个索引上。

当初咱们模仿一遍往 student 哈希表里插入一条数据 {"name": "Hunter"} 的过程。

首先，假如咱们的哈希表数组的大小为 4（这个大小会随着哈希表里的键值对数量减少或者缩小有主动的调整，也就是 rehash 的操作，咱们前面再介绍），也就是 size 属性为 4，那么 sizemask = 4 - 1 = 3。

咱们要往 table 里插入 {"name": "Hunter"} 这条数据，而哈希表 table 属性有四个长度，应该放在第几个地位呢，就须要应用这个键值对的键，也就是 name 通过哈希函数失去它的哈希值，这个哈希值是一个数值，假如失去的哈希值是 8，那么接下来就须要将 8 与 sizemask 也就是 3 进行 与 操作，失去的后果是 0，那么将这条数据放在 table 数组的索引 0，也就是第一个地位。

至于依据键值对的键获取哈希值应用的哈希函数，Redis 里应用的是 Murmurhash 算法，有趣味的能够去理解一下。

2、哈希表节点

哈希表节点的构造如下：

typedef struct dictEntry{
    // 键
    void *key;
    
    // 值
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    
    // 指向下个哈希表节点，造成链表
    struct dictEntry *next;
} dictEntry;

在这个构造中，key 属性保留着键值对中的键，v 属性则保留着键值对的值，其中值能够是一个指针，或者是一个 uint64_t 整数，也能够是一个 int64_t 整数。

假如咱们还是应用 {"name": "Hunter"} 为例，那么这个 key 就是指向的就是 name，val 指向的是 Hunter。

next 属性则是指向另一个哈希表节点的指针，因为不同的键在通过哈希函数解决之后失去的值在跟 sizemask 进行与操作之后失去的索引地位可能雷同，所以哈希表节点通过链地址法来解决键抵触的问题。

3、字典

字典的构造如下：

typedef struct dict{
    // 类型特定函数
    dictType *type;
    
    // 公有数据
    void *privdata;
    
    // 哈希表
    dictht ht[2];
    
    // rehash 索引
    int rehashidx;
}

type 属性和 privdata 属性是针对不同类型的键值对，为创立多态字典而设置的。

ht 属性则是一个蕴含了两个哈希表的数组，个别状况下只应用 ht[0] 哈希表，ht[1] 只有在 rehash，也就是对哈希表进行进行扩大或者膨胀的时候才会应用。

rehashidx 属性记录了 rehash 目前的进度，如果目前没有进行 rehash 操作，那么它的值就是 -1。

4、哈希算法和键抵触

如何将一个新的键值对插入到哈希表中，这个过程咱们在介绍哈希表的属性的时候就曾经模仿过这个流程了。

当多个键值对通过哈希算法被调配到哈希表的同一个索引上，咱们就称这些键产生了抵触。

为了解决抵触，后面在介绍哈希表节点的构造的时候，介绍了哈希表节点有一个 next 属性，指向的下一个哈希表节点，因而哈希表节点就用应用 next 属性将不同的哈希表节点连接起来。

因为哈希表节点组成的链表没有指向链表表尾的指针，所以为了防止遍历节点到链表尾部，程序会将新节点增加到链表的表头地位，排在其余节点的后面。

5、rehash

后面介绍过，当哈希表保留的键值对数量太多或者太少，会须要对哈希表的大小进行相应的扩大或者膨胀。

用于掂量哈希表的大小与键值对的数量之间的关系有一个计算关系，称为哈希表的负载因子（load factor）。

负载因子的计算公式如下：

load_factor = ht[0].used / ht[0].size

即哈希表已保留的节点数量 / 哈希表大小。

1. 哈希表的扩大与膨胀

当以下条件任意一个被满足时，程序主动开始对哈希表进行 扩大 操作：

• 负载因子大于等于 1，且服务器没有在执行 BGSAVE 或者 BGREWRITEAOF 命令时
• 负载因子大于等于 5，且服务器正在执行 BGSAVE 或者 BGREWRITEAOF 命令时

BGSAVE 和 BGREWRITEAOF 是 Redis 进行长久化操作的两个后盾执行的命令。

当哈希表的负载因子小于 0.1 时，程序主动开始对哈希表执行膨胀操作。

2. rehash 步骤

接下来介绍一下 Redis 的字典构造进行 rehash 的步骤。

1) 首先，须要用到字典构造中的 ht 数组的第二个，也就是 ht[1]，须要为其调配空间。

调配的空间大小取决于是扩大还是膨胀操作，以及 ht[0] 以后蕴含的键值对数量，也就是 ht[0].used 属性的值。

如果是扩大操作，咱们将须要 ht[1] 的空间大小设置为 x，那么 x 的应该是 2 的 n 次方，且是大于等于 ht[0].used * 2 的第一个 2 的 n 次方。

咱们假如以后 ht[0].used 的值为 9，那么大于等于 9 * 2 = 18 的最小的一个 2 的 n 次方的值是 32，也就是 2 的 5 次方，所以咱们要将其 ht[1] 的大小设置为 32，也就是哈希表构造里的 size 属性。

如果是膨胀操作，咱们须要将 ht[1] 的空间大小设置为 x，这个 x 应该是 2 的 n 次方，且是大于等于 ht[0].used 的第一个 2 的 n 次方。

假如 ht[0].used 的值为 9，那么大于等于 9 的最小的 2 的次方的值是 16，也就是 2 的 4 次方。

2) 调配好 ht[1] 的空间之后，将保留在 ht[0] 的所有键值对 rehash 到 ht[1] 上，rehash 的操作就是一一从新计算哈希表节点的键的哈希值和对应的索引值，而后将键值对搁置到 ht[1] 哈希表对应的地位上。

3) 将 ht[0] 上的所有键值对都迁徙到 ht[1] 之后，此时 ht[0] 就变成了空表，开释 ht[0]，将 ht[1] 设置为 ht[0]，并在 ht[1] 新创建一个空哈希表，为下一次 rehash 作筹备。

6、渐进式 rehash

下面的 rehash 的操作并不是一次性、集中式实现的，而是分屡次、渐进式实现的。

因为当 ht[0] 的键值对数量小的时候能够霎时实现，然而当键值对数量很大，比方几百万，几千万个键值对，一次性进行迁徙操作可能导致 Redis 一段时间内进行服务。

因而 rehash 的操作是分屡次、渐进式地将 ht[0] 外面的键值对缓缓地 rehash 到 ht[1]。

以下是其具体步骤：

1. 为 ht[1] 调配空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表
2. 在字典中维持索引计数器变量 rehashidx，将其设置为 0，示意 rehash 工作正式开始
3. 在 rehash 期间，每次对字典进行增加、删除、查找、或者更新操作时，程序除了执行指定的操作，还会顺带将 ht[0] 上对应索引地位上的哈希表节点都 rehash 到 ht[1]
4. 随着字典操作的一直执行，在某个工夫点，ht[0] 的所有键值对都会被 rehash 到 ht[1]，这时候 rehashidx 属性的值设为 -1，示意 rehash 操作曾经实现

在进行渐进式 rehash 的过程中，哈希表节点，也就是键值对会在两个哈希表中散布，所以字典的删除、查找、更新操作会在两个哈希表上进行。

比方如果在字典查找一个键，在 ht[0] 里没有查找到，那么会持续在 ht[1] 里查找。

另外，在渐进式 rehash 期间，新增加到字典的键值对一律会被保留到 ht[1] 外面，ht[0] 则不再进行任何增加操作，这个措施保障了 ht[0] 蕴含的键值对数量只减不增，并随着 rehash 操作的执行最终变成空表。