Chinaunix首页 | 论坛 | 博客
  • 博客访问: 188266
  • 博文数量: 71
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 48
  • 用 户 组: 普通用户
  • 注册时间: 2013-09-27 14:13
个人简介

坐着,坐着,就胖了。。。

文章分类

全部博文(71)

文章存档

2014年(15)

2013年(56)

我的朋友

分类: LINUX

2013-12-20 15:10:55

声明:本文为原创
#####请转贴时保留以下内容######
作者GTT
本文档归属http://oldtown.cublog.cn/.转载请注明出处!
请提出宝贵意见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

阅读(1419) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~