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

Redis数据结构与对象-链表和字典

1、链表

其实个人感觉redis的链表内容和其他的差不多。就是一个listNode结构,里面又指向前置节点和后置节点的指针。
然后redis链表可以保存各种不同类型的值。
链表被广泛用于实现redis的各种功能,比如列表键、发布与订阅、慢查询、监视器等。

2、字典

字典又称为符号表、关联数组、映射。是一种保存键值对的抽象数据结构。从作用上来说,我理解就是java 里面的hashMap。
在redis中被广泛用于实现各种功能,其中包括数据库和字段。

2.1、字典的底层实现

字典底层实现是哈希表,哈希表里面又包含哈希表节点。

2.1.1 哈希表

哈希表结构定义如下:

typedef struct dictht{//哈希表数组dictEntry **table;//哈希表大小unsigned long size;//哈希表大小掩码,用于计算索引值//总是等于size-1unsigned long sizemask;//该哈希表已有的节点的数量unsigned long used;
}dictht;

其中table 属性是一个数组,每个元素的类型是 dictEntry。每个dictEntry 保存一个键值对。

2.1.2 哈希表节点

用dictEntry 表示。

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

key保存键, v保存值。值可以是uint64_t 或者 int64_t 整数。
next指向另一个哈希表节点的指针,用来解决hash冲突。(是不是和java里面的hashmap很像呀~)

2.1.3 字典

redis中的字典结构如下:

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

type属性和privdata属性,为创建多态字典而设置。不用管,一般不用了解。
ht属性是一个数字,长度为2,类型是dictht,就是哈希表。ht[0]的哈希表平时会用到;h[1]的哈希表只有在对h[0]进行rehash时才会用到。另外还有rehashidx也和rehash有关。

2.2、哈希算法

其实就是根据key计算hash值和索引值,然后根据索引值把新的键值对的哈希表节点放到哈希表对应的位置上,
Redis使用MurmurHash2算法计算哈希值。
那么关键的问题来了,如何解决键冲突?

2.3、解决键冲突

两个或两个以上的键分配到同一个索引上面,如何解决?
redis采用链地址法。节点有next指针,能成为一条链。采用头插法。

2.4、rehash

哈希表中的键值对可能新增或者减少,那么表的容量也需要随之调整。

2.4.1、rehash何时对哈希表执行rehash操作?

扩展操作执行时机:

  1. 服务器目前没有在执行BGSAVE或者BGREWRITEAOF命令,并且哈希表负载因子>=1
  2. 服务器目前正在执行BGSAVE或者BGREWRITEAOF命令,并且哈希表负载因子>=5

负载因子=哈希表已保存的节点数量 / 哈希表大小

收缩操作执行:负载因子小于等于0.1

2.4.2、 如何进行rehash

rehash步骤:
1、为字典ht[1]分配空间,空间大小取决于ht[0]当前包含的键值对数量(ht[0].used)1.1. 扩展操作,空间大小 = 第一个大于等于 ht[0].used*2 的 2的n次幂。比如 ht[0].used =5,那么5*2=10,第一个大于10的2的n次幂是16,那么h[1]扩展为16.1.2. 收缩操作,h[1]大小  =第一个大于等于ht[0].used的2的n次幂。例如现在 ht[0].used =5,那么8是第一个大于等于5的2的n次幂。h[1]大小为8.
2、将ht[0]的键值对rehash到ht[1].
3、ht[0]全部迁移到ht[1]之后,释放ht[0],设置ht[1]为ht[0]

2.5、 渐进式rehash

为了避免rehash对服务器性能造成影响,服务器不是一次性将ht[0]里面的所有键值对rehash到ht[1]。而是分多次、渐进式处理。
步骤如下:
1、为ht[1] 分配空间,字典此时同时持有ht[0] 和ht[1];
2、字典中维持一个索引计数器变量 rehashidx,设置为0,表示rehash正式开始;
3、在rehash期间,每次对字典执行增删改查操作时,会将ht[0]在rehashidx索引上的所有键值对rehash到ht[1],当rehash完成之后,rehashidx 加1;
4、最终ht[0]所有键值对都被rehash到ht[1]之后,rehashidx=-1,表示rehash操作已经完成。

相关文章:

Redis数据结构与对象-链表和字典

1、链表 其实个人感觉redis的链表内容和其他的差不多。就是一个listNode结构,里面又指向前置节点和后置节点的指针。 然后redis链表可以保存各种不同类型的值。 链表被广泛用于实现redis的各种功能,比如列表键、发布与订阅、慢查询、监视器等。 2、字典…...

学系统集成项目管理工程师(中项)系列08a_合同管理(上)

1. 合同(Contract) 1.1. 契约 1.2. 广义概念 1.2.1. 以确定各种权利与义务为内容的协议,即只要是当事人之间达成的确定权利义务的协议均为合同,不管它涉及哪个法律部门及何种法律关系 1.2.2. 合同除应包括民法中的合同外&…...

【Linux 裸机篇(四)】I.MX6ULL C语言 LED 驱动

文章目录 一、汇编搭建 C 语言环境二、C 语言编写三、编写 Makefile四、链接脚本 一、汇编搭建 C 语言环境 实际工作中是很少用到汇编去写嵌入式驱动的,大部分情况下都是使用 C 语言去编写的。只是在开始部分用汇编来初始化一下 C 语言环境,比如初始化 D…...

我也曾经因安装库而抓狂,直到我遇到了

入门教程、案例源码、学习资料、读者群 请访问: python666.cn 大家好,欢迎来到 Crossin的编程教室 ! 几乎所有的 Python 学习者都遇到过“安装”方面的问题。这些安装问题包括 Python 自身环境的安装、第三方模块的安装、不同版本的切换&…...

DDPG算法详解

DQN算法详解 一.概述 概括来说,RL要解决的问题是:让agent学习在一个环境中的如何行为动作(act), 从而获得最大的奖励值总和(total reward)。 这个奖励值一般与agent定义的任务目标关联。 agent需要的主要学习内容:第一是行为策略…...

继续学c++

由于c里面有很多和c语言很像的东西,这里就来总结一点不像的或者要注意的,或者是我已经快忘记的; 先来一个浮点型也就是实型类型的总结; 知道浮点型有这两个类型:float和double型; 然后float型占四个字节…...

Day949.遗留系统之殇:为什么要对遗留系统进行现代化? -遗留系统现代化实战

遗留系统之殇:为什么要对遗留系统进行现代化? Hi,我是阿昌,今天学习记录是关于遗留系统之殇:为什么要对遗留系统进行现代化?的内容。 不知道你是否跟曾经一样,身处一个遗留系统的漩涡之中&…...

DAY 45 Nginx服务配置

Nginx概述 Nginx: Nginx 是开源、高性能、高可靠的 Web 和反向代理服务器,而且支持热部署,几乎可以做到 7 * 24 小时不间断运行,即使运行几个月也不需要重新启动,还能在不间断服务的情况下对软件版本进行热更新。 对…...

如何收集K8S容器化部署的服务的日志?

做开发的同学都知道日志的重要性,日志的种类一般有接口日志、错误日志、关键步骤日志、用户操作日志等。本文主要详细讲解使用kubernetes容器化部署的服务该如何记录和收集日志。 一、使用标准输出方式 将想要记录的日志内容输出到stdout或stderr即可(…...

python删除csv文件中的某几列或行

1. 读取数据 用pandas中的read_csv()函数读取出csv文件中的数据: import pandas as pddf pd.read_csv("comments.csv") df.head(2)用drop函数进行文件中数据的删除行或者删除列操作。 2. 删除列操作 方法一:假设我们要删除的列的名称为 ‘观众ID’,‘…...

Redis持久化机制导致服务自启动后恢复数据过长无法使用以及如何关闭

场景 若依前后端分离版手把手教你本地搭建环境并运行项目: 若依前后端分离版手把手教你本地搭建环境并运行项目_霸道流氓气质的博客-CSDN博客 在上面搭建前后端分离的项目后,如果需要在windows服务上进行部署。 若依前后端分离版本,Windo…...

DAY 37 shell免交互

Here Document 概述 常用的交互程序:read,ftp,passwd,su,sudo cat也可配合免交互的方式重定向输出到文件 Here Document 的作用 使用I/O重定向的方式将命令列表提供给交互式程序标准输入的一种替代品 格式 命令 …...

用python脚本从Cadence导出xdc约束文件

用python脚本从Cadence导出xdc约束文件 概述转换方法先导出csv文件修改CSV文件 CSV转XDC检查输出XDC文件csv2xdc源代码下载 概述 在Cadence设计完成带有FPGA芯片的原理图的时候,往往需要将FPGA管脚和网络对应关系导入vivado设计软件中,对于大规模FPGA管…...

【C++ 六】内存分区、引用

内存分区、引用 文章目录 内存分区、引用前言1 内存分区模型1.1 程序运行前1.2 程序运行后1.3 new 操作符 2 引用2.1 引用基本使用2.2 引用注意事项2.3 引用做函数参数2.4 引用做函数返回值2.5 引用本质2.6 常量引用 总结 前言 本文包含内存分区、引用基本使用、引用注意事项、…...

markdown基本语法

来自神秘人儿的投稿! markdown的使用,可以参考https://markdown.com.cn/basic-syntax/ 标题:用 # 表示 段落:enter即可,两端之间有一个空行 换行:一行的末尾加两个或者多个空格,两端之间没有…...

第十篇 Spring 集成Redis

《Spring》篇章整体栏目 ————————————————————————————— 【第一章】spring 概念与体系结构 【第二章】spring IoC 的工作原理 【第三章】spring IOC与Bean环境搭建与应用 【第四章】spring bean定义 【第五章】Spring 集合注入、作用域 【第六章】…...

PADS-LOGIC项目原理图设计

最小板原理图设计 目录 1 菜单与工具使用 2 常用设置 2.1选项卡 2.2 图纸设置 2.3 颜色设置 3 设计技巧 3.1 模块化设计思路 3.2 元件放置 3.3 走线及连接符 4 原理图绘制 4.1 POWER原理图设计 4.2 MCU原理图设计 4.2.1晶振电路 4.2.2复位电路 4.2.3 BOOT电路 …...

36岁大龄程序员被裁,找了2个月工作,年包从100万降到50万,要不要接?

为了找到工作,你愿意接受降薪多少? 一位36岁的杭州程序员问: 36岁被裁,找了2个月工作,年包从100万降到50万,真心纠结,要不要接? 网友们分成了旗帜鲜明的两派,一派人认为不…...

Android Retrofit 源码分析

1、简介 Retrofit 是一种基于 Java 的 RESTful Web Service 客户端库,它可以将网络请求抽象出来并支持多种转换器,可以将 JSON、XML 和其他格式的响应数据自动转换为 Java 对象。Retrofit 通过注解的方式来描述 REST API 调用,使开发人员能够…...

CDN如何阻止网络攻击

随着网络技术的发展,网络攻击事件也越来越多,对企业和个人的安全和稳定造成严重威胁。为此,高防CDN应运而生,成为广大用户保障网络安全的重要工具。什么是高防CDN?高防CDN的特点有哪些?高防CDN如何阻止网络攻击?接下来让我们一…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...