Redis(十)-Redis的数据结构之字典

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: 字典的数据结构其实完全可以类比Java中的HashMap数据结构,两者都是哈希表。

前言

字典的数据结构其实完全可以类比Java中的HashMap数据结构,两者都是哈希表。

字典

简介说明

字典,又称为符号表 ,关联数组或映射。是一种用于保存键值对(key-value pair)的抽象数据结构。字典中的每个键都是唯一的,通过键来更新值,或者根据键来删除整个键值对等等。字典在Redis中的应用相当广泛,比如Redis的数据库就是使用字典作为底层实现的。对数据库的增、删、查、改操作也是构建在对字典的操作之上的。

字典的实现

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

哈希表

哈希表的数据结构定义如下:

typedef struct dictht
{
         //哈希表数组,C语言中,*号是为了表明该变量为指针,有几个* 号就相当于是几级指针,这里是二级指针,理解为指向指针的指针
         dictEntry **table;
         //哈希表大小
         unsigned long size;
         //哈希表大小掩码,用于计算索引值
         unsigned long sizemask;
         //该哈希已有节点的数量
         unsigned long used;
}dictht;

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

2.size属性记录了哈希表的大小,也即table数组的大小。

3.used属性则记录哈希表目前已有节点(键值对)的数量。

4.sizemask属性的值总是等于size-1(从0开始),这个属性和哈希值一起决定一个键应该被放在table数组的那个索引上面。

下图表示一个空的哈希表的结构图

e92f2ad573b99a517ebb82d7cd2f0f0f_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1MzQ4MDg=,size_16,color_FFFFFF,t_70.png

哈希表节点

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

typedef struct dictEntry
{
         //键
         void *key;
         //值
         union{
           void *val;
            uint64_tu64;
            int64_ts64;
            }v;
         // 指向下个哈希表节点,形成链表
         struct dictEntry *next;
}dictEntry;

key属性保存着键值中的键,而v属性则保存着键值对中的值,键值(v属性)可以是一个指针,或uint64_t整数,或int64_t整数。next属性是指向另一个哈希表节点的指针,可以将多个哈希值相同的键值对连接在一起。以此来解决键冲突的问题。

字典

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

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

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

type属性是一个指向dictType结构的指针,每个dictType结构保存了一簇用于操作特定类型键值对的函数。Redis会为用途不同的字典设置不同的类型特定函数。

privdata属性则保存了需要传给那些类型特定函数的可选参数。

typedef struct dictType
{
         //计算哈希值的函数 
         unsigned int  (*hashFunction) (const void *key);
         //复制键的函数
         void *(*keyDup) (void *privdata,const void *key);
         //复制值的函数
         void *(*keyDup) (void *privdata,const void *obj);
          //复制值的函数
         void *(*keyCompare) (void *privdata,const void *key1, const void *key2);
         //销毁键的函数
         void (*keyDestructor) (void *privdata, void *key);
         //销毁值的函数
         void (*keyDestructor) (void *privdata, void *obj);
}dictType;

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

rehashidx记录了rehash目前的进度,如果目前没有进行rehash,值为-1。

哈希算法

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

Redis计算哈希值和索引值的方法如下:

#使用字典设置的哈希函数,计算键key的哈希值
hash=dict->type->hashFunction(key);
#使用哈希表的sizemask属性,计算出索引值
#根据情况不同,ht[x]可以是ht[0]或者ht[1]
index=hash&dict->ht[x].sizemask;

当字典被用作数据库的底层实现,或者哈希键的底层实现时,Redis使用MurmurHash2算法来计算键的哈希值。

解决键冲突(链表法)

当有两个或者以上数量的键被分配到了哈希表数组的同一个索引上面时,我们称这些键发生了冲突的。

Redis使用链表法解决哈希冲突,每个哈希表节点都有一个next指针,多个哈希表节点next可以用next指针构成一个单向链表,被分配到同一个索引上的多个节点可以使用这个单向链表连接起来。如下图所示:

d5fb074022beb98776ed17d819e00286_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1MzQ4MDg=,size_16,color_FFFFFF,t_70.png

如图所示,当键k0和k1经过哈希函数得到的索引值都是1时,就会使用next指针将连个节点(使用节点的好处是不需要辅助变量去获得链表的长度信息)连接起来。而由于节点没有指向链尾的指针,因此新的节点总是插入到链表的头部,排在已有节点的前面。

Redis rehash

随着操作的进行,哈希表中保存的键值对会逐渐的增多或者减少,程序需要对哈希表的大小进行相应的扩展或者收缩。

扩展和收缩哈希表的工作可以通过执行rehash(重新散列)来完成,Redis对字典的哈希表执行rehash的步骤如下:

1.为字典的ht[1]哈希表分配空间,哈希表大小取决于要执行的操作,以及ht[0]当前包含的键值对数量(也即是ht[0].used属性的值)

如果,执行的是扩展操作,那么ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方幂。

如果执行的是收缩操作,那么ht[1]的大小为第一个大于等于ht[0].used的2的n次方幂。

2.将保存在ht[0]中的所有键值对rehash到ht[1]上面;rehash指的是重新计算键的哈希值和索引值。然后将键值对放置到ht[1]哈希表的指定位置上。

3.当ht[0]包含的所有键值对都迁移到了ht[1]之后(ht[0]变为空表)释放ht[0],将ht[1]设置为ht[0],并在ht[1]新创建一个空白哈希表,为下一次rehash做准备。

总结

本文简单的介绍了Redis中的字典的数据结构, 她是通过哈希表节点来存储键值信息,通过链表法来处理键冲突。

参考

https://www.cnblogs.com/hunternet/p/9989771.html

《Redis设计与实现》

相关文章
|
21天前
|
消息中间件 缓存 NoSQL
Redis各类数据结构详细介绍及其在Go语言Gin框架下实践应用
这只是利用Go语言和Gin框架与Redis交互最基础部分展示;根据具体业务需求可能需要更复杂查询、事务处理或订阅发布功能实现更多高级特性应用场景。
151 86
|
2月前
|
存储 缓存 NoSQL
【📕分布式锁通关指南 12】源码剖析redisson如何利用Redis数据结构实现Semaphore和CountDownLatch
本文解析 Redisson 如何通过 Redis 实现分布式信号量(RSemaphore)与倒数闩(RCountDownLatch),利用 Lua 脚本与原子操作保障分布式环境下的同步控制,帮助开发者更好地理解其原理与应用。
103 0
|
3月前
|
存储 缓存 NoSQL
Redis核心数据结构与分布式锁实现详解
Redis 是高性能键值数据库,支持多种数据结构,如字符串、列表、集合、哈希、有序集合等,广泛用于缓存、消息队列和实时数据处理。本文详解其核心数据结构及分布式锁实现,帮助开发者提升系统性能与并发控制能力。
|
21天前
|
存储 缓存 NoSQL
Redis基础命令与数据结构概览
Redis是一个功能强大的键值存储系统,提供了丰富的数据结构以及相应的操作命令来满足现代应用程序对于高速读写和灵活数据处理的需求。通过掌握这些基础命令,开发者能够高效地对Redis进行操作,实现数据存储和管理的高性能方案。
61 12
|
20天前
|
存储 消息中间件 NoSQL
【Redis】常用数据结构之List篇:从常用命令到典型使用场景
本文将系统探讨 Redis List 的核心特性、完整命令体系、底层存储实现以及典型实践场景,为读者构建从理论到应用的完整认知框架,助力开发者在实际业务中高效运用这一数据结构解决问题。
|
29天前
|
存储 缓存 NoSQL
【Redis】 常用数据结构之String篇:从SET/GET到INCR的超全教程
无论是需要快速缓存用户信息,还是实现高并发场景下的精准计数,深入理解String的特性与最佳实践,都是提升Redis使用效率的关键。接下来,让我们从基础命令开始,逐步揭开String数据结构的神秘面纱。
|
11月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
223 59
|
4月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
52 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。