当前位置: 首页 > news >正文

Redis底层数据结构-Dict

1. Dict基本结构


Redis的键与值的映射关系是通过Dict来实现的。

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

哈希表结构如下图所示:由于会发生哈希冲突,所以entry个数可能会大于size
size总是2的n次方
![[Pasted image 20240402160110.png]]

哈希节点的结构如下图所示:
![[Pasted image 20240402160316.png]]

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

建立一个哈希表,以及哈希节点,数组【1】中存入的是dictEntry的地址
![[Pasted image 20240402161433.png]]

如果遇到哈希冲突之后,就会进行头插法将新插入的节点放入首节点位置(因为新放入的数据预计会在较近的时间被访问,其次头插法的时间复杂度低)
![[Pasted image 20240402161629.png]]

dictEntry中的key和value大部分都是指针,指向String类型的对象

Dict(字典)的结构如下图所示:核心是dictht ht【2】用于在rehash时
![[Pasted image 20240402161714.png]]

所以整体Dict结构如下图所示:
![[Pasted image 20240402162000.png]]

2. Dict渐进式rehash


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

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

  • 哈希表的LoadFactor>=1,并且服务器并没有执行BGSAVE或者BGREWRITEAOF等后台进程
  • 哈希表的LoadFactor>=5;
    Dict除了扩容以外,每次删除元素时,也会对负载因子做检查,当LoadFactor<0.1时&&size>4,会做哈希表收缩

Dict的rehash并不是一次性完成的,如果Dict中包含数百万的entry,要在依次rehash完成,极有可能导致主线程阻塞。因此Dict的rehash是分多次,渐进式的完成,因此称为渐进式rehash,流程如下

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

相关文章:

Redis底层数据结构-Dict

1. Dict基本结构 Redis的键与值的映射关系是通过Dict来实现的。 Dict是由三部分组成&#xff0c;分别是哈希表&#xff08;DictHashTable&#xff09;&#xff0c;哈希节点&#xff08;DictEntry&#xff09;&#xff0c;字典&#xff08;Dict&#xff09; 哈希表结构如下图所…...

Python基于深度学习的人脸识别项目源码+演示视频,利用OpenCV进行人脸检测与识别 preview

​ 一、原理介绍 该人脸识别实例是一个基于深度学习和计算机视觉技术的应用&#xff0c;主要利用OpenCV和Python作为开发工具。系统采用了一系列算法和技术&#xff0c;其中包括以下几个关键步骤&#xff1a; 图像预处理&#xff1a;首先&#xff0c;对输入图像进行预处理&am…...

CTF下加载CTFtraining题库以管理员身份导入 [HCTF 2018]WarmUp,之后以参赛者身份完成解题全过程

-------------------搭建CTFd------------------------------ 给大家介绍一个本地搭建比较好用的CTF比赛平台&#xff1a;CTFD。 CTFd是一个Capture The Flag框架&#xff0c;侧重于易用性和可定制性。它提供了运行CTF所需的一切&#xff0c;并且可以使用插件和主题轻松进行自…...

机器学习每周挑战——信用卡申请用户数据分析

数据集的截图 # 字段 说明 # Ind_ID 客户ID # Gender 性别信息 # Car_owner 是否有车 # Propert_owner 是否有房产 # Children 子女数量 # Annual_income 年收入 # Type_Income 收入类型 # Education 教育程度 # Marital_status 婚姻状况 # Housing_type 居住…...

Vulnhub:WESTWILD: 1.1

目录 信息收集 arp nmap nikto whatweb WEB web信息收集 dirmap enm4ulinux sumbclient get flag1 ssh登录 提权 横向移动 get root 信息收集 arp ┌──(root㉿ru)-[~/kali/vulnhub] └─# arp-scan -l Interface: eth0, type: EN10MB, MAC: 0…...

[C#]winform使用OpenCvSharp实现透视变换功能支持自定义选位置和删除位置

【透视变换基本原理】 OpenCvSharp 是一个.NET环境下对OpenCV原生库的封装&#xff0c;它提供了大量的计算机视觉和图像处理的功能。要使用OpenCvSharp实现透视变换&#xff08;Perspective Transformation&#xff09;&#xff0c;你首先需要理解透视变换的原理和它在图像处理…...

C++——list类及其模拟实现

前言&#xff1a;这篇文章我们继续进行C容器类的分享——list&#xff0c;也就是数据结构中的链表&#xff0c;而且是带头双向循环链表。 一.基本框架 namespace Mylist {template<class T>//定义节点struct ListNode{ListNode<T>* _next;ListNode<T>* _pre…...

https访问http的minio 图片展示不出来

问题描述&#xff1a;请求到的图片地址单独访问能显示&#xff0c;但是在网页中展示不出来 原因&#xff1a;https中直接访问http是不行的&#xff0c;需要用nginx再转发一下 nginx配置如下&#xff08;注意&#xff1a;9000是minio默认端口&#xff0c;已经占用&#xff0c;…...

【Python整理】 Python知识点复习

1.Python中__init__()中声明变量必须都是self吗? 在Python中的类定义里&#xff0c;init() 方法是一个特殊的方法&#xff0c;称为类的构造器。在这个方法中&#xff0c;通常会初始化那些需要随着对象实例化而存在的实例变量。使用 self 是一种约定俗成的方式来引用实例本身。…...

汽车电子行业知识:UWB技术及应用

文章目录 1.什么是UWB技术1.1.UWB测距原理1.2.UWB数据传输原理2.汽车UWB技术应用2.1.UWB雷达2.1.1.信道的冲击响应CIR2.2.舱外检测目标2.3.舱内检测活体2.3.1.活体检测原理2.4.脚踢尾箱开门2.4.1.脚踢检测原理1.什么是UWB技术 UWB(ultra wideband)也叫超宽带技术,是一种使用…...

Claude-3全解析:图片问答,专业写作能力显著领先GPT-4

人工智能技术的飞速发展正在深刻改变着我们的工作和生活方式。作为一名资深的技术爱好者&#xff0c;我最近有幸体验了备受瞩目的AI助手Claude-3。这款由Anthropic公司推出的新一代智能工具展现出了非凡的实力&#xff0c;尤其在图像识别和专业写作领域的表现更是让人眼前一亮&…...

Mac 如何彻底卸载Python 环境?

第一步&#xff1a;首先去应用程序文件夹中&#xff0c;删除关于Python的所有文件&#xff1b; 第二步&#xff1a;打开terminal终端&#xff0c;输入下面命令查看versions下有哪些python版本&#xff1b; ls /library/frameworks/python.framework/versions第三步&#xff1…...

Vue 大文件切片上传实现指南包会,含【并发上传切片,断点续传,服务器合并切片,计算文件MD5,上传进度显示,秒传】等功能

Vue 大文件切片上传实现指南 背景 在Web开发中&#xff0c;文件上传是一个常见的功能需求&#xff0c;尤其是当涉及到大文件上传时&#xff0c;为了提高上传的稳定性和效率&#xff0c;文件切片上传技术便显得尤为重要。通过将大文件切分成多个小块&#xff08;切片&#xff0…...

【VUE+ElementUI】el-table表格固定列el-table__fixed导致滚动条无法拖动

【VUEElementUI】el-table表格固定列el-table__fixed导致滚动条无法拖动 背景 当设置了几个固定列之后&#xff0c;表格无数据时&#xff0c;点击左侧滚动条却被遮挡&#xff0c;原因是el-table__fixed过高导致的 解决 在index.scss中直接加入以下代码即可 /* 设置默认高…...

重置gitlab root密码

gitlab-rails console -e production user User.where(id: 1).first user User.where(name: "root").first #输入重置密码命令 user.password"admin123!" #再次确认密码 user.password_confirmation"admin123!" #输入保存命令&am…...

v-text 和v-html

接下来&#xff0c;我讲介绍一下v-text和v-html的使用方式以及它们之间的区别。 使用方法 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-widt…...

学习笔记——C语言基本概念结构体共用体枚举——(10)

1、结构体 定义新的数据类型&#xff1a; 数据类型&#xff1a;char short int long float double 数组 指针 结构体 结构体&#xff1a; 新的自己定义的数据类型 格式&#xff1a; struct 名字{ 成员 1&#xff1b; 成员 2&#xff1b; 。 。 。 …...

VMware虚拟机三种网络模式

VMware虚拟机提供了三种主要的网络连接模式&#xff0c;它们分别是&#xff1a; 桥接模式&#xff08;Bridged Mode&#xff09;网络地址转换模式&#xff08;NAT Mode&#xff09;仅主机模式&#xff08;Host-Only Mode&#xff09; 1. 桥接模式&#xff08;Bridged Mode&am…...

Ai音乐大师演示(支持H5、小程序)独立部署源码

Ai音乐大师演示&#xff08;支持H5、小程序&#xff09;独立部署源码...

Windows下Docker搭建Flink集群

编写docker-compose.yml 参照&#xff1a;https://github.com/docker-flink/examples/blob/master/docker-compose.yml version: "2.1" services:jobmanager:image: flink:1.14.4-scala_2.11expose:- "6123"ports:- "18081:8081"command: jobma…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...