有必要温习一遍内核中对于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 无话可说；