LINUX-2.6内核支持双向循环链表外，还支持另一种双向链表，其与 list_head 有明显的不同，因为它不是循环的，这就是现在要讨论的内核中的哈希表，也叫散列表。对于散列表而言，重要的不是在固定的时间内找到表中的最末一个元素，而是空间。表头存放在 hlist_head 中，这个结构具体实现如下：
struct hlist_head
{
struct hlist_node *first;
};
可以看得出来，不像双向链表的实现，哈希表的表头结点只有一个成员，指向下一个结点（如果没有就为NULL），其余的节点的实现如下：
struct hlist_node
{
struct hlist_node *next;
struct hlist_node **pprev;
};
每个元素都是 hlist_node 类型的数据结构，她的next指针指向下一个元素，pprev指针指向前一个元素的next字段，因为不是循环链表，所以第一个元素的pprev字段和最后一个元素的next字段都置为NULL。
同样地，内核会把这样的数据结构嵌入到需要用散列表组织起来的结构体当中，比如进程管理，由于很多情况下，内核都需要从进程的PID导出对应的进程描述符指针。例如为kill 系统调用提供服务时就会发生这种情况：当进程p1希望向进程p2发送一个信号时，p1调用kill 系统调用，其参数为p2的PID，内核从这个PID导出其对应的进程描述符，然后从P2的进程描述符中取出记录挂起信号的数据结构指针。
为了提高效率，避免扫描进程链表来寻找指定的PID，2.6内核引入了4个散列表，它们分别用来处理进程的4个不同类型的ID： pid、tgid、pgrp和session。
我们来看看内核是怎么组织它们的，首先在进程描述中，包含了一个叫做pids的结构体数组：
struct pid pids[PIDTYPE_MAX]; // PIDTYPE_MAX 就是枚举常量4
其中结构体pid的定义是：
struct pid
{
/* Try to keep pid_chain in the same cacheline as nr for find_pid */
int nr;
struct hlist_node pid_chain;
/* list of pids with the same nr, only one of them is in the hash */
struct list_head pid_list;
};
内核用四个这样的结构体来实现针对不同的PID的散列存储，其中nr放的是相应进程的PID，这个PID的值通过相应的哈希映射（具体的算法是哈希地址 = (nr*0x9e370001) >> 21 ）得到一个哈希地址，再把这个计算出来的哈希地址存储在相应的哈希表上。pid_chain是当由pid计算出来的哈希地址冲突时，这些pid所在的进程描述符组成的一个双向链表。而pid_list是同一线程组的所有线程组成的双向循环链表，看看下面这幅图就明白了：
图中以TGID为例子，显示了其中几个进程的组织形式，从PID的数值计算出哈希地址，如果冲突，则将它们用struct hlist_node 类型的结构体连成一个双向链表，并将表头的 hlist_head 中的 fisrt 指针指向第一个进程描述符。然后我们还注意到，具有相同的PID 的一组线程，他们之间用 struct pid 中的 pid_list 连成了一个双向循环链表。（这样做的好处是，当内核需要向线程组发送消息的时候，这样的散列表可以由指定的PID号为内核返回所有的线程）。
当然，跟双向循环链表一样，内核也提供了很多对哈希表的操作函数和宏。
基本数据结构：
struct hlist_head
{
struct hlist_node *first;
};
struct hlist_node
{
struct hlist_node *next, **pprev;
};
下面是内核中对于哈希表的基本操作函数和宏：
1、初始化表头和节点的宏：
#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
#define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)
2、通过节点指针判断该节点是否被链进某哈希表链里：
static inline int hlist_unhashed(const struct hlist_node *h)
{
return !h->pprev;
}
3、通过表头指针判断该哈希表是否为空：
static inline int hlist_empty(const struct hlist_head *h)
{
return !h->first;
}
4、从哈希链表中删除节点指针 n 所指向的节点：
static inline void __hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next;
struct hlist_node **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
}
static inline void hlist_del(struct hlist_node *n)
{
__hlist_del(n);
n->next = LIST_POISON1;
n->pprev = LIST_POISON2;
}
附图：
5、删除节点并初始化之：
static inline void hlist_del_init(struct hlist_node *n)
{
if (n->pprev) {
__hlist_del(n);
INIT_HLIST_NODE(n);
}
}
6、在h所指向的哈希表头之后插入节点n：
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
struct hlist_node *first = h->first;
n->next = first;
if (first)
first->pprev = &n->next;
h->first = n;
n->pprev = &h->first;
}
附图：
7、在next所指向的节点之前插入n所指向的节点：
/* next must be != NULL */
static inline void hlist_add_before(struct hlist_node *n,
struct hlist_node *next)
{
n->pprev = next->pprev;
n->next = next;
next->pprev = &n->next;
*(n->pprev) = n;
}
附图：
注意，这个函数的第二个参数next必须不能为空指针，否则将出错。（因为代码对next进行了解引用）
8、在n所指向的节点后面插入next所指向的节点：
static inline void hlist_add_after(struct hlist_node *n,
struct hlist_node *next)
{
next->next = n->next;
n->next = next;
next->pprev = &n->next;
if(next->next)
next->next->pprev = &next->next;
}
附图：
以下是用到的一些宏的详细解释：
9、ptr是一个指向结构体type里面的member字段的一个指针，该宏的作用是返回一个指向整个结构体的指针。
#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
其中相关的另外的两个宏定义具体是：
#define container_of(ptr, type, member) ({ / const typeof(((type *)0)->member) *__mptr = (ptr); /
(type *)((char *)__mptr - offsetof(type, member)); })
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
首先，offsetof宏的作用是，返回结构体TYPE中字段MEMBER的偏移量，其巧妙的地方在于先把0转换为该结构体类型指针，再通过它来引用字段MEMBER，再取其地址，则这个地址就是字段MEMBER在结构体TYPE的相对于地址0的地址，实际上就是偏移量。
而宏container_of(ptr, type, member)则通过一个指向结构体type里面的member字段的一个指针，返回一个指向整个结构体的指针。其中定义一个__mptr指针来代替ptr是要防止当ptr有自加自减单目运算符时可能出现的副作用。（另外，整个宏的定义用的是语句表达式，这个GNU C的语法扩展，其整个表达式的值取决于最右边的那个表达式，因此container_of最终的值为指针__mptr - offsetof() 的值）。
具体看看这幅图就明白了：
10、这两个宏的功能都是通过表头指针head依次获得指向各个节点的指针pos。
#define hlist_for_each(pos, head) /
for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); /
pos = pos->next)
#define hlist_for_each_safe(pos, n, head) /
for (pos = (head)->first; pos && ({ n = pos->next; 1; }); /
pos = n)
首先，prefetch宏是一个空的实现，其值是1，因此for循环中的第二个表达式其实就等价于 pos。
其次，如果要删除pos所指向的节点，那么只能使用第二个宏hlist_for_each_safe(pos, n, head)，因为第一个宏在for循环的第三个表达式中对pos指针进行了解引用，如果pos所指向的节点已经被释放了这个操作就是非法的了。而safe版本的遍历不会有这个尴尬，因为用了一个中间变量n来暂时保存pos的next指针。
再强调一下，当我们要利用内核的哈希表实现自己的代码的时候，用到这两个宏来遍历我们的哈希链表的时候，记得：如果要遍历之后有删除的操作，一定要用safe版本。
11、以下这三个宏完成一样的功能：遍历哈希链表，并且获得其所在结构体的指针tpos。hlist_for_each_entry版本从表头开始遍历，而hlist_for_each_entry_continue版本从pos所指向的节点的下一个节点开始遍历，hlist_for_each_entry_from版本从pos所指向的那个节点开始遍历。
#define hlist_for_each_entry(tpos, pos, head, member) /
for (pos = (head)->first; /
pos && ({ prefetch(pos->next); 1;}) && /
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); /
pos = pos->next)
#define hlist_for_each_entry_continue(tpos, pos, member) /
for (pos = (pos)->next; /
pos && ({ prefetch(pos->next); 1;}) && /
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); /
pos = pos->next)
#define hlist_for_each_entry_from(tpos, pos, member) /
for (; pos && ({ prefetch(pos->next); 1;}) && /
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); /
pos = pos->next)
这两个宏的应用，同样要注意安全的问题，注意到for循环的第三个表达式都没有用到临时变量来保存pos的下一个指针变量，因此不能用这两个宏来遍历删除节点，要安全地遍历各个节点，需要用以下这个宏：
12、安全地从表头开始遍历各个节点。（这里的安全指的是遍历的过程可以删除该节点）
#define hlist_for_each_entry_safe(tpos, pos, n, head, member) /
for (pos = (head)->first; /
pos && ({ n = pos->next; 1; }) && /
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); /
pos = n)