当前课程知识点：Linux 内核分析与应用 > 第1章 概述 > 1.4 源码分析-内核中的哈希表 > Video
在前面陈老师带领我们学习了内核中的双链表
在内核中还有一个独特的专门用于
哈希表的链表结构hlist
今天呢就让我们一同来学习一下
在我们开始阅读源码之前呢 我们需要先回顾一下哈希表的相关概念
哈希表是我们在数据结构中学习过的一种非常重要的用于查找的数据结构
它的基本思想是将关键字和其存储位置之间建立起一种映射关系
我们称之为哈希函数 通过哈希函数我们可以实现在时间复杂度O(1)下查找数据
而在实际的应用过程中常常有一种现象
对于两个相同的关键字呢经过哈希函数的运算后
它们具有同样的哈希地址如果我们对这种情况不
特殊处理的话也就意味着这两个不同的关键字将会被存储在同一个位置上
这显然是不合适的这种现象我们称之为冲突现象
在哈希表中解决冲突是一个非常重要的问题 那么如何解决哈希表的冲突呢
常见的方法有这么几种 开放寻址法 再散列法还有链地址法
而今天我们着重讲的就是链地址法
它的基本思想是将具有相同哈希地址的记录链成一个链表
m个哈希地址呢 就有m个链表
然后用一个数组 将这M个链表的头节点的存储起来 形成一个动态的结构
之所以复习哈希表的知识 因为我们今天要学习的hlist呢
就是内核为我们提供了一个用于实现哈希表链地址法的一个数据结构
好了让我们现在进入源码
我这次使用的内核版本是2.6版本的
低等级的版本的代码比较简单 也比较适合我们初学者
首先呢我们来看
哈希表相关的源码在这样一个路径下include\linux\list.h文件中
打开这个文件呢我们就会发现它是分为两部分的
前一部分呢都是以list为前缀命名的代码
他们是双链表相关的源码
我们往下翻找到了以hlist为前缀命名的这部分
源码呢就是我们要找的哈希表相关的源码了
hlist是一种链表结构
只不过是专门用于实现哈希表中的链地址法的
它比起常规的双链表的略有不同
首先我们来看看内核中用于实现hlist的两个数据结构
一个是hlist_head
它是链表的头节点
它有一个指向第一个链表体结构的first指针
另一个就是链表体结构hlist_node了
它包含一个指向其后继节点的next指针
特别的是它还包含一个二级指针pprev
这就是与我们常见的双链表的不同之处了
阅读hlist相关代码的关键也在于此
我们只要弄清楚了这个二级指针的指向
便可以画出hlist链表的结构图
结合着图呢再分析hlist相关的操作的函数就能简便不少
所以为了搞清楚这个二级指针的指向
我们需要从其他的代码中获取线索
首先看到了这4个宏从名字上我们就可以看出来前三个宏是对于头节点
进行初始化的宏 第4个宏呢是对于
hlist_node节点初始化的宏
接下来的这个函数hlist_unhashed
从名字和其返回值我们就可以分析得出
它是判断一个hlist_node型的节点是否经过哈希的
如果该节点没有经过哈希那么其
指针域pprev应当是初始化时候赋予的空
那么其返回的值就应当为true了
接着这个函数hlist_empty
它需要传入的参数是一个hlist_head型的节点
从它的返回值我们也可以分析的出
该函数是对于一个
头节点判断其
所链接的链表是否为空的如果
该头节点所链的链表为空 那么自然其first指针域呢
就应当为空 返回值就是true了
前面这两个函数都没有提到对于
二级指针pprev的操作 所以我们还需要再接着往下看
接下来的这个函数叫做hlist_del
看到这个函数的名字我立马想起来
在双链表之中也有一个类似的函数叫做list_del
它的功能是从双链表中删除一个节点的
而它所要做的就是修改
其后继结点的前驱指针和其前驱结点的后继指针
好了结合着这个函数的功能 我们大胆的猜测hlist_del
它是一个对于哈希链表节点进行删除操作的函数
现在我们来分析一下它的执行过程首先呢它的
传入的参数是一个指向hlist_node型的指针n
它第一步先用一个一级指针next保存
当前节点的next指针域
用一个二级指针pprev保存当前节点的pprev指针域
接着呢它将next指针赋值给了*pprev
在分析这一句语句之前呢我这里要暂停一下
在这里我插一段有关于二级指针的概念 一级指针我们都见的比较多也比较熟悉
它指向的是某个变量 也就是说一级指针中存储的是某个变量的地址
而二级指针 简单的来说就是一个指向指针的指针
二级指针中存储的是某个一级指针的地址
如图所示的A是二级指针 B是一级指针 C是一个变量
先来看B 它是一个指向变量C的一级指针
它通过存储变量C的地址来达到指向变量C的目的
而A呢 是一个指向指针B的二级指针
它通过存储指针B的地址来达到指向指针B的目的
接着是有关于指向操作 我们知道对于一个
一级指针进行一次指向操作 就相当于间接的引用
这个指针指向的一个变量
同理呢 对于一个二级指针进行一次指向操作
就相当于间接的引用
它指向的那个一级指针了 而对于一个二级指针进行两次指向操作
就相当于对它指向的一级指针
所指向的那个变量的间接引用
在复习了二级指针的概念之后 我们回过头来再看看代码
*pprev就是对于二级指针pprev的一次指向操作
也就是对于pprev二级指针所指向的那个一级指针的间接引用
该语句将next指针赋值给了该一级指针
接着呢是一个判断当next指针不为空的情况下
也就是当前节点的后继节点存在的情况下 将pprev指针
赋值给了当前结点后继结点的pprev指针域
该函数的关键的两句就是它们了
为了分析它们我们需要来看一张图
这里我们先回忆一下 对于一个双链表之中
节点删除操作的过程
上面这两个是一个双链表的结构
我们要删除中间这个节点 我们要做的呢
是修改其前驱结点的
next指针域让其指向其后继节点
修改其后继结点的pre指针域让其指向当前结点的前驱结点
这样做是为了保证我们在删除中间这个节点之后我们的双链表结构仍然是连续的
而hlist它同样是个链表应当也遵循这样的原则
下面这两个图是一个hlist的
链表结构我们让pprev指针域先指向一个未知的x指针
们如果要删除中间这个节点 我们要做的首先当然是修改其前驱节
节点的next指针域 让其指向当前节点的后继节点
而我们回过头来再看看代码
*pprev就是对于pprev指针的一次指向操作 也就是对于
x指针的间接引用
而next指针则保存的是指向后继结点的指针
我们将next指针赋给*pprev就完成了
如图上所示的这样一个连线
看到这里呢我们
其实都可以想到了这个x指针 应当就是当前节点前驱
结点的next指针 因为只有这样呢
我们才能保证我们在删除中间节点之后的我们的
hlist链表仍然是连续的
所以最后一步我们自然也可以分析得出
后继节点存在的情况下让后继结点的
pprev指针域指向
当前节点前驱节点的next指针域也就是
该语句所完成的操作了
经过刚刚的分析 我们对hlist_node节点中的二级指针
pprev已经有了一个清楚的认识
我们现在可以将hlist的链表的结构图画出来了
结合图将刚刚的删除节点操作再过一遍
一来是验证我们的分析是否正确 二来可以加深印象
如图所示从左到右依次是A B C
三个hlist_node节点它们链成了一个链表
其中的pprev指针是指向前驱结点的next指针的一个二级指针
我们现在要做的是将中间节点node_b从这个链表中删除
首先我们用pprev和next
这两个变量的将node_b
节点中的同名指针保存起来
接着我们要做的就是修改
其前驱结点node_a中的next指针 让其指向其后继结点node_c也就是这个语句
pprev我们知道就是对二级指针pprev的一次指向操作
即相当于对于pprev指针指向的一级指针也就是node_a中的next指针进行操作
而next变量中保存的即是node_c的地址
我们将其赋值给node_a中的next指针
即将图中这条线连接了起来
而最后我们需要对其后继节点node_c中的
pprev指针进行修改 让其指向其前驱节点node_a中的
next指针 我们在pprev变量中保存的即是
node_a的next指针的地址
将其复制给由next变量取得的node_c节点的
pprev指针域也就是将图中这条连线
连接了起来 到此我们便可以放心的删除node_b了
删除node_b之后我们的链表依然是连续的
这里是完整的由内核提供的hlist所构成的哈希表的结构图
包含了由hlist_head组成的数组
它之中保存的是指向每个链表第一个节点的指针
和由hlist_node构成的链表 它其中可以保存产生冲突的各个关键字
剩余的hlist相关的源码 大家可以结合这张图来阅读
另外hlist中的一些代码的与双链表中的代码也是比较类似的
大家可以相互参照着看
剩余的源码就留给各位同学来分析了
最后呢我们还剩了一个问题
就是为何hlist_node中需要有这个二级指针pprev
那么Linux内核这样设计肯定是有它的道理的 我们先来一同分析一下
首先我们试一下直接将这个二级指针去掉看可以吗
我们将二级指针去掉之后 那么hlist呢
就成了一个单链表的结构
那么hlist这个单链表的结构仍然可以将这些产生冲突的关键词串联起来
这是没有问题的
但是对于一个单链表进行
操作就会有一些麻烦了
插入操作还好说 我们可以采用头插法插入在
这个位置
时间复杂度也是为O(1)的 但是如果我们要删除某一个特定的节点呢
我们需要修改其前驱结点的next指针
而没有了二级指针pprev我们就只能从头来遍历一遍链表
才能找到其前驱结点
所以这无疑增加了删除操作的时间复杂度
所以直接删除这个二级指针
并不是一个合适的选择
那么我们可以看看将这个二级指针换成一个一级指针可以吗
我们将这个二级指针改成一个指向其前驱节点的一级指针
也就是说将hlist的链表结构改成一个双链表
的确呢对于双链表可以很方便的进行插入和删除的操作
而且list.h中也有现成的函数和宏我们可以直接使用
但是我们对比一下hlist和list就能发现
它们两个最大的区别就是在节点的定义上
在双链表中的结构体只有一个也就是节点list_head
而在hlist中则有两种类型的节点
一个是hlist_head 一个是hlist_node
假设呢我们的hlist_node呢
它其中有一个指向其前驱结点的prev指针
那么这个指向其前驱结点的prev指针它肯定指向的
节点类型应该是hlist_node类型
但是如果我们使用这个指针
是一个头节点类型的节点
我们就会发现必须对这个指针进行一次
强制的类型转换
那么这样一来呢
每次进行操作的时候我们都需要判断其指向的那个节点的类型
这将使我们的代码变得很复杂
所以采用双链表的也不是一个很好的选择
那我们这里还剩最后一种选择也就是将
hlist_head也改成hlist_node
将它们的节点类型统一起来
的确这样一改之后便不再有上述的那些麻烦了
但是我们这里又产生了一个新的问题
我们的头节点需要这个
prev指针吗也就是指向其前驱的指针吗
哈希表的头节点是不需要存放数据的
只用来指向相应的链表
我们现在给它增加了一个无用的指针 就相当于将其占用的空间足足提高了一倍
而哈希表中的头结点的数量呢
与数据的总量是在一个数量级上的
这将会造成巨大的空间上的浪费
所以综上所述 内核所采用的hlist_node
的设计它既可以保证头结点中呢
只保留一个有用的指针 不造成空间上的浪费
又可以使对于链表的插入和删除操作的时间复杂度都为O(1）
无疑是一个非常优秀的设计
这也是我们在阅读内核源码时所要学习的 也就是内核的设计思路
好了 今天的分享就到这里了 谢谢大家
-1.1 Linux操作系统概述
-1.2 Linux内核结构以及内核模块编程
--Video
-1.3 Linux内核源码中的双链表结构
--Video
-1.4 源码分析-内核中的哈希表
--Video
-1.5 动手实践-Linux内核模块的插入和删除
--Video
-第1章 概述--章节测验
-2.1 内存管理之内存寻址
--Video
-2.2 段机制
--Video
-2.3分页机制
--Video
-2.4 动手实践-把虚拟地址转换成物理地址
--Video
-第2章 内存寻址--章节测验
-3.1 进程概述
--Video
-3.2 Linux进程创建
--Video
-3.3 Linux进程调度
--Video
-3.4 动手实践-打印进程描述符task_struct中的字段
--Video
-3.5工程实践-基于内核模块的负载监控
--Video
-第3章 进程管理--章节测验
-4.1 Linux内存管理机制
--Video
-4.2 进程用户空间管理机制
--Video
-4.3 物理内存分配与回收机制（上）
--Video
-4.4 物理内存分配与回收机制（下）
--Video
-4.5 动手实践-Linux内存映射基础（上）
--Video
-4.6 动手实践-Linux内存映射实现（中）
--Video
-4.7 动手实践-Linux内存映射测试（下）
--Video
-4.8 初学者对内存管理的常见疑惑
-第4章 内存管理--章节测验
-5.1 中断机制概述
--Video
-5.2 中断处理机制
--Video
-5.3 中断下半部处理机制
--Video
-5.4 时钟中断机制
--Video
-5.5 动手实践-中断上半部的代码分析及应用
--Video
-5.6 动手实践-中断下半部的代码分析及应用
--Video
-第5章 中断--章节测验
-6.1 Linux中的各种API
--Video
-6.2 系统调用机制
--Video
-6.3 动手实践-添加系统调用（系统调用日志收集系统）
--Video
-第6章 系统调用--章节测验
-7.1 内核同步概述
--Video
-7.2 内核同步机制
--Video
-7.3 动手实践-内核多任务并发实例（上）
--Video
-7.4 动手实践-内核多任务并发实例（下）
--Video
-第7章 内核同步--章节测验
-8.1 虚拟文件系统的引入
--Video
-8.2 虚拟文件系统的主要数据结构
--Video
-8.3 文件系统中的各种缓存
--Video
-8.4 页高速缓存机制以及读写
--Video
-8.5 动手实践-编写一个文件系统（上）
--Video
-8.6 动手实践-编写一个文件系统（中）
--Video
-8.7 动手实践-编写一个文件系统（下）
--Video
-第8章 文件系统--章节测验
-9.1 设备驱动概述
--Video
-9.2 I/O空间管理
--Video
-9.3 设备驱动模型
--Video
-9.4 字符设备驱动程序简介
--Video
-9.5 块设备驱动程序简介
--Video
-9.6 动手实践-编写字符设备驱动程序
--Video
-9.7工程实践-编写块设备驱动的基础（上）
--Video
-9.8 工程实践-块设备驱动程序分析（中）
--Video
-9.9 工程实践-块设备驱动程序实现（下）
--Video
-第9章 设备驱动--章节测验
-致谢与说明
--Video
