Redis设计与实现3 哈希对象（ ziplist hashtable）

ziplist 编码的哈希对象使用压缩列表作为底层实现， 每当有新的键值对要加入到哈希对象时， 程序会先将保存了键的压缩列表节点推入到压缩列表表尾， 然后再将保存了值的压缩列表节点推入到压缩列表表尾， 因此：

保存了同一键值对的两个节点总是紧挨在一起， 保存键的节点在前， 保存值的节点在后；

先添加到哈希对象中的键值对会被放在压缩列表的表头方向， 而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。

举个例子， 如果我们执行以下 HSET 命令， 那么服务器将创建一个列表对象作为 profile 键的值：

另一方面， hashtable 编码的哈希对象使用字典作为底层实现， 哈希对象中的每个键值对都使用一个字典键值对来保存：

Redis 的字典使用哈希表作为底层实现， 一个哈希表里面可以有多个哈希表节点， 而每个哈希表节点就保存了字典中的一个键值对。

Redis 字典所使用的哈希表由 dict.h/dictht 结构定义：

table 属性是一个数组， 数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针， 每个 dictEntry 结构保存着一个键值对。

size 属性记录了哈希表的大小， 也即是 table 数组的大小， 而 used 属性则记录了哈希表目前已有节点（键值对）的数量。

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

图 4-1 展示了一个大小为 4 的空哈希表 （没有包含任何键值对）。

哈希表节点使用 dictEntry 结构表示， 每个 dictEntry 结构都保存着一个键值对：

key 属性保存着键值对中的键， 而 v 属性则保存着键值对中的值， 其中键值对的值可以是一个指针， 或者是一个 uint64_t 整数， 又或者是一个 int64_t 整数。

next 属性是指向另一个哈希表节点的指针， 这个指针可以将多个哈希值相同的键值对连接在一次， 以此来解决键冲突（collision）的问题。

举个例子， 图 4-2 就展示了如何通过 next 指针， 将两个索引值相同的键 k1 和 k0 连接在一起。

Redis 中的字典由 dict.h/dict 结构表示：

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

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

除了 ht[1] 之外， 另一个和 rehash 有关的属性就是 rehashidx ： 它记录了 rehash 目前的进度， 如果目前没有在进行 rehash ， 那么它的值为 -1 。

图 4-3 展示了一个普通状态下（没有进行 rehash）的字典：

在Redis中，由于它对实时性要求更高，因此使用了渐进式rehash

当有新键值对添加到Redis字典时，有可能会触发rehash。Redis中处理哈希碰撞的方法与Java一样，都是采用链表法，整个哈希表的性能则依赖于它的大小size和它已经保存节点数量used的比率。

比率在1:1时，哈希表的性能最好，如果节点数量比哈希表大小大很多的话，则整个哈希表就退化成多个链表，其性能优势全无。

上图的哈希表，平均每次失败查找需要访问5个节点。为了保持高效性能，在不修改键值对情况下，

需要进行rehash，目标是将ratio比率维持在1:1左右。

Ratio ＝ Used / Size

rehash触发条件：

rehash执行过程：

Redis哈希为了避免整个rehash过程中服务被阻塞，采用了渐进式的rehash，即rehash程序激活后，并不是

马上执行直到完成，而是分多次，渐进式（incremental）的完成。同时，为了保证并发安全，在执行rehash

中间执行添加时，新的节点会直接添加到ht[1]而不是ht[0], 这样保证了数据的完整性与安全性。

另一方面，哈希的Rehash在还提供了创新的（相对于Java HashMap）收缩（shrink）字典，当可用节点远远

大于已用节点的时候，rehash会自动进行收缩，具体过程与上面类似以保证比率始终高效使用。

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

Redis hash 是一个 string 类型的 field（字段） 和 value（值） 的映射表，hash 特别适合用于存储对象。

Redis 中每个 hash 可以存储 232 - 1 键值对（40多亿）。

hash类型可以理解为map集合，{key1:value1,key2:value2}

实例

Hash 的应用场景：

将一个用户作为一个 hash ，然后其属性和值就作为内部的 k-v 集合进行存储

例如

user:1 代表第 1 个用户，然后这个用户具有 name，age，job 这些字段，因为 redis 效率很高，因此适合将属性值经常变动的对象作为 hash 存储

个人理解和便于学习，进行了简单分类！

分为以下几类：

下表列出了 redis hash 基本的相关命令：

更多命令请参考： https://redis.io/commands

当Hash的数据项较少时,Hash底层才会用压缩列表zipList进行存储数据.数据增加,底层的zipList会转成dict,

具体配置如下

dict的数据结构:

由此可见,每个dict中有两个hashtable

结构图如下:

指大字典扩容较耗时,需重新申请新的数组,然后将旧字典所有链表的元素重新挂接到新的数组下面,是一个O(n)的 *** 作.

因为Redis是单线程的,无法承受这样的耗时过程,所以采用渐进式rehash小步搬迁,虽然慢一点,但可以搬迁完毕.

扩容一般在hash表中的元素个数等于第一维数组长度时,开始扩容. 扩容大小是原数组的两倍.不过在Redis做bgsave(RDB持久化 *** 作的过程),为了减少内存页的过多分离(copy on write),Redis不会去扩容. 但如果hash表的元素个数已经达到了第一维数组长度的5倍时,就会强制扩容,无论是否在持久化.

不扩容主要是为了尽可能减少内存页过多分离,系统需要过多的开销去回收内存 .

当我们的hash表元素逐渐删除越来越少时,redis于是就会对hash表进行缩容来减少第一维数组长度的空间占用. 缩容条件是元素个数低于数组长度的10%,并且缩容不考虑是否在持久化.

不用考虑bgsave主要是因为我们的缩容的内存都是已经使用过的,缩容的时候可以直接置空,而且由于申请的内存比较小,提示会释放一些已经使用的内存,不会增大系统的压力.

rehash步骤:

过程图如下:

---