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

Linux内核数据结构 散列表

1、散列表数据结构

  • 在Linux内核中,散列表(哈希表)使用非常广泛。本文将对其数据结构和核心函数进行分析。和散列表相关的数据结构有两个:hlist_headhlist_node

    //hash桶的头结点
    struct hlist_head {struct hlist_node *first;//指向每一个hash桶的第一个结点的指针
    };
    //hash桶的普通结点
    struct hlist_node {struct hlist_node *next;//指向下一个结点的指针struct hlist_node **pprev;//指向上一个结点的next指针的地址
    };
    
  • 对应的结构如下
    在这里插入图片描述

    • hash_table 为散列表(数组),其中的元素类型为 struct hlist_head 。以 hlist_head 为链表头的链表,其中的节点hash值是相同的(也叫冲突)。first指针指向链表中的节点①,然后节点①的 pprev 指针指向 hlist_head 中 的 first ,节点①的 next 指针指向节点②,以此类推。
    • hash_table 的列表头仅存放一个指针,也就是 first 指针,指向的是对应链表的头结点,没有tail指针,也就是指向链表尾节点的指针,这样的考虑是为了节省空间——尤其在 hash bucket (数组size)很大的情况下可以节省一半的指针空间。
    • pprev是一个二级指针, 它指向前一个节点的next指针的地址 。为什么我们需要这样一个指针呢?它的好处是什么?
      • 哈希表的目的是为了方便快速的查找,所以哈希表中hash桶的数量通常比较大,否则“冲突”的概率会非常大,这样也就失去了哈希表的意义。如何做到既能维护一张大表,又能不使用过多的内存呢?就只能从数据结构上下功夫了。所以对于哈希表的每个hash桶,它的结构体中只存放一个指针,解决了占用空间的问题。现在又出现了另一个问题:数据结构不一致。显然,如果hlist_node采用传统的nextprev指针,对于第一个节点和后面其他节点的处理会不一致。hlist_node巧妙地将pprev指向上一个节点的next指针的地址,由于hlist_headfirst域指向的结点类型和hlist_node指向的下一个结点的结点类型相同,这样就解决了通用性!
      • 下面讲解结点相关操作的时候会有更详细的解释。

2、散列表删除结点

  • 如果要删除hash桶对应链表中的第一个普通结点
    在这里插入图片描述对应的程序代码如下:

    static inline void __hlist_del(struct hlist_node *n) 
    { struct hlist_node *next = n->next;//获取指向第二个普通结点的指针 struct hlist_node **pprev = n->pprev;//保留待删除的第一个结点的pprev域(即头结点first域的地址),此时 pprev = &first *pprev = next; /*因为pprev = &first,所以*pprev = next,相当于 first = next即将hash桶的头结点指针指向原来的第二个结点,如上图中的黑线1*/if (next) //如果第二个结点不为空next->pprev = pprev;//将第二个结点的pprev域设置为头结点first域的地址,如上图中的黑线2 
    }
    
  • 如果要删除hash桶对应链表中的非第一个结点
    在这里插入图片描述对应的程序代码如下:

    static inline void __hlist_del(struct hlist_node *n) 
    { struct hlist_node *next = n->next;//获取指向待删除结点的下一个普通结点的指针 struct hlist_node **pprev = n->pprev;//获取待删除结点的pprev域 *pprev = next; //修改待删除结点的pprev域,逻辑上使待删除结点的前驱结点指向待删除结点的后继结点,如上图中的黑线1if (next) //如果待删除结点的下一个普通结点不为空next->pprev = pprev;//设置下一个结点的pprev域,如上图中的黑线2,保持hlist的结构 
    }
    

    可以看到删除第一个普通结点和删除非第一个普通结点的代码是一样的。

  • 下面再来看看如果hlist_node中包含两个分别指向前驱结点和后继结点的指针。
    在这里插入图片描述很明显删除hash桶对应链表中的非第一个普通结点,只需要如下两行代码:

    n->next->prev = n->prev;
    n->prev->next = n->next;
    

    可是,如果是删除的hash桶对应链表中的第一个普通结点:此时 n->prev->next = n->next 就会出问题,因为hash桶的表头结点没有next域,所以,明显在这种情况下删除hash桶对应链表的第一个普通结点和非第一个普通结点的代码是不一样的。 同理结点插入操作也存在同样的问题。

相关文章:

Linux内核数据结构 散列表

1、散列表数据结构 在Linux内核中,散列表(哈希表)使用非常广泛。本文将对其数据结构和核心函数进行分析。和散列表相关的数据结构有两个:hlist_head 和 hlist_node //hash桶的头结点 struct hlist_head {struct hlist_node *first…...

数据库系统课设——基于python+pyqt5+mysql的酒店管理系统(可直接运行)--GUI编程

几个月之前写的一个项目,通过这个项目,你能学到关于数据库的触发器知识,python的基本语法,python一些第三方库的使用,包括python如何将前后端连接起来(界面和数据),还有界面的设计等…...

《C和指针》笔记9: typedef

C语言支持一种叫作typedef的机制,它允许你为各种数据类型定义新名字。typedef声明的写法和普通的声明基本相同,只是把typedef这个关键字出现在声明的前面。例如,下面这个声明: char *ptr_to_char;把变量ptr_to_char声明为一个指向…...

《C和指针》笔记6:gets/puts/scanf/printf/getchar函数用法

本博客可以了解一些gets/puts/scanf/printf/getchar函数的基本用法。 文章目录 1. gets函数2. puts函数3. scanf函数4. printf函数5. getchar函数6. putchar函数 1. gets函数 gets函数从标准输入读取一行文本并把它存储于作为参数传递给它的数组中。一行输入由一串字符组成&a…...

智慧课堂学生行为检测评估算法

智慧课堂学生行为检测评估算法通过yolov5系列图像识别和行为分析,智慧课堂学生行为检测评估算法评估学生的表情、是否交头接耳行为、课堂参与度以及互动质量,并提供相应的反馈和建议。智慧课堂学生行为检测评估算法能够实时监测学生的上课行为&#xff0…...

rainbond云原生应用管理平台部署

rainbond简介 rainbond 是 一个 开源的Kubernetes 云原生应用管理平台。 Rainbond 核心100%开源,Serverless体验,不需要懂K8s也能轻松管理容器化应用,平滑无缝过渡到K8s,是国内首个支持国产化信创、适合私有部署的一体化应用管理…...

jemter连接数据json断言

文章目录 一、jmeter连接数据库1、加载JDBC驱动2、连接数据3、SQL Query的Query Type使用方法:4、Variable Name使用方法:5、Result variable name使用方法: 二、Json响应断言1、添加 》 断言 》 JSON断言2、JSON断言界面参数说明&#xff1a…...

JavaFX 加载 fxml 文件

JavaFX 加载 fxml 文件主要有两种方式,第一种方式通过 FXMLLoader 类直接加载 fxml 文件,简单直接,但是有些控件目前还不知道该如何获取,所以只能显示,目前无法处理。第二种方式较为复杂,但是可以使用与 fx…...

(三)Redis——Set

SADD key value SMEMBERS 127.0.0.1:6379> SADD set aaa 1 127.0.0.1:6379> SMEMBERS set aaa 127.0.0.1:6379> SADD set aaa 0 127.0.0.1:6379> SMEMBERS set aaaSISMEMBER 判断 aaa 是否在 set 中 127.0.0.1:6379> SISMEMBER set aaa 1 127.0.0.1:6379>…...

Vue组件通信方式详解(全面版)

在Vue应用开发中,组件通信是一个重要的话题。不同的组件可能需要在不同的情况下进行数据传递和交互。Vue提供了多种方式来实现组件通信,每种方式都有其适用的场景。本文将详细介绍Vue中实现组件通信的各种方式,并为每种方式提供通俗易懂的代码…...

什么是Promise对象?它的状态有哪些?如何使用Promise处理异步操作?以及 async、await

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ Promise对象⭐ 创建Promise对象⭐ 使用Promise处理异步操作⭐ async、await⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅…...

Android 之自定义绘制一

绘制的基本要素 onDraw(Canvas) 绘制方法 Canvas 绘制工具 Paint 调整风格 粗细等 坐标系: x y ,3D 会有z轴,x 左到右,y 上至下,与数学中y颠倒 尺寸单位: 布局中 dp ,sp ,代码中 px;dp 为了适配不同的尺寸 绘制的关键: draw(Canvas )......(关键类:Paint) Paint.ANTI_A…...

vue3 计算两个表单得到第三个表单数据

<el-formref"ruleFormRef"label-width"150px"label-suffix":":rules"rules":disabled"drawerProps.isView":model"drawerProps.rowData"><el-form-item label"云平台名称" prop"cloudId&…...

Premiere Pro软件安装包分享(附安装教程)

目录 一、软件简介 二、软件下载 一、软件简介 Adobe Premiere Pro&#xff0c;简称PR&#xff0c;是Adobe公司开发的一款非线性视频编辑软件&#xff0c;被广泛应用于电影、电视剧、广告、纪录片、独立电影和音乐会等影视制作领域。它被公认为是行业内的标准工具&#xff0c…...

springboot设置文件上传大小,默认是1mb

问题排查和解决过程 之前做了个项目&#xff0c;需要用到文件上传&#xff0c;启动项目正常&#xff0c;正常上传图片也正常&#xff0c;但这里图片刚好都小于1M&#xff0c;在代码配置文件里面也写了配置&#xff0c;限制大小为500M&#xff0c;想着就没问题&#xff08;测试…...

Unity 之transform.LookAt() 调整一个物体的旋转,使其朝向指定的位置

文章目录 总的介绍补充&#xff08;用于摄像机跟随的场景&#xff09; 总的介绍 transform.LookAt 是 Unity 引擎中 Transform 组件的一个方法&#xff0c;用于调整一个物体的旋转&#xff0c;使其朝向指定的位置。通常情况下&#xff0c;它被用来使一个物体&#xff08;如摄像…...

linux————haproxy

一、概述 HAProxy是一个免费的负载均衡软件&#xff0c;可以运行于大部分主流的Linux操作系统上&#xff08;CentOS、Ubuntu、Debian、OpenSUSE、Fedora、麒麟、欧拉、UOS&#xff09;。 HAProxy提供了L4(TCP)和L7(HTTP)两种负载均衡能力&#xff0c;具备丰富的功能。HAProxy具…...

【80天学习完《深入理解计算机系统》】第十天 3.3 条件码寄存器【CF ZF SF OF】【set】

专注 效率 记忆 预习 笔记 复习 做题 欢迎观看我的博客&#xff0c;如有问题交流&#xff0c;欢迎评论区留言&#xff0c;一定尽快回复&#xff01;&#xff08;大家可以去看我的专栏&#xff0c;是所有文章的目录&#xff09;   文章字体风格&#xff1a; 红色文字表示&#…...

使用WSL修改docker文件存储位置

按照以下说明将其重新定位到其他驱动器/目录&#xff0c;并保留所有现有的Docker数据。 首先&#xff0c;右键单击Docker Desktop图标关闭Docker桌面&#xff0c;然后选择退出Docker桌面&#xff0c;然后&#xff0c;打开命令提示符&#xff1a; wsl --list -v您应该能够看到&a…...

软件设计师学习笔记6-存储系统

1.层次化存储体系 1.1层次化存储结构 局部性原理是层次化存储结构的支持 时空局部性&#xff1a;刚被访问的内容&#xff0c;立即又被访问(eg: 循环体 ) 空间局部性&#xff1a;刚被访问的内容&#xff0c;临近的空间很快被访问(eg:数组) 1.2层次化存储结构的分类 DRAM&…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...