Redis底层数据结构-Dict
1. Dict基本结构
Redis的键与值的映射关系是通过Dict来实现的。
Dict是由三部分组成,分别是哈希表(DictHashTable),哈希节点(DictEntry),字典(Dict)
哈希表结构如下图所示:由于会发生哈希冲突,所以entry个数可能会大于size
size总是2的n次方
哈希节点的结构如下图所示:
当我们向Dict添加键值对时,Redis首先根据key计算出hash值(h),然后利用h&sizemask(其实就是h对数组长度取余)计算元素应该存储到数组中哪个索引位置
建立一个哈希表,以及哈希节点,数组【1】中存入的是dictEntry的地址
如果遇到哈希冲突之后,就会进行头插法将新插入的节点放入首节点位置(因为新放入的数据预计会在较近的时间被访问,其次头插法的时间复杂度低)
dictEntry中的key和value大部分都是指针,指向String类型的对象
Dict(字典)的结构如下图所示:核心是dictht ht【2】用于在rehash时
所以整体Dict结构如下图所示:
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,流程如下:
- 计算新hash表的size,值取决于当前要做的是扩容还是收缩
- 如果是扩容,则新size为第一个大于等于dict.ht[0].used+1的2^n
- 如果是收缩,则新size为第一个大于等于dict.ht[0].used的2^n(不得小于4)
- 按照新的size申请内存空间,创建dictht,并赋值给dict.ht[1]
- 设置dict.rehashidx=0,标示开始rehash
- 每次执行新增,查询,修改,删除操作时(也就是说每次访问dict时执行一次rehash),都检查一下dict.rehashidx是否大于-1,如果是,则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1],并且将rehashidx++,直到dict.ht[0]的所有数据都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最终为空
相关文章:

Redis底层数据结构-Dict
1. Dict基本结构 Redis的键与值的映射关系是通过Dict来实现的。 Dict是由三部分组成,分别是哈希表(DictHashTable),哈希节点(DictEntry),字典(Dict) 哈希表结构如下图所…...

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

CTF下加载CTFtraining题库以管理员身份导入 [HCTF 2018]WarmUp,之后以参赛者身份完成解题全过程
-------------------搭建CTFd------------------------------ 给大家介绍一个本地搭建比较好用的CTF比赛平台:CTFD。 CTFd是一个Capture The Flag框架,侧重于易用性和可定制性。它提供了运行CTF所需的一切,并且可以使用插件和主题轻松进行自…...

机器学习每周挑战——信用卡申请用户数据分析
数据集的截图 # 字段 说明 # 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原生库的封装,它提供了大量的计算机视觉和图像处理的功能。要使用OpenCvSharp实现透视变换(Perspective Transformation),你首先需要理解透视变换的原理和它在图像处理…...

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

https访问http的minio 图片展示不出来
问题描述:请求到的图片地址单独访问能显示,但是在网页中展示不出来 原因:https中直接访问http是不行的,需要用nginx再转发一下 nginx配置如下(注意:9000是minio默认端口,已经占用,…...
【Python整理】 Python知识点复习
1.Python中__init__()中声明变量必须都是self吗? 在Python中的类定义里,init() 方法是一个特殊的方法,称为类的构造器。在这个方法中,通常会初始化那些需要随着对象实例化而存在的实例变量。使用 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
人工智能技术的飞速发展正在深刻改变着我们的工作和生活方式。作为一名资深的技术爱好者,我最近有幸体验了备受瞩目的AI助手Claude-3。这款由Anthropic公司推出的新一代智能工具展现出了非凡的实力,尤其在图像识别和专业写作领域的表现更是让人眼前一亮&…...
Mac 如何彻底卸载Python 环境?
第一步:首先去应用程序文件夹中,删除关于Python的所有文件; 第二步:打开terminal终端,输入下面命令查看versions下有哪些python版本; ls /library/frameworks/python.framework/versions第三步࿱…...

Vue 大文件切片上传实现指南包会,含【并发上传切片,断点续传,服务器合并切片,计算文件MD5,上传进度显示,秒传】等功能
Vue 大文件切片上传实现指南 背景 在Web开发中,文件上传是一个常见的功能需求,尤其是当涉及到大文件上传时,为了提高上传的稳定性和效率,文件切片上传技术便显得尤为重要。通过将大文件切分成多个小块(切片࿰…...

【VUE+ElementUI】el-table表格固定列el-table__fixed导致滚动条无法拖动
【VUEElementUI】el-table表格固定列el-table__fixed导致滚动条无法拖动 背景 当设置了几个固定列之后,表格无数据时,点击左侧滚动条却被遮挡,原因是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
接下来,我讲介绍一下v-text和v-html的使用方式以及它们之间的区别。 使用方法 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-widt…...
学习笔记——C语言基本概念结构体共用体枚举——(10)
1、结构体 定义新的数据类型: 数据类型:char short int long float double 数组 指针 结构体 结构体: 新的自己定义的数据类型 格式: struct 名字{ 成员 1; 成员 2; 。 。 。 …...
VMware虚拟机三种网络模式
VMware虚拟机提供了三种主要的网络连接模式,它们分别是: 桥接模式(Bridged Mode)网络地址转换模式(NAT Mode)仅主机模式(Host-Only Mode) 1. 桥接模式(Bridged Mode&am…...

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

Windows下Docker搭建Flink集群
编写docker-compose.yml 参照: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…...

网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...

iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
Vue 模板语句的数据来源
🧩 Vue 模板语句的数据来源:全方位解析 Vue 模板(<template> 部分)中的表达式、指令绑定(如 v-bind, v-on)和插值({{ }})都在一个特定的作用域内求值。这个作用域由当前 组件…...
es6+和css3新增的特性有哪些
一:ECMAScript 新特性(ES6) ES6 (2015) - 革命性更新 1,记住的方法,从一个方法里面用到了哪些技术 1,let /const块级作用域声明2,**默认参数**:函数参数可以设置默认值。3&#x…...
TCP/IP 网络编程 | 服务端 客户端的封装
设计模式 文章目录 设计模式一、socket.h 接口(interface)二、socket.cpp 实现(implementation)三、server.cpp 使用封装(main 函数)四、client.cpp 使用封装(main 函数)五、退出方法…...
Python第七周作业
Python第七周作业 文章目录 Python第七周作业 1.使用open以只读模式打开文件data.txt,并逐行打印内容 2.使用pathlib模块获取当前脚本的绝对路径,并创建logs目录(若不存在) 3.递归遍历目录data,输出所有.csv文件的路径…...