linux内核中的list.h文件中哈希表的分析

素颜马尾好姑娘i 2022-07-15 13:01 476阅读 0赞

一、背景

本篇文章将先从对哈希表的基本介绍开始，然后分析linux内核（3.10.0版）中的list.h文件中的哈希表。

二、简述哈希表

根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为哈希表。

上面这一段是从一本教材中摘抄出来的对哈希表的一段描述。

大家对数组的概念想必都不陌生，众所周知，数组通过数组号就可以找到对应的存储的数据。但数组的缺点也很明显，不便于增删数据。

大家对双向链表的概念也一定不陌生，双向链表比起数组，增删方便，但是查找数据就需要遍历整个链表，很费时费力。

如果可以有一个链表，既增添方便，也可以直接进行数据的访问而不必不断比较那就太好了。哈希表就是有类似这样的能力。

当然，我这样的说法并不严谨。但便于理解。

三、哈希函数的构造

可以想象，如果一个索引号对应着不止一个数据，那这时候就会有矛盾产生。到底对应着哪个数据呢？我们有必要构造哈希函数来使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。

常用构造哈希函数的方法有：（1）直接定址法  （2）数字分析法  （3）平方取中法  （4）折叠法  （5）除留余数法  （6）随机数法

具体的可以查阅相关资料。

四、处理冲突的方法

常用的处理冲突的方法有：（1）开放定址法  （2）再哈希法  （3）链地址法  （4）建立一个公共溢出区

具体的可以查阅相关资料。

五、list.h文件的哈希表的构造与实现分析

在linux kernel 3.10.0版本中，list.h位于include/linux目录下。

我们先来看一看list.h中哈希表的构造：

![20161121161805712][]

可以看到，linux内核处理冲突的方法是链地址法。思想是：将所有关键字为同义词的结点链接在同一个链表中。若选定的哈希表长度为m，则可将哈希表定义为一个由m个头指针组成的指针数组。就如上图所示。

在linux内核中定义哈希表头结点与结点的代码位于types.h文件中。

struct hlist\_head \{  
        struct hlist\_node \*first;

\};

struct hlist\_node \{

struct hlist\_node \*next, \*\*pprev;

\};

对源码分析如下：

1、初始化哈希表头结点

![20161121163413483][]

第一条宏定义只初始化头结点

第二条宏定义声明并初始化头结点

第三条宏定义使用指针初始化头结点，可在运行时进行初始化

2、初始化哈希表结点、检测结点是否未被哈希、检测哈希表是否为空

![20161121164042055][]

3、删除哈希结点

![20161121165003661][]

我在这里分析一下实现函数（第一个函数）：

S1:next是一个指向结构体struct hlist\_node的指针，在这里给它赋了一个初值n->next。这样，next就指向n的下一个结点。

S2:pprev是一个二级指针，指向指向结构体struct hlist\_node指针的指针，在这里给它赋了一个初值n->pprev。这样，pprev就指向上一个结点的next指针。

S3:将n下一个结点的地址赋给n上一个结点的next指针。这样，n上一个结点的next指针就不指向n了，而是指向n的下一个结点。

S4:如果n下一个结点为空，则结束。n下一个结点不为空，则将n下一个结点的pprev指向n上一个结点的next指针。

到此就结束了结点的删除操作。

第二个调用函数执行完删除操作后将分别指向了LIST\_POISON与LIST\_POISON2。以保证不在链表中的结点项不能被访问。

第三个调用函数先判断该结点是否被哈希，接着删除完后还要对该结点进行初始化。

第二和第三个调用函数在对n结点进行删除后的处理是不同的，前者是将n设置为了不可用，后者是对n进行了初始化。

4、添加哈希结点

![20161121174000761][]

（1）第一个函数将n结点添加在头结点h之后

（2）第二个函数将n结点添加在结点next之前，所以next结点一定不可以为NULL

（3）第三个函数将next结点插入到n结点之后

（4）第四个函数十分奇怪，它将自己的ppev指针指向自己的next指针，实现了虚假添加操作，这样的结点会被hlist\_unhashed判为已hash。所以也可以对它调用hlist\_del函数。

5、移动链表

![20161122094505076][]

此函数将本来以old为头结点的链表移动成为以new为头结点的链表。

6、链表结构体的入口

![20161123104804584][]

![20161123104846631][]

这两个宏定义由某链表的头结点获得该结构体的首地址。

其中第二个宏定义先对ptr进行判断，如果ptr是空指针，则返回NULL，如果其不是空指针才对其进行操作。

7、访问哈希链表

![20161129084053247][]

![20161129084112232][]

这里核心在于使用了container\_of函数，在哈希链表中访问我们需要的数据项。

第二个函数的操作更为安全，因为会在访问之前对ptr指针进行是否为空的判断。

8、遍历哈希链表

![20161123105508211][]

这两个宏定义对哈希链表进行遍历。第二个比第一个更安全一些。因为第二个在遍历时可以对pos进行删除操作。

使用第一个宏定义时则不可以删除pos，因为若在遍历时执行删除pos，会使pos->next无效而出错。

9、用链表外指针遍历哈希链表

![20161129094423442][]

我们可以看到，第一个函数是从链表头开始进行遍历。

第二个函数是从当前结点的下一个结点开始进行遍历。

第三个函数是从当前结点开始进行遍历。

而第四个函数可以在遍历过程中对当前结点进行删除操作，因为在对结点进行处理之前，结点的下一个指针信息已经被存储。

[20161121161805712]: /images/20220715/caac8dbaf0604c21ba19d78bb08a00d8.png
[20161121163413483]: /images/20220715/bf4bbaa3b3184d719dfef51a718cf02a.png
[20161121164042055]: /images/20220715/f43a7cd2a816474ba0f733951c69662b.png
[20161121165003661]: /images/20220715/11d5fb2c79004ebcb16752ddf4131b2d.png
[20161121174000761]: /images/20220715/44cce85f609a439cb6f3c706e1d8c7f8.png
[20161122094505076]: /images/20220715/f3b199c33bf3454fa7a3acb6a2bd3bdc.png
[20161123104804584]: /images/20220715/fa26f7237a50447d9c502f35f42132bf.png
[20161123104846631]: /images/20220715/b8bcba367a1f46688f1bc8e72b5c3fdc.png
[20161129084053247]: /images/20220715/244239104cea43958b89714fa78fcc9c.png
[20161129084112232]: /images/20220715/aa3facf58f8c479ebc8448ea7b7ed785.png
[20161123105508211]: /images/20220715/c23db5b2cf234b5180ef9d1e29fbe5a5.png
[20161129094423442]: /images/20220715/917389348d70463d8df841776d69d634.png