1. 什么是字典(hash)
Redis 的字典相当于 Java 语言里面的 HashMap,如图所示:
它是无序字典,内部存储了很多键值对。实现结构上与 Java 的 HashMap也是一样的,都是“数组 + 链表”的二维结构。在数组位置发生 hash 冲突时,就会将冲突的元素使用链表串起来,如图所示:
与 Java HashMap 不同的是,Redis 的字典的值只能是字符串,另外它们 rehash 的方式也不一样。因为 Java HashMap 在字典很大时,rehash 是一个耗时的操作,需要一次性全部 rehash。Redis 为了追求高性能,不能堵塞服务,所以采用了渐进式 rehash 策略。关于 rehash 的内容,后面再具体说明。
2. 字典的数据结构
Redis 的字典使用哈希表作为底层实现,一个哈希表里面可以有多个哈希表节点,而每个哈希表节点就保存了字典中的一个键值对。
2.1 哈希表节点
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
属性:是指向另一个哈希表节点的指针,这个指针可以将多个哈希值相同的键值对连接在一起,以此来解决键冲突的问题。
- uint64_t:指的是无符号64位整数;
- int64_t:值得是带符号64位整数。
2.2 哈希表
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码,用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
}dictht;
table
属性:是一个数组,数组中的每个元素都是一个指向哈希表节点(dictEntry)结构的指针,每个哈希表节点(dictEntry)都保存着一个键值对;size
属性:记录了哈希表的大小,也即是table
数组的大小;used
属性:记录了哈希表目前已有节点(键值对)的数量;sizemask
属性:它的值总是等于size - 1
,这个属性和哈希值一起决定了一个键应该被放到table
数组的哪个索引上面。
2.3 字典
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash索引
// 当 rehash 不在进行时,值为 -1
int rehashidx;
} dict;
type
&privdata
属性:是针对不同类型的键值对,为创建多态字典而设置的;type
属性:是一个指向dictType
结构的指针;dictType
结构:保存了一簇用于操作特定类型键值对的函数,Redis 会为用途不同的字典设置不同的类型特定函数;privdata
属性:保存了需要传给那些类型特定函数的可选参数;ht
属性:是一个包含两个项的数组,数组中的每个项都是一个dictht
哈希表,一般情况下,字典只使用ht[0]
哈希表,ht[1]
哈希表只会在对ht[0]
哈希表进行rehash
时使用;rehashidx
:它记录了rehash
目前的进度,如果目前没有在进行rehash
,那么它的值为-1
。
2.4 类型特定函数
typedef struct dictType {
// 计算哈希值的函数
unsigned int (*hashFunction)(const void *key);
// 复制键的函数
void *(*keyDup)(void *privdata, const void *key);
// 复制值的函数
void *(*valueDup)(void *privdata, const void *obj);
// 对比键的函数
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
// 销毁键的函数
void (*keyDestructor)(void *privdata, void *key);
// 销毁值的函数
void (*valDestructor)(void *privdata, void *obj);
} dictType;
2.5 小结
3. hash 的基本使用
3.1 HSET
Redis Hset
命令用于为哈希表中的字段赋值 。
如果哈希表不存在,一个新的哈希表被创建并进行 HSET
操作。
如果字段已经存在于哈希表中,旧值将被覆盖。
如果字段是哈希表中的一个新建字段,并且值设置成功,返回 1 。 如果哈希表中域字段已经存在且旧值已被新值覆盖,返回 0 。
3.1.1 语法
redis 127.0.0.1:6379> HSET KEY_NAME FIELD VALUE
3.1.2 示例
# 设置不存在新值 -> 返回 1
127.0.0.1:6379> HSET myhash field1 "redis"
(integer) 1
127.0.0.1:6379> HSET myhash field2 "Java"
(integer) 1
# 查看 myhash 的所有键值对
127.0.0.1:6379> HGETALL myhash
1) "field1"
2) "redis"
3) "field2"
4) "Java"
# 覆盖已存在值 -> 返回 0
127.0.0.1:6379> HSET myhash field2 "Mongo"
(integer) 0
# 覆盖成功
127.0.0.1:6379> HGETALL myhash
1) "field1"
2) "redis"
3) "field2"
4) "Mongo"
3.2 HMSET
Redis Hmset
命令用于同时将多个 field-value
(字段-值)对设置到哈希表中。
此命令会覆盖哈希表中已存在的字段。
如果哈希表不存在,会创建一个空哈希表,并执行 HMSET
操作。
如果命令执行成功,返回 OK 。
HSET 的批量操作版
3.2.1 语法
redis 127.0.0.1:6379> HMSET KEY_NAME FIELD1 VALUE1 ...FIELDN VALUEN
3.2.2 示例
127.0.0.1:6379> HMSET myhash field1 "Java" field2 "C" field3 "C#" field4 "Go"
OK
127.0.0.1:6379> HGETALL myhash
1) "field1"
2) "Java"
3) "field2"
4) "C"
5) "field3"
6) "C#"
7) "field4"
8) "Go"
3.3 HSETNX
Redis Hsetnx
命令用于为哈希表中不存在的的字段赋值 。
如果哈希表不存在,一个新的哈希表被创建并进行 HSET
操作。
如果字段已经存在于哈希表中,操作无效。
如果 key
不存在,一个新哈希表被创建并执行 HSETNX
命令。
和 HSET & HMSET 的区别就是,不会覆盖已存在的值
3.3.1 语法
redis 127.0.0.1:6379> HSETNX KEY_NAME FIELD VALUE
3.3.2 示例
# 得到目前 myhash 的键值对
127.0.0.1:6379> HGETALL myhash
1) "field1"
2) "Java"
3) "field2"
4) "C"
5) "field3"
6) "C#"
7) "field4"
8) "Go"
# 尝试使用 HSETNX 覆盖已有的值 -> 返回 0,失败
127.0.0.1:6379> HSETNX myhash field1 "python"
(integer) 0
# myhash 的键值对没有发生变化
127.0.0.1:6379> HGETALL myhash
1) "field1"
2) "Java"
3) "field2"
4) "C"
5) "field3"
6) "C#"
7) "field4"
8) "Go"
# 使用 HSETNX 插入新的键值对
127.0.0.1:6379> HSETNX myhash field5 "python"
(integer) 1
# 插入成功
127.0.0.1:6379> HGETALL myhash
1) "field1"
2) "Java"
3) "field2"
4) "C"
5) "field3"
6) "C#"
7) "field4"
8) "Go"
9) "field5"
10) "python"
3.4 HGET
Redis Hget 命令用于返回哈希表中指定字段的值。
返回给定字段的值。如果给定的字段或 key
不存在时,返回 nil
。
3.4.1 语法
redis 127.0.0.1:6379> HGET KEY_NAME FIELD_NAME
3.4.2 示例
# HGET 获取已存在的 key
127.0.0.1:6379> HGET myhash field1
"Java"
127.0.0.1:6379> HGET myhash field2
"C"
# HGET 获取不存在的 key
127.0.0.1:6379> HGET myhash field7
(nil)
3.5 HGETALL
Redis Hgetall
命令用于返回哈希表中,所有的字段和值。
在返回值里,紧跟每个字段名(field name)之后是字段的值(value),所以返回值的长度是哈希表大小的两倍。
3.5.1 语法
redis 127.0.0.1:6379> HGETALL KEY_NAME
3.5.2 示例
127.0.0.1:6379> HGETALL myhash
1) "field1"
2) "Java"
3) "field2"
4) "C"
5) "field3"
6) "C#"
7) "field4"
8) "Go"
9) "field5"
10) "python"
3.6 HKEYS
Redis Hkeys
命令用于获取哈希表中的所有域(field)。
3.6.1 语法
redis 127.0.0.1:6379> HKEYS KEY_NAME
3.6.2 示例
127.0.0.1:6379> HKEYS myhash
1) "field1"
2) "field2"
3) "field3"
4) "field4"
5) "field5"
3.7 HVALS
Redis Hvals
命令返回哈希表所有域(field)的值。
3.7.1 语法
redis 127.0.0.1:6379> HVALS KEY_NAME
3.7.2 示例
127.0.0.1:6379> HVALS myhash
1) "Java"
2) "C"
3) "C#"
4) "Go"
5) "python"
3.8 HLEN
Redis Hlen
命令用于获取哈希表中字段的数量。
3.8.1 语法
redis 127.0.0.1:6379> HLEN KEY_NAME
3.8.2 示例
127.0.0.1:6379> HLEN myhash
(integer) 5
3.9 HEXISTS
Redis Hexists
命令用于查看哈希表的指定字段是否存在。
如果哈希表含有给定字段,返回 1
。 如果哈希表不含有给定字段,或 key
不存在,返回 0
。
3.9.1 语法
redis 127.0.0.1:6379> HEXISTS KEY_NAME FIELD_NAME
3.9.2
# 查询存在的 FIELD
127.0.0.1:6379> HEXISTS myhash field1
(integer) 1
127.0.0.1:6379> HEXISTS myhash field2
(integer) 1
# 查询不存在的 FIELD
127.0.0.1:6379> HEXISTS myhash field8
(integer) 0
3.10 HDEL
Redis Hdel
命令用于删除哈希表 key
中的一个或多个指定字段,不存在的字段将被忽略。
返回值:被成功删除字段的数量,不包括被忽略的字段。
3.10.1 语法
redis 127.0.0.1:6379> HDEL KEY_NAME FIELD1.. FIELDN
3.10.2 示例
# 目前 myhash 的键值对
127.0.0.1:6379> HGETALL myhash
1) "field1"
2) "Java"
3) "field2"
4) "C"
5) "field3"
6) "C#"
7) "field4"
8) "Go"
9) "field5"
10) "python"
# 删除存在的 FIELD
127.0.0.1:6379> HDEL myhash field5
(integer) 1
127.0.0.1:6379> HGETALL myhash
1) "field1"
2) "Java"
3) "field2"
4) "C"
5) "field3"
6) "C#"
7) "field4"
8) "Go"
# 删除不存在的 FIELD
127.0.0.1:6379> HDEL myhash field6
(integer) 0
# 删除多个存在的 FIELD
127.0.0.1:6379> HDEL myhash field1 field2
(integer) 2
127.0.0.1:6379> HGETALL myhash
1) "field3"
2) "C#"
3) "field4"
4) "Go"
3.11 HINCRBY
Redis Hincrby
命令用于为哈希表中的字段值加上指定增量值。
增量也可以为负数,相当于对指定字段进行减法操作。
如果哈希表的 key
不存在,一个新的哈希表被创建并执行 HINCRBY
命令。
如果指定的字段不存在,那么在执行命令前,字段的值被初始化为 0
。
对一个储存字符串值的字段执行 HINCRBY
命令将造成一个错误。
返回值:执行 HINCRBY
命令之后,哈希表中字段的值。
3.11.1 语法
redis 127.0.0.1:6379> HINCRBY KEY_NAME FIELD_NAME INCR_BY_NUMBER
3.11.2 示例
# 插入新的 FIELD,VALUE 为 10
127.0.0.1:6379> HSET myhash field5 10
(integer) 1
127.0.0.1:6379> HGETALL myhash
1) "field3"
2) "C#"
3) "field4"
4) "Go"
5) "field5"
6) "10"
# 加减 field5 的值
127.0.0.1:6379> HINCRBY myhash field5 5
(integer) 15
127.0.0.1:6379> HINCRBY myhash field5 -10
(integer) 5
4. 哈希算法
当要将一个新的键值对添加到 hash
里面时,程序需要先根据键值对的键计算出哈希值和索引值,然后再根据索引值,将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。
Redis
计算哈希值和索引值的方法如下:
# 使用字典设置的哈希函数,计算键 key 的哈希值(类型特定函数中)
hash = dictType#hashFunction(key)
# 使用哈希表的 sizemask 属性和哈希值,计算出索引值(哈希表中)
# ht[x] -> 如果当前 hash 处于 rehash 阶段,则可能是ht[0] || ht[1]
index = hash & dictht#ht[x].sizemask
5. 键冲突
和 Java HashMap
类似,Redis Hash
也是由数组 + 链表的方式组成。所以在发生键冲突时,Redis 的哈希表也是通过构成一个单向链表,将冲突的键连接起来,以此来解决键冲突的问题。再次看回下面的图,就可以理解 Redis Hash
是怎么解决键冲突的了。
6. rehash
随着操作不断执行,哈希表保存的键值对会逐渐地增加或者减少,为了让哈希表的负载因子(load factor)维持在一个合理的范围之内,程序会对哈希表的大小进行相应的扩展或者收缩。
在描述 rehash
的步骤之前,先回顾一下字典的数据结构:
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash索引
// 当 rehash 不在进行时,值为 -1
int rehashidx;
} dict;
Redis
对哈希表进行 rehash
的步骤如下:
- 为字典的
ht[1]
分配空间,这个空间取决于要执行的操作类型,以及ht[0]
当前所包含的键值对数量(也就是ht[0].used
属性的值);- 扩展操作:
ht[1]
>= 第一个大于ht[0].used * 2
的 2n; - 收缩操作:
ht[1]
>= 第一个大于ht[0].used
的 2n。
- 扩展操作:
- 通过对
ht[0]
的键进行重新计算哈希值和索引值后,保存到ht[1]
里; - 当
rehash
结束后,ht[0]
会被自动删除,内存被回收。然后将ht[1]
设置为ht[0]
,并在ht[1]
新创建一个空白哈希表,为下一次rehash
做准备。
7. 渐进式 rehash
当哈希表里的键值对数量过大,进行常规的 rehash
所占用的时间过大,会影响用户的正常使用。所以,Redis
采取了渐进式 rehash
的方式,通过分多次、渐进式地将 ht[0]
里面的键值对慢慢地 rehash
到 ht[1]
中。
渐进式 rehash
的步骤如下:
- 给
ht[1]
分配空间; - 在字典中维持一个索引计数器变量
rehashidx
,并将它的值设置为0
,表示rehash
开始; - 在
rehash
期间,每次对字典执行增删改查操作时,程序除了执行指定的操作以外,还会顺带将ht[0]
哈希表在rehashindex
索引上的所有键值对rehash
到ht[1]
,当rehash
工作完成以后,rehashindex + 1
; - 当
ht[0]
的所有值都rehash
到ht[1]
后,rehashidx
会被设为-1
,表示rehash
结束。
7.1 渐进式 rehash 时操作哈希表
- 查找:现在
ht[0]
找,找不到再到ht[1]
找; - 添加:直接往
ht[1]
中添加; - 更新、删除:先找到,再更新/删除。也是在
ht[0] & ht[1]
之间进行。
8. 字典 API
函数 | 作用 | 时间复杂度 |
---|---|---|
dictRelease | 释放给定字典,以及字典中所包含的所有键值对 | O(N),N 为字典包含的键值对数量 |
频繁释放(rehash)数据量大的字典,非常影响整体的性能
9. 参考
- 《Redis 设计与实现》
- 《Redis 深度历险 核心原理与应用实践》
- Redis 字典
10. 其他相关文章
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/77873.html