Chinaunix首页 | 论坛 | 博客
  • 博客访问: 513527
  • 博文数量: 168
  • 博客积分: 62
  • 博客等级: 民兵
  • 技术积分: 442
  • 用 户 组: 普通用户
  • 注册时间: 2011-04-30 11:45
文章分类

全部博文(168)

文章存档

2016年(2)

2015年(19)

2014年(98)

2013年(22)

2012年(6)

2011年(21)

分类:

2011-10-09 18:03:11

有必要温习一遍内核中对于hash链表的定义和相关重要操作:
     
  1.  499 struct hlist_head {
  2.  500 struct hlist_node *first;
  3.  501 };//hash表表头
     
  1.  503 struct hlist_node {
  2.  504 struct hlist_node *next, **pprev;
  3.  505 };//hash链表表节点

哈希链表的初始化:

     
  1.  507 #define HLIST_HEAD_INIT { .first = NULL }
  2.  508 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
  3.  509 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
  4.  510 #define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)

下面这张图包含了很多哈希链表的操作:具体的操作代码参见Source code吧。

(可以对照这张图看代码:)

 

 

 

hash最重要的是选择适当的hash函数,从而平均的分配关键字在桶中的位置,从而优化查找 插入和删除所用的时间。然而任何hash函数都会出现冲突问题。内核采用的解决哈希冲突的方法是:拉链法

拉链法解决冲突的做法是:将所有关键字为同义词的结点链接在同一个链表中。若选定的散列表长度为m,则可将散列表定义为一个由m个头指针(struct hlist_head name)组成的指针数组T[0..m-1]。凡是散列地址为i的结点,均插入到以T[i]为头指针的链表中。T中各分量的初值均应为空指针。在拉链法中,装填因子α(装填的元素个数/数组长度)可以大于 1,但一般均取α≤1。

当然,用拉链法解决hash冲突也是有缺点的,指针需要额外的空间。

下面说明一下关于内核函数中经常用到的hash链表遍历的宏:

     
  1.  675 #define hlist_for_each_entry(tpos, pos, head, member) \
  2.  676 for (pos = (head)->first; \
  3.  677 pos && ({ prefetch(pos->next); 1;}) && \
  4.  678 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
  5.  679 pos = pos->next)
  6.  680

其实展开之后就是for(xxx;xxx;xxx)语句....

1)初始化条件:pos = (head)->first 指向第一个hash链表节点的指针

2)测试条件:({ prefetch(pos->next); 1;})//这个表达式的值永远为1

          ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); //这个表达式的值也永远为1,但是这里tpos指向了hlist_node所在的宿主结构。

测试条件只是:检测pos指针是否为空的同时,把tpos指向的hlist_node所在的宿主结构。同时预先取得指向下一个hlist_node的指针值。

3)步长:pos = pos ->next 无话可说;

 

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