Redis 基本数据结构三:哈希

1. 哈希简介

几乎所有的编程语言都提供了哈希(hash)类型,例如 Java 中的 Map,python 中的字典,在Redis中,哈希类型是指键的值本身又是一个键值对结构,如下图所示:

2. 常用命令

  • 设置值
# HSET key field value
node02:6379> hset user name tom
(integer) 1
# hsetnx: field 不存在就创建,否则不覆盖旧值,返回0
# node02:6379> hsetnx user name tom
(integer) 0
  • 批量设置值
# HMSET key field value [field value ...]
node02:6379> hmset user name tom age 20 sex male
OK
  • 获取值
# HGET key field
node02:6379> hget user name
"tom"
  • 批量获取值
# HMGET key field [field ...]
node02:6379> hmget user name age sex
1) "tom"
2) "20"
3) "male"
  • 删除 field
# HDEL key field [field ...]
node02:6379> hdel user age
(integer) 1
  • 统计 field 个数
node02:6379> hlen user
(integer) 1
  • field 是否存在
# HEXISTS key field
node02:6379> hexists user score
(integer) 0
  • 获取所有 field
# HKEYS key
node02:6379> hkeys user
1) "name"
2) "age"
3) "sex"
  • 获取所有 value
# HVALS key
node02:6379> hvals user
1) "tom"
2) "20"
3) "male"
  • 获取所有 field-value
# HGETALL key
node02:6379> hgetall user
1) "name"
2) "tom"
3) "age"
4) "20"
5) "sex"
6) "male"

说明,当 field-value 此种方式可能造成阻塞,尽量获取部分的 field,如果一定要获取全部的 field-value,优先使用 hscan 命令。hscan 命令会循序渐进的读取 key,而不是一口气都读出来。

# HSCAN key cursor [MATCH pattern] [COUNT count]
# cursor: 游标,从此处开始遍历,第一次遍历设置为 0
# pattern: 遍历 field 的正则,例如 test*,代表只遍历 test 开头的 field
# count: 每个遍历读取多少条记录,默认为 10
node02:6379> hscan user 0
1) "0"
2) 1) "name"
   2) "tom"
   3) "age"
   4) "20"
   5) "sex"
   6) "male"
# 返回值"0",是下次应该遍历的 cursor
# 因为这里默认第一次遍历10个,已经全部查出来了,所以下次的 cursor 为 0.
  • field 数值计算
node02:6379> hincrby user name 1
(error) ERR hash value is not an integer
node02:6379> hincrby user age 1
(integer) 21
node02:6379> hincrbyfloat user age 2.5
"23.5"
  • 统计 value 的长度
node02:6379> hstrlen user name
(integer) 3

3. 内部编码

哈希类型的内部编码有两种:

  • ziplist:当哈希类型元素个数小于hash-max-ziplist-entries 配置(默认512个)、同时所有值都小于hash-max-ziplist-value配置(默认64 字节)时,Redis会使用ziplist作为哈希的内部实现,ziplist使用更加紧凑的结构实现多个元素的连续存储,所以在节省内存方面比hashtable更加优秀。
  • hashtable:当哈希类型无法满足ziplist的条件时,Redis会使 用hashtable作为哈希的内部实现,因为此时ziplist的读写效率会下降,而hashtable的读写时间复杂度为O(1),但是hashtable会占用更多内存。
# 当field个数比较少且没有大的value时,内部编码为ziplist
beh07:6379> hmset map k1 v1 k2 v2
OK
beh07:6379> object encoding map
"ziplist"

# 当有value大于64字节,内部编码会由ziplist变为hashtable
beh07:6379> hset map k3 "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ"
(integer) 1
beh07:6379> object encoding map
"hashtable"

# 当field个数超过512,内部编码也会由ziplist变为hashtable,这里不演示了....

4. 内部结构

hashtable 的结构和 Java 的 HashMap 几乎是一样的,都是通过分桶的方式解决 hash 冲突。它是无序字典。内部实现结构上同 Java 的 HashMap 也是一致的,同样的数组 + 链表二维结构。第一维 hash 的数组位置碰撞时,就会将碰撞的元素使用链表串接起来。第一维是数组,第二维是链表。数组中存储的是第二维链表的第一个元素的指针。

渐进式rehash

大字典的扩容是比较耗时间的,需要重新申请新的数组,然后将旧字典所有链表中的元素重新挂接到新的数组下面,这是一个O(n)级别的操作,作为单线程的Redis表示很难承受这样耗时的过程。步子迈大了会扯着蛋,所以Redis使用渐进式rehash小步搬迁。虽然慢一点,但是肯定可以搬完。

渐进式 rehash 会在 rehash 的同时,保留新旧两个 hash 结构,查询时会同时查询两个 hash 结构,然后在后续的定时任务中以及 hash 操作指令中,循序渐进地将旧 hash 的内容一点点迁移到新的 hash 结构中。当搬迁完成了,就会使用新的hash结构取而代之。当 hash 移除了最后一个元素之后,该数据结构自动被删除,内存被回收。

搬迁操作埋伏在当前字典的后续指令中(来自客户端的hset/hdel指令等),但是有可能客户端闲下来了,没有了后续指令来触发这个搬迁,那么Redis就置之不理了么?当然不会,优雅的Redis怎么可能设计的这样潦草。Redis还会在定时任务中对字典进行主动搬迁。

hash函数

hashtable 的性能好不好完全取决于 hash 函数的质量。hash 函数如果可以将 key 打散的比较均匀,那么这个 hash 函数就是个好函数。Redis 的字典默认的 hash 函数是 siphash。siphash 算法即使在输入 key 很小的情况下,也可以产生随机性特别好的输出,而且它的性能也非常突出。对于 Redis 这样的单线程来说,字典数据结构如此普遍,字典操作也会非常频繁,hash 函数自然也是越快越好。

扩容条件

正常情况下,当 hash 表中元素的个数等于第一维数组的长度时,就会开始扩容,扩容的新数组是原数组大小的 2 倍。不过如果 Redis 正在做 bgsave,为了减少内存页的过多分离 (Copy On Write),Redis 尽量不去扩容(dict_can_resize),但是如果 hash 表已经非常满了,元素的个数已经达到了第一维数组长度的 5 倍 (dict_force_resize_ratio),说明 hash 表已经过于拥挤了,这个时候就会强制扩容。

缩容条件

当 hash 表因为元素的逐渐删除变得越来越稀疏时,Redis 会对 hash 表进行缩容来减少 hash 表的第一维数组空间占用。缩容的条件是元素个数低于数组长度的 10%。缩容不会考虑 Redis 是否正在做 bgsave。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券