手机版
你好,游客 登录 注册
背景:
阅读新闻

Linux内核哈希表分析与应用

[日期:2013-01-17] 来源:CSDN  作者:tigerjb [字体: ]

前言:
1.基本概念:
散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

2. 常用的构造散列函数的方法
散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数,数据元素将被更快地定位。散列表的常用构造方法有:
 (1)直接定址法
 (2)数字分析法
 (3)平方取中法
 (4)折叠法
 (5)随机数法
 (6)除留余数法

3、处理冲突的方法
  散列表函数设计好的情况下,可以减少冲突,但是无法完全避免冲突。常见有冲突处理方法有:
  (1)开放定址法
  (2)再散列法
  (3)链地址法(拉链法)
  (4)建立一个公共溢出区

4. 散列表查找性能分析
 散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到,另一些关键码在散列函数得到的地址上产生了冲突,需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中,产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以,对散列表查找效率的量度,依然用平均查找长度来衡量。
  查找过程中,关键码的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。影响产生冲突多少有以下三个因素:
  1. 散列函数是否均匀;
  2. 处理冲突的方法;
  3. 散列表的装填因子。


  散列表的装填因子定义为:α= 填入表中的元素个数 / 散列表的长度。
  α是散列表装满程度的标志因子。由于表长是定值,α与“填入表中的元素个数”成正比,所以,α越大,填入表中的元素较多,产生冲突的可能性就越大;α越小,填入表中的元素较少,产生冲突的可能性就越小。实际上,散列表的平均查找长度是装填因子α的函数,只是不同处理冲突的方法有不同的函数。

一.Linux内核哈希表数据结构
hash最重要的是选择适当的hash函数,从而平均的分配关键字在桶中的位置,从而优化查找 插入和删除所用的时间。然而任何hash函数都会出现冲突问题。内核采用的解决哈希冲突的方法是:拉链法拉链法解决冲突的做法是:将所有关键字为同义词的结点链接在同一个链表中。若选定的散列表长度为m,则可将散列表定义为一个由m个头指针(struct hlist_head name)组成的指针数组T[0..m-1]。凡是散列地址为i的结点,均插入到以T[i]为头指针的链表中。T中各分量的初值均应为空指针。在拉链法中,装填因子α(装填的元素个数/数组长度)可以大于 1,但一般均取α≤1。当然,用拉链法解决hash冲突也是有缺点的,指针需要额外的空间。

1. 其代码位于include/linux/list.h中,3.0内核中将其数据结构定义放在了include/linux/types.h中
哈希表的数据结构定义:
如图:


struct  hlist_head{
 struct hlist_node *first;
}
struct  hlist_node {
        struct hlist_node *next,**pprev;
}
1>hlist_head表示哈希表的头结点。哈希表中每一个entry(list_entry)所对应的都是一个链表(hlist).hlist_head结构体只有一个域,即first。First指针指向该hlist链表的第一个结点。
2>hlist_node结构体有两个域,next和pprev。
(1)next指向下个hlist_node结点,倘若改结点是链表的最后一个节点,next则指向NULL
(2)pprev是一个二级指针,它指向前一个节点的next指针。

2.Linux 中的hlist(哈希表)和list是不相同的,在list中每个结点都是一样的,不管头结点还是其它结点,使用同一个结构体表示,但是在hlist中,头结点使用的是struct hlist_head来表示的,而对于其它结点使用的是strcuct hlist_node这个数据结果来表示的。还有list是双向循环链表,而hlist不是双向循环链表。因为hlist头结点中没有prev变量。为什么要这样设计呢?
散列表的目的是为了方便快速的查找,所以散列表通常是一个比较大的数组,否则“冲突”的概率会非常大,这样就失去了散列表的意义。如何来做到既能维护一张大表,又能不占用过多的内存呢?此时只能对于哈希表的每个entry(表头结点)它的结构体中只能存放一个指针。这样做的话可以节省一半的指针空间,尤其是在hash bucket很大的情况下。(如果有两个指针域将占用8个字节空间)

3.hlist的结点有两个指针,但是pprev是指针的指针,它指向的是前一个结点的next指针,为什么要采用pprev,二不采用一级指针?
由于hlist不是一个完整的循环链表,在list中,表头和结点是同一个数据结构,直接用prev是ok的。在hlist中,表头中没有prev,只有一个first。
1>为了能统一地修改表头的first指针,即表头的first指针必须修改指向新插入的结点,hlist就设计了pprev。list结点的pprev不再是指向前一个结点的指针,而是指向前一个节点(可能是表头)中的next(对于表头则是first)指针,从而在表头插入的操作中可以通过一致的node->pprev访问和修改前结点的next(或first)指针。
2>还解决了数据结构不一致,hlist_node巧妙的将pprev指向上一个节点的next指针的地址,由于hlist_head和hlist_node指向的下一个节点的指针类型相同,就解决了通用性。

linux
相关资讯       Linux内核分析  哈希表 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直��或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款