声明：本文为原创
#####请转贴时保留以下内容######
作者：GTT
请提出宝贵意见Mail:mtloveft@hotmail.com
Linux Version：2.6.33
提示：本文是介绍一些linux kernel 基础数据结构系列！
在讨论hash表实现前先看一个问题。就是前面的双向链表，如果有很多数据，遍历整个双向链表是很慢的。假设链表由n个元素，每个元素查找时间是t,那么查找的时间最坏的情况就是n*t。为了解决这个问题就有了hash表，每个元素的查找时间基本就是常数T.
什么是hash表
举个简单的例子
一个班级里如果所有的学生都链接在一个链表里，点名时岂不是很费劲。
如果按照名字分类，点名时可以少花费很多时间。
如果能把每个名字单独分一类，有很容易查找的话，那就最好了。
实际情况可能不可以，但计算机上是可以贴近一些。
比如，班上50名学生，先定义50个list_head
每个学生的名字的ASCII码总和在整除50,取余，
根据余数的大小，链接到对应的list_head里。
这样有一个好处，所有的查找时间都是固定的。想一想，如果
在全国范围内建个学生数据库，按照名字查找，如果是双向链表，那不得慢死。
如果有这个hash表，一下就快很多。当让还有重名的问题。
如果在把年龄也算到hash值里,就又可以细分以下了。
hash表的定义如下
先定义一个数组list_head[mask]
然后定义hash值得算法，因为要放到数组里，所以最后都和mask运算一下，比如整除取余等。
这样保证不会越界。直接和mask 做&运算也能保证不会数组越界的问题。
所以一般hash 表的mask都是hash表的长度。
以后根据算出的hash值，马上就能得到双向链表。
如果hash表足够大的话，查找时间就等于计算hash值得时间，基本是一个定值。
以上是利用list_head做hash表的表头，能得到双向链表。之后的增/删/合/移/查等操作就
是上一篇文章介绍的了。没什么好解释的了。
关键kernel又提供了一个hlist_head,它又是怎么回事呢？
hash表的原理明白了的话，数组list_head[mask]中list_head的大小为两个指针大小即8byte.
有人认为8byte是浪费，如果能减少为4byte，那岂不是更好，其实这是由需求的。在
一些嵌入式开发的硬件里，内存比较小，而hash表又很大，能减少一半岂不是美到家了。
所以就来了个hlist_head， 紧紧是减少了内存的使用量。其他的没有特别的。
以现在的计算机发展速度来看这都是鸟枪换大炮，浪费脑细胞。
定义如下
|
struct hlist_head {
struct hlist_node *first;
};
|
双向链表的结构如下
|
struct hlist_node {
struct hlist_node *next, **pprev;
};
|
而next指向下一节点元素的指针，而pprev指向上一节点元素的next指针的指针。
构成图如下
来看看hash表的遍历
|
#define hlist_for_each(pos, head) \
for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
pos = pos->next)
|
也就是根据hash值先找到hlist_head然后再用上面的遍历方法
进行遍历，突出条件就是pos 是NULL时退出
Kernel base Series(3)将介绍特殊的hash table hlist_nulls_head
阅读(541) | 评论(0) | 转发(0) |
