5）深度解密 Redis 的哈希（Hash）
楔子
下面来解密 Redis 的哈希，整篇文章分为三个部分。
Redis 哈希的相关命令；
Redis 哈希的应用场景；
Redis 哈希的实现原理；
Redis 哈希的相关命令
hset key field1 value1 field2 value2···：设置键值对，可同时设置多个
这里的键值对指的是 field、value，而命令中的 key 指的是哈希表的名称。
# 返回 3 表示成功设置 3 个键值对
127.0.0.1:6379> hset girl name satori age 16 gender female
(integer) 3
127.0.0.1:6379> hget key field：获取 hash 中 field 对应的 value
127.0.0.1:6379> hget girl name
"satori"
127.0.0.1:6379> hget girl age
"16"
127.0.0.1:6379> hgetall key：获取 hash 中所有的键值对
127.0.0.1:6379> hgetall girl
1) "name"
2) "satori"
3) "age"
4) "16"
5) "gender"
6) "female"
127.0.0.1:6379>
hlen key：获取 hash 中键值对的个数
127.0.0.1:6379> hlen girl
(integer) 3
127.0.0.1:6379> hexists key field：判断 hash 中是否存在指定的 field
127.0.0.1:6379> hexists girl name
(integer) 1 # 存在返回 1
127.0.0.1:6379> hexists girl where
(integer) 0 # 不存在返回 0
127.0.0.1:6379> hkeys/hvals key：获取 hash 中所有的 field 和所有的 value
127.0.0.1:6379> hkeys girl
1) "name"
2) "age"
3) "gender"
127.0.0.1:6379> hvals girl
1) "satori"
2) "16"
3) "female"
127.0.0.1:6379> hincrby key field number：将 hash 中字段 field 对应的值自增 number，number 必须指定，显然 field 对应的值要能解析成整型
127.0.0.1:6379> hincrby girl age 3
(integer) 19 # 返回增加之后的值
127.0.0.1:6379> hincrby girl age -3
(integer) 16 # 可以为正、可以为负
127.0.0.1:6379> hsetnx key field1 value1：每次只能设置一个键值对，不存在则设置，存在则无效
127.0.0.1:6379> hsetnx girl name koishi
(integer) 0 # name 存在，所以设置失败
127.0.0.1:6379> hget girl name
"satori" # 还是原来的结果
127.0.0.1:6379> hsetnx girl length 156
(integer) 1 # 设置成功
127.0.0.1:6379> hget girl length
"156"
127.0.0.1:6379> hdel key field1 field2 ···：删除 hash 中的键，当然键没了，整个键值对就没了
# 返回有效删除的键值对的个数
127.0.0.1:6379> hdel girl name age xxx
(integer) 2
127.0.0.1:6379> hget girl name
(nil)
127.0.0.1:6379> hget girl age
(nil)
127.0.0.1:6379> 以上就是 Redis 哈希的一些基础操作。
Redis 哈希的应用场景
哈希表的应用场景就很广泛了，比如：
1）商品购物车，购物车非常适合用哈希表示，使用人员唯一编号作为 key（哈希表的名称），哈希表本身则负责存储商品的 id 和数量等信息，比如：
hset uid_124 product_id p_305 count 20注意：我们说 Redis 所有的 key 都存在一个哈希表中，而这里的 value 也是一个哈希表。假设当前还有一个 key，名为 name，值为字符串 satori，那么转成 JSON 之后，整体结构就类似下面这样：
{
"uid_124": {"product_id": "p_305",
"count": 20},
"name": "satori"
}uid_124 和 name 都位于全局的哈希表中，因为 Redis 的键值对都是采用哈希表存储的。而 name 对应的 value 是一个普通的字符串，uid_124 对应的 value 又是一个哈希表，因此这背后的结构要理清楚。
2）存储用户的属性信息，使用人员唯一编号作为 key，哈希表存储属性字段和对应的值，比如姓名、年龄、薪资、工作年限等等；
3）存储文章详情页，文章的唯一编号作为 key，哈希表存储点赞数、阅读量、收藏数等等。
对于这种映射型的结构，使用哈希表再合适不过了。
Redis 哈希的实现原理
前面在说压缩列表的时候，提到过 Redis 的 Hash 对象的底层实现之一是压缩列表（现在已将压缩列表替换成 listpack），而另一个底层实现则是哈希表。
哈希表是一种保存键值对（key-value）的数据结构，当中的每一个 key 都是独一无二的，程序可以根据 key 查找到与之关联的 value，或者通过 key 来更新 value，又或者根据 key 来删除整个 key-value 等等。
哈希表优点在于，它能以 O(1) 的复杂度快速查询数据。至于原因我们在前面已经解释过了，哈希表可以理解为一个数组，在存储的时候会通过 Hash 函数对 key 进行运算，计算出桶的编号（也可以理解为索引），然后将元素存进去。至于在根据 key 获取元素的时候，也是同样的道理，会先对 key 进行哈希运算找到桶的位置，然后将里面的元素取出来。
当然上面说的是理想情况，因为哈希运算是随机的，有可能不同的 key 被映射到同一个桶，此时我们就说出现了哈希冲突。而常见的解决哈希冲突的方式有两种，分别是「分离链接法（separate chaining）」和「开放寻址法（open addressing）」。
「分离链接法」是为每一个哈希桶维护一个链表，出现冲突时，所有哈希到同一个桶的元素通过一个链表连接起来；
「开放寻址法」是当哈希到某一个桶的时候，发现这个桶里面已经有其它元素了（出现冲突），那么会执行探测函数进行二次探查，重新找一个桶。而探测函数也有多种，比如线性探测、平方探测、迭代探测等等；
那么 Redis 采用的是哪一种做法呢？答案是「分离链接法」，在不扩容哈希表的前提下，将具有相同哈希值的数据串起来，形成链表，以便这些数据在表中仍然可以被查询到。好了，那么接下来就看看 Redis 哈希表的结构设计。
Redis 哈希的结构设计
Redis 的哈希表结构如下：
typedef struct dictht {
// 数组的首地址，哈希表是通过数组实现的
// 而数组中的每个元素都是一个 dictEntry *
// 所以这里 table 的类型是 dictEntry **
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值
unsigned long sizemask;
// 该哈希表已有的节点数量
unsigned long used;
} dictht;哈希函数在映射的时候是随机的，因此元素越多就越可能出现哈希冲突，虽然映射到同一个桶的元素可以通过链表组织起来，但这个链表不可能无限长，否则就失去了哈希表的意义。
因此为避免这一点，当元素过多的时候，就需要对哈希表进行扩容，申请一个新的哈希表，并将老哈希表中的元素拷贝过去。并且在申请新的哈希表的时候，可以适当将空间申请的大一些，目的就是为了减少哈希冲突的频率。
所以上面的 size 成员指的就是哈希表的空间大小，或者说整个数组的长度，而 used 成员指的是哈希表中已存储的节点数量，当 used 快超过 size 的时候就意味着哈希表要扩容了。
Python 的字典在底层也是通过哈希表实现的，不过 Python 的哈希表在出现冲突时使用的是「开放寻址法」，并且当 used 数量达到哈希表空间大小的三分之二的时候，就会发生扩容。
我们再用一张图来描述一下 Redis Hash 的结构：
整个结构还是很好理解的，这里需要注意 dictEntry，里面还有一个 next 字段，用于指向下一个 dictEntry。因为 Redis 要通过「分离链接法」解决哈希冲突的问题，所以需要维护一个链表，也就是所谓的「链式哈希」。
然后再来看一下 dictEntry，我们知道它是一个结构体，但是 value 字段和我们想象的有些不一样。
typedef struct dictEntry {
// 指向键值对中的键
void *key;
// 指向键值对中的值
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
// 指向下一个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;我们看到 value 不单纯是一个指针，而是一个共同体，因此 value 可以是一个指向某个对象的指针，也可以是一个无符号的 64 位整数、有符号的 64 位整数或 double 类型的浮点数。
这么做的好处就是节省内存，当「值」是整数或浮点数时，就可以将值的数据内嵌在 dictEntry 结构体里，无需再用一个指针指向实际的对象，从而节省了内存空间。
哈希冲突与链式哈希
这里再来聊一聊哈希冲突，最开始的时候说过，哈希表实际上就是一个数组，数组中的每一个存储单元是一个哈希桶（也可以称之为哈希槽），桶的编号和索引保持一致。写入一个键值对时，会对 key 进行哈希映射得到桶的编号，然后将键值对（dictEntry *）写入对应的桶中。
哈希映射，可以简单理解为先对 key 进行哈希运算，得到一个很大的数，然后再对数组的长度进行取模运算（一般会优化成按位与），即可得到一个合法的索引，整个过程就称为哈希映射。因此在实现哈希表的时候，如何设计一个好的哈希函数是非常关键的，它能直接影响哈希表的效率。
而哈希冲突则是两个不同的 key 最终被映射到同一个桶中，举个例子，有一个可以存放 5 个桶的哈希表，key1 和 key3 都被映射到了 2 号哈希桶。
此时 key1 和 key3 被映射到了相同的哈希桶中，而当有两个及以上的 key 被分配到了同一个哈希桶时，这些 key 就发生了冲突。而解决哈希冲突，我们说有两种做法，Redis 采用了「链式哈希」，即「分离链接法」。
不过链式哈希局限性也很明显，随着链表长度的增加，查询这一位置上的数据的耗时就会增加，毕竟链表查询的时间复杂度是 O(n)。而要想解决这一问题，就需要进行 rehash，也就是对哈希表的大小进行扩展，接下来就看看 Redis 是如何实现 rehash 的。
rehash
我们说 Redis 使用 dictht 结构体表示哈希表，不过在实际使用时，Redis 会用两个哈希表。
// 在 dictht 的基础上又定义了一个结构体
typedef struct dict {
//...
//两个哈希表，交替使用
//用于 rehash 操作
dictht ht[2];
//哈希表是否在进行 rehash 的标识
//-1 表示没有进行 rehash
long rehashidx;
//...
} dict;之所以定义 2 个哈希表，是因为进行 rehash 的时候，需要用上 2 个哈希表。
在正常服务请求阶段，插入的数据都会写入到「哈希表 1」，此时的「哈希表 2」 并没有被分配空间。但随着数据逐步增多，触发了 rehash 操作，「哈希表 2」就闪亮登场了，整个过程分为三步：
给「哈希表 2」 分配空间，一般会比「哈希表 1」 大 2 倍；
将「哈希表 1」的数据迁移到「哈希表 2」 中；
迁移完成后，「哈希表 1」的空间会被释放，并把「哈希表 2」 设置为「哈希表 1」，然后在「哈希表 2」 新创建一个空白的哈希表，为下次 rehash 做准备；
我们用一张图展示一下整个过程：
过程不难理解，就是哈希表 1 满了之后，为哈希表 2 申请更大的空间，然后将哈希表 1 的元素拷贝过去，再释放哈希表 1，最后将哈希表 2 和哈希表 1 交换位置。之后容量再满了的话，则继续重复此过程，周而复始。
我们查看一下源代码：
int dictExpand(dict *d, unsigned long size)
{
/* 需要的容量小于当前容量，则不需要扩容 */
if (dictIsRehashing(d) || d->ht[0].used > size)
return DICT_ERR;
dictht n;
// 重新计算扩容后的值
unsigned long realsize = _dictNextPower(size);
/* 如果新的扩容大小等于当前容量，不需要扩容 */
if (realsize == d->ht[0].size) return DICT_ERR;
/* 分配一个新的哈希表，并将所有指针初始化为 NULL */
n.size = realsize;
n.sizemask = realsize-1;
n.table = zcalloc(realsize*sizeof(dictEntry*));
n.used = 0;
if (d->ht[0].table == NULL) {
// 第一次初始化
d->ht[0] = n;
return DICT_OK;
}
// 把增量输入放入新 ht[1] 中
d->ht[1] = n;
// 设置为 0（默认值 -1），表示需要进行 rehash
d->rehashidx = 0;
return DICT_OK;
}从以上源码可以看出，如果需要扩容则会申请一个新的内存地址赋值给 ht[1]，并把 dict 对象的 rehashidx 设置为 0，表示之后需要进行 rehash 操作。
另外当哈希表的使用容量不足总空间的 10% 时就会触发缩容，Redis 在缩容时也会把 rehashidx 设置为 0，表示之后需要进行 rehash 操作。
不过这个过程看起来简单，但其实存在性能隐患。如果「哈希表 1」的数据量非常大，那么在迁移至「哈希表 2」的时候，因为会涉及大量的数据拷贝，此时可能会对 Redis 造成阻塞，无法服务其他请求。
那么要怎么解决呢？于是 Redis 采用了渐进式 rehash。
渐进式 rehash
为了避免 rehash 在数据迁移过程中，因拷贝数据而影响 Redis 性能，所以 Redis 采用了渐进式 rehash。核心思想就是数据迁移的工作不再是一次性完成，而是分多次迁移。整个过程如下：
给「哈希表 2」 分配空间；
在 rehash 期间，每次哈希表进行新增、删除、或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将「哈希表 1」中索引位置上的 key-value 迁移到「哈希表 2」。当然这是分批次完成的，客户端对哈希表每发起一次请求，就迁移一部分；
随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间点，会把「哈希表 1」的所有 key-value 都迁移到「哈希表 2」，从而完成 rehash 操作；
这样就巧妙地把一次性大量数据迁移工作的开销，分摊到了多次处理请求的过程中，避免了一次性 rehash 的耗时操作。但是在进行渐进式 rehash 的过程中，会有两个哈希表，所以在此期间，哈希表元素的删除、查找、更新等操作都会在这两个哈希表进行。
比如查找一个 key 的话，会先在「哈希表 1」里面查找，如果没找到，就会继续到哈希表 2 里面查找。另外，在渐进式 rehash 期间，新增一个 key-value 时，会被保存到「哈希表 2」里面，而「哈希表 1」 则不再进行任何添加操作。这样保证了「哈希表 1 」的 key-value 数量只会减少，随着 rehash 操作的完成，最终「哈希表 1」就会变成空表。
一旦 rehash 完成，就会将 rehashidx 设置为 -1，表示 rehash 结束。
什么时候进行 rehash？
再来看看最后一个问题，什么时候进行 rehash 呢？看一下源代码，位于 dict.c 中。
//如果哈希表为空，将哈希表扩容为初始大小
if (d->ht[0].size == 0)
return dictExpand(d, DICT_HT_INITIAL_SIZE);
//如果哈希表承载的元素个数超过其当前大小，并且可以进行扩容
//或者哈希表承载的元素个数是当前大小的5倍
if (d->ht[0].used >= d->ht[0].size &&(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
return dictExpand(d, d->ht[0].used*2);
}所以扩容有三个条件，满足任何一个即可扩容：
ht[0] 的大小为 0；
ht[0].used > ht[0].size，即哈希表内的元素数量已经超过哈希表的大小，并且可以扩容；
ht[0].used 大于等于 ht[0].size 的 5 倍；
对于条件一来说，此时哈希表是空的，所以 Redis 就需要将表空间设置为初始大小，而这是初始化的工作，并不属于 rehash 操作。
而条件二和条件三就对应了 rehash 的场景，因为在这两个条件中，都比较了哈希表当前承载的元素个数（d->ht[0].used）和哈希表当前设定的大小（d->ht[0].size），这两个值的比值一般称为负载因子（load factor）。
像 Java 的 HashMap，Go 的 map，都有负载因子这一概念。
也就是说，Redis 判断是否进行 rehash 的条件，就是看 load factor 是否大于等于 1、或者是否大于 5。
当 load factor 大于 5 时，就表明哈希表已经过载很严重了，需要立刻扩容。而当 load factor 大于等于 1 时，Redis 还会再判断 dict_can_resize 这个变量值，查看当前是否可以进行扩容。
而 dict_can_resize 在源码中是通过以下两个函数设置的，它们的作用分别是启用和禁止哈希表执行 rehash 功能，如下所示：
void dictEnableResize(void) {
dict_can_resize = 1;
}
void dictDisableResize(void) {
dict_can_resize = 0;
}然后这两个函数的调用又被封装在了 updateDictResizePolicy 函数中。
updateDictResizePolicy 函数用来启用或禁用 rehash 扩容功能，这个函数调用 dictEnableResize 函数启用扩容功能的条件是：当前没有 RDB 子进程，并且也没有 AOF 子进程，这就对应了 Redis 没有执行 RDB 快照和没有进行 AOF 重写的场景。
void updateDictResizePolicy(void) {
if (server.rdb_child_pid == -1 &&
server.aof_child_pid == -1)
dictEnableResize();
else
dictDisableResize();
}所以每次新增键值对的时候，都会判断是否能够进行 rehash 操作：
当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令，也就是没有执行 RDB 快照和没有进行 AOF 重写的时候，就会进行 rehash 操作；
当负载因子大于等于 5 时，此时说明哈希冲突非常严重了，不管有没有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作；
小结
Redis 中的 Hash 类型底层使用了哈希表，并且当元素冲突时采用「链式哈希」。如果哈希冲突严重、需要扩容时，会开辟一个新的哈希表，翻倍扩容，并采用「渐进式 rehash」的方式迁移数据。
而所谓所谓「渐进式 rehash」就是指，把大块数据迁移的开销，平摊到多次小的操作中，目的是降低主线程的性能影响。
Redis 里面凡是需要 O(1) 时间获取 k-v 数据的场景，都使用了哈希表这个数据结构，也就是说哈希表是 Redis 重中之重的「底层数据结构」。
Redis 也为哈希表封装好了友好的「增删改查」API，并在适当时机「自动扩容、缩容」，这给上层数据类型（Hash/Set）、全局哈希表的实现提供了非常大的便利。
「全局哈希表」在触发渐进式 rehash 的情况有 2 个：
增删改查哈希表时：每次迁移 1 个哈希桶；
定时 rehash：如果哈希表一直没有操作，无法渐进式迁移数据，那主线程会默认每间隔 100ms 执行一次迁移操作。这里一次会以 100 个桶为基本单位迁移数据，并限制如果一次操作耗时超时 1ms 就结束本次任务，待下次再触发迁移；
注意：定时 rehash 只会迁移全局哈希表中的数据，不会定时迁移 Hash/Set 下的哈希表的数据，这些哈希表只会在操作数据时做实时的渐进式 rehash。
哈希表在负载因子超过 1 时，会触发 rehash，但如果此时 Redis正在执行 RDB快照或 AOF rewrite，为避免父进程大量写时复制，会暂时关闭触发 rehash。但也有个例外，如果负载因子超过了 5（哈希冲突已非常严重），会强制做 rehash。
哈希表在 rehash 期间，会在两个哈希表里面查询，如果旧哈希表找不到结果，还需要在新哈希表里面查询一次。
最后，一个好的哈希函数对哈希表的性能起着至关重要的作用，好的哈希函数应该尽可能地避免哈希冲突，将多个 key 均匀地映射到整个哈希空间。那么 Redis 使用的是哪种哈希函数呢？更准确地说，Redis 的哈希函数内部使用了哪种算法呢？
Redis 3.0 之前使用 DJBX33A 算法；
Redis 3.0-4.0 使用 MurmurHash2 算法；
Redis 4.0 开始使用 SipHash 算法；
本文参考自：
极客时间蒋德钧：《Redis 源码剖析与实战》
小林 coding：《图解 Redis》
课代表 kaito 在极客时间《Redis 源码剖析与实战》评论区的精彩回答