linux内核里面的双向循环链表和哈希链表有什么不同呢？1、双向循环链表是循环的，哈希链表不是循环的 2、双向循环链表不区分头结点和数据结点，都用list_head表示，而哈希链表区分头结点(hlist_head)和数据结点(hlist_node)。与哈希链表有关的两个数据结构如下：

struct hlist_head { 
    struct hlist_node *first;  //指向每一个hash桶的第一个结点的指针
}; 
struct hlist_node { 
    struct hlist_node *next;   //指向下一个结点的指针
    struct hlist_node **pprev; //指向上一个结点的next指针的指针
};

1、哈希链表为什么要区分头结点和数据结点？

头结点和数据结点如果都使用list_head的话，那岂不是更容易实现。内核list.h中描述得很明白：

/*
 * Double linked lists with a single pointer list head.
 * Mostly useful for hash tables where the two pointer list head is
 * too wasteful.
 * You lose the ability to access the tail in O(1).
 */

意思是说这种双向链表的头结点只有一个指针成员(即struct hlist_node *first)，它主要使用在哈希表中。因为哈希表会有很多表项，每个表项如果使用list_head这样含有两个指针成员的数据结构的话，会造成内存空间的浪费。所以，为了尽可能的减少内存空间的浪费，就要使数据结构变得稍微复杂一些，鱼和熊掌不可兼得啊。

2、hlist_node的pprev成员为什么是struct hlist_node **类型的？

如果hlist_node的定义是下面这样的话

struct hlist_node { 
    struct hlist_node *next;
    struct hlist_node *prev;
};

第一个数据结点的prev成员应该指向头结点，但是因为prev成员指向的是hlist_node的数据类型的指针，而头结点的数据类型是hlist_head，所以无法实现。为了解决这样的问题，才有了下面的hlist_node的定义

struct hlist_node { 
    struct hlist_node *next;
    struct hlist_node **pprev;
};

在上图中，第一个数据结点的pprev成员(数据类型struct hlist_node **)指向头结点的first成员(数据类型struct hlist_node *)，第二个数据结点的pprev成员(数据类型struct hlist_node **)指向第一个数据结点的next成员(数据类型struct hlist_node *)，从而对于第一个数据结点的操作和非第一个数据结点的操作就没有区别了，都统一起来了。这样就不用对第一个数据结点进行特殊处理了，为编写代码带来了极大的好处，这种设计有点小艺术。

其他的hlist的初始化、插入、删除、遍历请自行参阅list.h源文件，源文件是最好的老师。