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

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

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> …...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]

报错信息&#xff1a;libc.so.6: cannot open shared object file: No such file or directory&#xff1a; #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...