哈希链表及其相关操作

有必要温习一遍内核中对于hash链表的定义和相关重要操作：

 499 struct hlist_head {
 500 struct hlist_node *first;
 501 };//hash表表头

 503 struct hlist_node {
 504 struct hlist_node *next, **pprev;
 505 };//hash链表表节点

哈希链表的初始化：

 507 #define HLIST_HEAD_INIT { .first = NULL }
 508 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
 509 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
 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链表遍历的宏：

 675 #define hlist_for_each_entry(tpos, pos, head, member) \
 676 for (pos = (head)->first; \
 677 pos && ({ prefetch(pos->next); 1;}) && \
 678 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 679 pos = pos->next)
 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 无话可说；