散列表（又名哈希表）仅仅需要一个包含单一指针的链表头。它是双向链表的变体。它不同于双链表——表头和结点使用相同的结构体——散列表对表头和结点有不同的定义。如下：
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};散列表的实现一般采用hlist_head数组，每个hlist_head挂一个双向hlist_node链表，大致如下图。其中pprev它指向前一个结点的next指针。
1、初始化
1.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)1.2、初始化结点
static inline void INIT_HLIST_NODE(struct hlist_node *h)
{
h->next = NULL;
h->pprev = NULL;
}
2、逻辑判断
static inline int hlist_unhashed(const struct hlist_node *h)
{
return !h->pprev;
}
static inline int hlist_empty(const struct hlist_head *h)
{
return !h->first;
}
3、删除结点
3.1、内部API
static inline void __hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next;//(1)
struct hlist_node **pprev = n->pprev;//(2)
*pprev = next;//(3)
if (next)
next->pprev = pprev;//(4)
}
3.2、外部API
static inline void hlist_del(struct hlist_node *n)
{
__hlist_del(n);//(1)
n->next = LIST_POISON1;//(2)
n->pprev = LIST_POISON2;//(3)
}
static inline void hlist_del_init(struct hlist_node *n)
{
if (!hlist_unhashed(n)) {
__hlist_del(n);//(1)
INIT_HLIST_NODE(n);//(2)
}
}
4、添加结点
4.1、表头添加结点
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)（0）
{
struct hlist_node *first = h->first;//（1）
n->next = first;//（2）
if (first)
first->pprev = &n->next;//（3）
h->first = n;//（4）
n->pprev = &h->first;//（5）
}
在此基础上再次插入一个结点
4.2、指定结点之前添加结点
/* next must be != NULL */
static inline void hlist_add_before(struct hlist_node *n,
struct hlist_node *next)//(0)
{
n->pprev = next->pprev;//(1)
n->next = next;//(2)
next->pprev = &n->next;//(3)
*(n->pprev) = n;//(4)
}
4.3、指定结点之后添加结点
static inline void hlist_add_after(struct hlist_node *n,
struct hlist_node *next)//(0)
{
next->next = n->next;//(1)
n->next = next;//(2)
next->pprev = &n->next;//(3) if(next->next)
next->next->pprev = &next->next;//(4)
}
/* after that we'll appear to be on some hlist and hlist_del will work */
static inline void hlist_add_fake(struct hlist_node *n)
{
n->pprev = &n->next;
}
5、移动散列表
/*
* Move a list from one list head to another. Fixup the pprev
* reference of the first entry if it exists.
*/
static inline void hlist_move_list(struct hlist_head *old,
struct hlist_head *new)
{
new->first = old->first;//(1)
if (new->first)
new->first->pprev = &new->first;//(2)
old->first = NULL;//(3)
}