Redis入门到通关之数据结构解析-Dict

本文涉及的产品
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
简介: Redis入门到通关之数据结构解析-Dict

概述


我们知道Redis是一个键值型(Key-Value Pair)的数据库,我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。

Dict由三部分组成,分别是:哈希表(DictHashTable)、哈希节点(DictEntry)、字典(Dict)

当我们向Dict添加键值对时,Redis首先根据key计算出hash值(h),然后利用 h & sizemask来计算元素应该存储到数组中的哪个索引位置。

我们存储k1=v1,假设k1的哈希值h =1,则1&3 =1,因此k1=v1要存储到数组角标1位置。


构成


Dict由三部分组成,分别是:哈希表(DictHashTable)、哈希节点(DictEntry)、字典(Dict)


Dict的扩容


Dict 中的 HashTable 就是数组结合单向链表的实现,当集合中元素较多时,必然导致哈希冲突增多,链表过长,则查询效率会大大降低。

Dict在每次新增键值对时都会检查负载因子(LoadFactor = used/size) ,满足以下两种情况时会触发哈希表扩容:

  • 哈希表的 LoadFactor >= 1,并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程;
  • 哈希表的 LoadFactor > 5 ;


Dict的rehash


不管是扩容还是收缩,必定会创建新的哈希表,导致哈希表的size和sizemask变化,而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新计算索引,插入新的哈希表,这个过程称为rehash。过程是这样的:

  • 计算新hash表的realeSize,值取决于当前要做的是扩容还是收缩:
  • 如果是扩容,则新size为第一个大于等于dict.ht[0].used + 1的2^n
  • 如果是收缩,则新size为第一个大于等于dict.ht[0].used的2^n (不得小于4)
  • 按照新的realeSize申请内存空间,创建dictht,并赋值给dict.ht[1]
  • 设置dict.rehashidx = 0,标示开始rehash
  • 将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1]
  • 将dict.ht[1]赋值给dict.ht[0],给dict.ht[1]初始化为空哈希表,释放原来的dict.ht[0]的内存
  • 将rehashidx赋值为-1,代表rehash结束
  • 在rehash过程中,新增操作,则直接写入ht[1],查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增,随着rehash最终为空

整个过程可以描述成:


总结


Dict的结构:

  • 类似java的HashTable,底层是数组加链表来解决哈希冲突
  • Dict包含两个哈希表,ht[0]平常用,ht[1]用来rehash

Dict的伸缩:

  • 当LoadFactor大于5或者LoadFactor大于1并且没有子进程任务时,Dict扩容
  • 当LoadFactor小于0.1时,Dict收缩
  • 扩容大小为第一个大于等于used + 1的2^n
  • 收缩大小为第一个大于等于used 的2^n
  • Dict采用渐进式rehash,每次访问Dict时执行一次rehash
  • rehash时ht[0]只减不增,新增操作只在ht[1]执行,其它操作在两个哈希表
相关文章
|
7天前
|
存储 NoSQL Java
【面试宝藏】Redis 常见面试题解析
Redis 是内存数据结构存储系统,用作数据库、缓存和消息中间件,支持字符串、哈希、列表等数据类型。它的优点包括高性能、原子操作、持久化和复制。相比 Memcached,Redis 提供数据持久化、丰富数据结构和发布/订阅功能。Redis 采用单线程模型,但通过 I/O 多路复用处理高并发。常见的面试问题涉及持久化机制、过期键删除、回收策略、集群和客户端等。
33 4
|
2天前
|
JavaScript 安全 前端开发
【Node.js】从入门到精通(一)—— fs 模块全解析
【Node.js】从入门到精通(一)—— fs 模块全解析
5 0
|
7天前
|
存储 缓存 NoSQL
【面试宝藏】Redis 常见面试题解析其二
Redis 高级面试题涵盖了哈希槽机制、集群的主从复制、数据丢失可能性、复制机制、最大节点数、数据库选择、连通性测试、事务操作、过期时间和内存优化等。Redis 使用哈希槽实现数据分布,主从复制保障高可用,异步复制可能导致写操作丢失。集群最大支持1000个节点,仅允许单数据库。可通过 `ping` 命令测试连接,使用 `EXPIRE` 设置过期时间,`MULTI/EXEC` 等进行事务处理。内存优化包括合理数据类型、设置过期时间及淘汰策略。Redis 可用作缓存、会话存储、排行榜等场景,使用 `SCAN` 查找特定前缀键,列表实现异步队列,分布式锁则通过 `SET` 命令和 Lua 脚本实现。
21 5
|
8天前
|
机器学习/深度学习 算法
数据结构入门 时间 空间复杂度解析
数据结构入门 时间 空间复杂度解析
8 0
|
9天前
|
存储 算法 大数据
深入解析力扣170题:两数之和 III - 数据结构设计(哈希表与双指针法详解及模拟面试问答)
深入解析力扣170题:两数之和 III - 数据结构设计(哈希表与双指针法详解及模拟面试问答)
|
9天前
|
存储 数据挖掘 数据处理
【python源码解析】深入 Pandas BlockManager 的数据结构和初始化过程
【python源码解析】深入 Pandas BlockManager 的数据结构和初始化过程
|
9天前
|
存储 算法 数据挖掘
数据结构面试常见问题:解锁10大关键问题及答案解析【图解】
数据结构面试常见问题:解锁10大关键问题及答案解析【图解】
|
10天前
|
存储 监控 NoSQL
Redis中的LRU淘汰策略深入解析
Redis的内存管理关键在于处理数据增长与有限内存的矛盾,LRU策略被广泛用于此。LRU基于“不常访问的数据未来访问可能性小”的假设,淘汰最近最少使用的数据。Redis通过双向链表实现,但并非严格LRU,而是采样算法以平衡性能和精度。用户可通过调整`maxmemory-samples`等参数优化。尽管LRU简单高效,但无法区分数据重要性和访问频率,可能误淘汰重要数据。合理设置参数、结合其他策略、监控调优是优化LRU使用的关键。
12 1
|
13天前
|
测试技术 C语言
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
13 1
|
5天前
数据结构——栈和队列
数据结构——栈和队列
8 1

热门文章

最新文章

推荐镜像

更多