【Redis】哈希对象、哈希表、哈希表节点、字典及其扩容机制

文章目录

前言

首先，说道哈希对象，在Redis中，他是Redis对外支持的五种数据结构之一（字符串、list、set、Zset和他自己哈希表）。

接下来将会针对次数据结构讲解一些细节，供大家参考学习。

一、哈希对象

哈希表在Redis中可以由两种底层的数据结构来实现，分别是：

编码转换条件：

当哈希对象可以同时满足以下两个条件时，哈希对象使用ziplist编码：

接下来要说的哈希表，是哈希对象的底层实现方式之一（另一个是压缩列表）。

二、哈希表

一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

在Redis中，哈希表是字典的底层实现（补充一下，字典又是Redis数据库的底层实现）。而哈希表本身又是如何实现的呢？

在Redis之外，一般如何构建哈希表？

一般来说，我们使用数组+链表的形式来实现哈希表，具体规则为：

在Redis中，哈希表结构定义

哈希表数组就是我上稳重提到的数组结构。
与此同时哈希表本身还维护着一些变量：哈希表的大小、掩码、已有哈希节点数量等等（说句题外话，这些变量，随时都能通过直接调用过去的时间复杂度为1的树枝，都是Redis查询速度快的原因之一）。

三、哈希表节点

上文中提到，哈希表的核心数据存储是放在一个叫做哈西数组的数组结构中，而数组中的具体元素，格式为哈希表节点，其中每一个哈希表节点都保存着一个键值对，如下图所示：

四、字典 1、字典的实现

注意，ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表， ht[l]哈希表只会在对ht[0]哈希表进行rehash时使用。

那什么是rehash呢？

2、rehash（扩容、缩容）

当原来的哈希表经放了较多的元素时，频繁出现哈西冲突（或者为了预防频繁出现的哈西冲突），便需要扩容。

3、什么时候才需要rehash？

当下列条件的任何一个被满足时，自动扩容：

另外，当负载因子 < 0.1时，便会开始缩容操作。

4、负载因子的计算：

具体怎么扩容缩容请看下一小节。

5、rehash的步骤如下：

为ht[1] 分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（也即是ht[0] . used属性的值）：如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于 ht[0].used*2的2”（2的"次方需）；如果执行的是收缩操作，那么ht[l]的大小为第一个大于等于ht[0] .used的2的n次方"。
将保存在ht[0]中的所有键值对重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。
当ht[0]包含的所有键值对都迁移到了 ht[l]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[l]新创建一个空白哈希表，为下一次rehash做准备

五、扩容时如何保证可操作？渐进式rehash

rehash动作并不是一次性完成的，而是分多次、渐进式地完成。这样做的原因在于，如果如果哈希表里保存的键值对数量是过多，那么要一次性将这些键值对全部rehash到 ht[1] 的话，庞大的计算量可能会导致服务器在一段时间内停止服务。

因此，为了避免rehash对服务器性能造成影响，服务器不是一次性将ht[O]里面的所有键值对全部rehash到ht[l]，而是分多次、渐进式地将ht[0]里面的键值对慢慢地rehash到 ht[1]

这就涉及到一个概念——渐进式rehash。

渐进式rehash的步骤

为ht[l]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。
在rehash进行期间，每次对字典进行增删改查时，会顺带将ht[0]哈希表在rehashidx为索引位上的所有键值对rehash到ht [1]，当rehash工作完成之后，程序将rehashidx属性的值增一。其中，ht0的key转移到ht1中，ht0原位置变为空。
随着字典操作的不断执行，最终在某个时间点上， ht[0]的所有键值对都会被rehash至ht [1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。

另外注意：

在rehash时，外界要査找一个键的话，程序会先在ht[0]里査找，如果没找到，就会到ht[1]里査找。
另外，在渐进式rehash期间，新添加到字典的键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作，这一措施保证了 ht[0]包含的键值对数量会只减不增，并随着rehash操作的执行而最终变成空表。