![](/style/images/good.png)
![](/style/images/bad.png)
深入理解Redis 数据结构—字典 - 小码code
source link: https://www.cnblogs.com/jeremylai7/p/16600789.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
深入理解Redis 数据结构—字典
字典,又称为符号表、关联数组或映射,是一种用于保存键值对的抽象数据结构。在字典中,一个键可以和一个值进行关联,这些关联的键和值称为键值对。键值对中键是
唯一的
,我们可以根据键key
通过映射查找或者更新对应的值value
。
很多高级开发语言有对应集合支持字典这种数据结构,比如Java
中的Map
集合。C语言
并未内置字典这种数据结构,Redis
构建了自己的字典实现。
字典在Redis
中应用非常广泛,Redis
数据库就是使用字典作为数据底层的实现。对数据的增、删、改、查操作也是建立在字典之上操作。
当执行命令:
set msg "hello"
在数据库中创建一个键为 msg
,值为 hello
的键值对,这个键值对
就用字典来实现的。创建其他数据类型的键值对,比如list
、hash
、set
、sort set
也是用字典来实现的。
处理用来表示数据中的键值对,字典还是hash
数据类型底层实现之一,比如一个hash
数据类型website
,包含100
个键值对,这些键值对中的键是网址名称
,值是网页地址
:
redis> HGETALL website
1)"Redis"
2)"Redis.io"
3)"nacos"
4)"nacos.io"
.....
website
键的底层就是一个字典,包好了100
个键值对
,例如:
- 键值对中的键为
"Redis"
,值为"Redis.io"
。 - 键值对中的键为
"nacos"
,值为"nacos.io"
。
字典的实现
Redis
字典使用哈希表作为底层实现,一个哈希表里面有多个哈希表节点,每个哈希表节点保存字典中的键值对。
Redis
字典使用的哈希表由 dict.h/dictht 结构来表示:
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
// table 数组
dictEntry **table;
// 哈希表的大小
unsigned long size;
// 等于size-1,用于计算索引值
unsigned long sizemask;
// 已有的键值对数量
unsigned long used;
} dictht;
注释:这是哈希表结构,每个字典有两个实现增量重散列,从旧的哈希表到新的哈希表。
table
属性的是一个数组,数组中的每个元素都指向哈希节点dictEntry
,每个dictEntry
结构都保存一个键值对。size
记录了哈希表的大小,也就是table
数组的大小。used
属性记录了哈希表目前已有的键值对数量。sizemask
的值等于size-1
,这个属性和哈希表一起决定键应该放在table
数组的那个位置上。
下图展示一个大小为4
空哈希表(没有包含任务的键值对):
![2448954-20220819084954377-1737203009.png](https://img2022.cnblogs.com/blog/2448954/202208/2448954-20220819084954377-1737203009.png)
哈希表节点
哈希表节点使用dictEntry结构来表示,每个dictEntry
结构都保存着一个键值对
:
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下一个哈希表节点,形成链表
struct dictEntry *next;
} dictEntry;
key
保存键值v
保持值,v
可以是一个指针,可以是uint64_t
整数,也可以是一个int64_t
整数。next
指向另一个哈希表节点的指针,这个指针将多个哈希值相同
的键值对连接在一起,以此解决hash冲突
的问题。
下图展示两个键的hash值
相同的哈希表节点k0
和k1
,两者通过next
指针连接在一起。
![2448954-20220819085021338-1162896736.png](https://img2022.cnblogs.com/blog/2448954/202208/2448954-20220819085021338-1162896736.png)
Redis
中的字典由dict.h/dict结构表示:
typedef struct dict {
// 类型特定的函数
dictType *type;
// 私有函数
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
int iterators; /* number of iterators currently running */
} dict;
type
属性和privadata
属性是针对不同类型的键值对,为创建多态的字典而设置。type
是指向dictType
结构的指针,每个dictType
包含几组针对特定类型的键值对操作的函数,Redis
会为用途不同的字典设置不同的函数。下图展示dictType
字典类型:
typedef struct dictType {
// 计算哈希值
unsigned int (*hashFunction)(const void *key);
// 复制键
void *(*keyDup)(void *privdata, const void *key);
// 复制值
void *(*valDup)(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;
-
privdata
属性保存针对不同的类型操作的函数传的可选参数。 -
ht[2]
是包含两个数大小的数组,类型为dictht
哈希表。字典只使用ht[0]
哈希表,ht[1]
只会对ht[0]
哈希表进行rehash
时使用。 -
rehashidx
记录了rehash
的进度,如果目前没有进行的rehash
,那么它的值为-1
。
下图为一个普通状态下(没有进行rehash)的字典:
![2448954-20220819085051529-1308185212.png](https://img2022.cnblogs.com/blog/2448954/202208/2448954-20220819085051529-1308185212.png)
当要将一个新的键值对添加到字典中,程序需要先根据键值对中的键计算出哈希值和索引值,然后根据索引值,将包含新键值的哈希表放在哈希表数组的指定索引上。
Redis
计算哈希值和索引值的步骤如下:
- 使用字典设置的哈希函数,计算键的哈希值。
hash = dict—>type->hashFunction(key)
- 使用哈希表的
sizemask
属性和哈希值,取余计算出哈希值。
index = hash & dict ->ht[x].sizemask
了解过HashMap
底层原理的同学应该知道,上面计算索引值和HashMap
找到索引下标的原理是类似的。
什么是取余
&
运算?
取余就是计算两数相除的余数, 比如一个数组长度为4,索引范围是0~3
,需要放置0,1,7
,放置如下图所示:
![2448954-20220819085120180-1280216549.png](https://img2022.cnblogs.com/blog/2448954/202208/2448954-20220819085120180-1280216549.png)
举个例子,要将一个键值对k0
和v0
添加到下方的空字典表中:
![2448954-20220819085138479-880079657.png](https://img2022.cnblogs.com/blog/2448954/202208/2448954-20220819085138479-880079657.png)
首先计算键的哈希值:
hash = dict—>type->hashFunction(key)
计算键k0
的哈希值。
假设计算出来的哈希值为8
,然后计算索引值:
index = dict -> hash & ht[0].sizemask = 8 & 3 = 0;
计算出键k0
的索引值0
,这表示键值对k0
和v0
的节点放置到哈希表数组下标0
的位置上,如下图所示:
![2448954-20220819085207288-1374073043.png](https://img2022.cnblogs.com/blog/2448954/202208/2448954-20220819085207288-1374073043.png)
当两个或者两个以上的计算出数组索引值一致时,就发生了键冲突
。
Redis的哈希表采用链表法
来解决键冲突,每个哈希表的节点都有一个next
指针,多个哈希表节点用next
指针组成一个单链表,被分配到同一个数组索引上的多个节点使用单向链表连接起来,这就很好的解决了键冲突
的问题。
举个例子,程序要将一个键值对k2
和v2
添加到下图的哈希表中,并且计算k2
的索引值为2
,那么键k1
和k2
将发生冲突:
![2448954-20220819085224801-1810720828.png](https://img2022.cnblogs.com/blog/2448954/202208/2448954-20220819085224801-1810720828.png)
解决冲突的办法就是使用next
指针将k2
和k1
所在的节点连接起来,如下图所示:
![2448954-20220819085239037-974887020.png](https://img2022.cnblogs.com/blog/2448954/202208/2448954-20220819085239037-974887020.png)
- 字典是一种映射的
键值对
数据结构,其中键是唯一的,通过唯一的键可以快速找到对应的值。 - 字典包含广泛用在
Redis
数据库中。- 其中所有数据类型的键值对都使用字典作为底层实现。
Hash
类型的键值对也是基于字典实现。
- 字典的结构
- 包含一个字典,包含根据特定类型处理的函数
dictType
、两个哈希表ht[2]
,字典只用到了ht[0]
,遇到了扩容才会使用ht[1]
。 - 一个字典包含
两个哈希表
,每个哈希表dictht
包含一个table
数组,size
记录数组的大小,sizemask
等于size-1
,sizemask
和哈希值决定数据存在在table
的位置。used
记录已有的键值对。 - 哈希表节点dictEntry
结构保存一个键值对,其中
key保存键,
V保存值,
V可以是一个指针、可以是
uint64_t整数、也可以是
int64_t的整数。
next是为了解决
键hash冲突,两个键的计算出的索引在数组的同一个地方,就使用
next`指针连接在一起。
- 包含一个字典,包含根据特定类型处理的函数
- 新增一个键值对,首先通过调用
dict—>type->hashFunction(key)
计算键的哈希值
,再和dictht
的sizemask
做取余操作,计算得到要存放table
数组的索引位置。如果发生键冲突
时,使用链表法
将多个哈希节点通过next
指针组成一个单链表。 Redis
字典的实现和Java
中的HashMap
数据结构有以下类似的点:- 确定索引位置: 键首先使用哈希算法算出哈希值,再和数组的
长度-1
做取余操作,确定存放数组的下标。 - 解决hash冲突: 两个键值计算的索引一致,采用
链表法
,将多个节点通过next
指针连在一起。
- 确定索引位置: 键首先使用哈希算法算出哈希值,再和数组的
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK