Redis基本数据类型之Hash

2020-06-30

Redis Hash结构的数据存储是最常使用的一种之一，特别适合用于对象的存储，本节我们重点分析下其常用命令、底层实现、使用场景等等。

1、简单介绍

Redis hash是一个String类型的field和value的映射表。添加、删除操作复杂度平均为O(1)，为什么是平均呢？因为Hash的内部结构包含zipmap和hash两种。hash特别适合用于存储对象。相对于将对象序列化存储为String类型，将一个对象存储在hash类型中会占用更少的内存，并且可以方便的操作对象。为什么省内存，因为对象刚开始使用zipmap存储的。

2、常用命令

2.1、HSET-设置值

HSET hash field value

将哈希表 hash 中域 field 的值设置为 value 。

如果给定的哈希表并不存在，那么一个新的哈希表将被创建并执行 HSET 操作。如果域 field 已经存在于哈希表中，那么它的旧值将被新值 value 覆盖。

当 HSET 命令在哈希表中新创建 field 域并成功为它设置值时，命令返回 1 ；如果域 field 已经存在于哈希表，并且 HSET 命令成功使用新值覆盖了它的旧值，那么命令返回 0 。

2.2、HSETNX 不存在设置，存在不设置

HSETNX hash field value

当且仅当域 field 尚未存在于哈希表的情况下，将它的值设置为 value 。

如果给定域已经存在于哈希表当中，那么命令将放弃执行设置操作。如果哈希表 hash 不存在，那么一个新的哈希表将被创建并执行 HSETNX 命令。

2.3、HGET 获取值

HGET hash field

返回哈希表中给定域的值。

HGET 命令在默认情况下返回给定域的值。如果给定域不存在于哈希表中，又或者给定的哈希表并不存在，那么命令返回 nil 。

2.4、HEXISTS是否在该key中存在field

HEXISTS hash field

检查给定域 field 是否存在于哈希表 hash 当中。

2.5、HDEL删除指定的key下的field

HDEL key field [field …]

删除哈希表 key 中的一个或多个指定域，不存在的域将被忽略

2.6、HLEN 获取hash表中键值的数量

HLEN key

返回哈希表 key 中域的数量。

2.7、HMSET 设置多个hash值

HMSET key field value [field value …]

同时将多个 field-value (域-值)对设置到哈希表 key 中。

此命令会覆盖哈希表中已存在的域。如果 key 不存在，一个空哈希表被创建并执行 HMSET 操作。

2.8、HMGET 获取多个值

HMGET key field [field …]

返回哈希表 key 中，一个或多个给定域的值。

如果给定的域不存在于哈希表，那么返回一个 nil 值。因为不存在的 key 被当作一个空哈希表来处理，所以对一个不存在的 key 进行 HMGET操作将返回一个只带有 nil 值的表。

2.9、HKEYS 返回所有key中的field

HKEYS key

返回哈希表 key 中的所有域。

2.10、HVALS 返回所有field的值

HVALS key

返回哈希表 key 中所有域的值。

2.11、HGETALL获取所有的field及值

HGETALL key

返回哈希表 key 中，所有的域和值。

在返回值里，紧跟每个域名(field name)之后是域的值(value)，所以返回值的长度是哈希表大小的两倍。

2.12、HSTRLEN 获取给定key的field的字符串长度

HSTRLEN key field

返回哈希表 key 中，与给定域 field 相关联的值的字符串长度（string length）。

如果给定的键或者域不存在，那么命令返回 0 。

2.13、HINCRBY 给定指定key的field累加整数

HINCRBY key field increment

为哈希表 key 中的域 field 的值加上增量 increment 。

增量也可以为负数，相当于对给定域进行减法操作。

如果 key 不存在，一个新的哈希表被创建并执行 HINCRBY命令。如果域 field 不存在，那么在执行命令前，域的值被初始化为 0 。

对一个储存字符串值的域 field 执行 HINCRBY 命令将造成一个错误。本操作的值被限制在 64 位(bit)有符号数字表示之内。

2.14、HINCRBYFLOAT 给定指定key的field累加浮点数

HINCRBYFLOAT key field increment

为哈希表 key 中的域 field 加上浮点数增量 increment 。

如果哈希表中没有域 field ，那么 HINCRBYFLOAT 会先将域 field 的值设为 0 ，然后再执行加法操作。

如果键 key 不存在，那么 HINCRBYFLOAT 会先创建一个哈希表，再创建域 field ，最后再执行加法操作。

3、内部实现

redis的hash底层的结构是通过ziplist和hashtable两种，我们分析下为什么使用两种及两种结构内部如何存储的及相互转换条件等

3.1、ziplist压缩列表

压缩列表是redis为了节约内存开发的，是一系列特殊编码的连续内存块组成的顺序型数据结构

	格式	长度	说明
`zlbytes`	`uint32_t`	`4` 字节	记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配，或者计算 `zlend` 的位置时使用。
`zltail`	`uint32_t`	`4` 字节	记录压缩列表表尾节点距离压缩列表的起始地址有多少字节：通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。
`zllen`	`uint16_t`	`2` 字节	记录了压缩列表包含的节点数量：当这个属性的值小于 `UINT16_MAX` （`65535`）时，这个属性的值就是压缩列表包含节点的数量；当这个值等于 `UINT16_MAX` 时，节点的真实数量需要遍历整个压缩列表才能计算得出。
`entryX`	列表节点	不定	压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
`zlend`	`uint8_t`	`1` 字节	特殊值 `0xFF` （十进制 `255` ），用于标记压缩列表的末端。

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

保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后；
先添加到哈希对象中的键值对会被放在压缩列表的表头方向，而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。

演示添加的数据的过程，

entryX可以保存一个字节数组也可以保存一个整数值，我们重点看下entryX这个结构

字段	说明
previous_entry_length	压缩列表中前一个节点的长度，如果前一个节点长度小于254字节，那么previous_entry_length占用1字节，否则占用5字节（第一个字节是0xFE,后四个字节是长度）
encoding	保存数据的类型以及长度；字节数组：1/2/5字节长度，值的最高位分别是00/01/10，这种编码content表示存储的是字节数组，数组长度最高两位去除后其他位记录的；整数：1字节，值的最高位以11开头，这种编码content表示保存整数值，整数值的类型和长度由去除最高两位之后的其他位记录
content	保存节点的值，可以是一个字节数组或者整数

分析这个节点信息后，我们发现一个问题，每一个entryX中都会记录前一个节点的长度，如果插入节点到尾部没有任何问题，如果插入的节点是非尾部就会从下一个元素的prevlen（1字节）获取这个前一个节点的长度，如果此时插入的节点大于254那么下一个节点就存不下当前插入节点的长度，导致连锁反应。

压缩列表里要恰好有多个连续的、长度介于 250 字节至 253 字节之间的节点，连锁更新才有可能被引发，在实际中，这种情况并不多见；

即使出现连锁更新，但只要被更新的节点数量不多，就不会对性能造成任何影响

3.2、hashtable(字典)

字典，又称符号表（symbol table）、关联数组（associative array）或者映射（map），是一种用于保存键值对（key-value pair）的抽象数据结构。

3.2.1、数据结构

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

属性说明：

type 属性是一个指向 dictType 结构的指针，每个 dictType 结构保存了一簇用于操作特定类型键值对的函数， Redis 会为用途不同的字典设置不同的类型特定函数，如计算哈希值的函数、复制键的函数、复制值的函数等。
而 privdata 属性则保存了需要传给那些类型特定函数的可选参数
ht 属性是一个包含两个项的数组，数组中的每个项都是一个 dictht 哈希表，一般情况下，字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。
rehashidx ：它记录了 rehash 目前的进度，如果目前没有在进行 rehash ，那么它的值为 -1 。

真正存储数据的是ht,我们分析下数据结构

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

属性说明：

table 属性是一个数组，数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针，每个 dictEntry 结构保存着一个键值对。
size 属性记录了哈希表的大小，也即是 table 数组的大小，而 used 属性则记录了哈希表目前已有节点（键值对）的数量。
sizemask 属性的值总是等于 size - 1 ，这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。
used属性记录了该哈希表已使用节点的数量

table数组中存储的dictEntry数据结构

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

3.2.2、数据存储和解决冲突

键值对添加到字典里面时，需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

# 使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);

# 使用哈希表的 sizemask 属性和哈希值，计算出索引值
# 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

计算出要放在hash数组的指定索引

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时，我们称这些键发生了冲突，如上图中的<k1,v1>和<k2,v2>都被分配到3这个索引位置上，而解决冲突的办法就是使用 next 指针将键 k2 和 k1 所在的节点连接起来。

因为 dictEntry 节点组成的链表没有指向链表表尾的指针，所以为了速度考虑，程序总是将新节点添加到链表的表头位置（复杂度为 O(1)），排在其他已有节点的前面。

3.2.3、rehash

哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。

1 2	# 负载因子 = 哈希表已保存节点数量 / 哈希表大小 load_factor = ht[0].used / ht[0].size

条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：

服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 1 ；

服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 5

Redis 对字典的哈希表执行 rehash 的步骤如下：

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

3.3、ziplist和hashtable转换

ziplist是为了节省内存而设计的，默认是使用ziplist来存储但是需要满足两个条件

哈希对象保存的所有键值对的键和值的字符串长度REDIS_HASH_MAX_ZIPLIST_VALUE默认小于 64 字节；
哈希对象保存的键值对数量REDIS_HASH_MAX_ZIPLIST_ENTRIES 默认小于 512 个；

我们分析下源码：

能满足这两个条件的哈希对象需要使用 hashtable 编码

本文作者： 顾明训
本文链接： https://www.itzones.cn/2020/06/30/Redis基本数据类型之Hash/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！