当前位置: 首页 > 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…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...