漫谈Linux内核哈希表(1)

关于哈希表，在内核里设计两个很重要的数据结构:
   哈希链表节点：

点击(此处)折叠或打开

1. /*Kernel Version : 3.4.x [include/linux/types.h]*/
   
2. struct hlist_node {
   
3.     struct hlist_node *next, **pprev;
   
4. };

    可以看到哈希节点和内核普通双向链表的节点唯一的区别就在于，前向节点pprev是个两级指针，至于为什么这样设计而不采用struct list_head{}来作为哈希链表的节点，我们后面会详细介绍。另外一个重要的数据结构是，哈希链表的表头。

   哈希链表表头：

点击(此处)折叠或打开

1. /*Kernel Version : 3.4.x [include/linux/types.h]*/
   
2. struct hlist_head {
   
3.     struct hlist_node *first;
   
4. };

    因为哈希链表并不需要双向循环的技能，它一般适用于单向散列的场景。所以，为了减少开销，并没有用struct hlist_node{}来代表哈希表头，而是重新设计struct hlist_head{}这个数据结构。此时，一个哈希表头就只需要4Byte了，相比于struct hlist_node{}来说，存储空间已经减少了一半。这样一来，在需要大量用到哈希链表的场景，其存储空间的节约是非常明显的，特别是在嵌入式设备领域。

   接下来，我们来重点回答一下哈希节点里那个两级指针的问题。先讲个小插曲，记得本人当年刚参加工作时，导师给安排了一个活儿，那时候年轻气盛、血气方刚，没一会儿功夫，三下五除二就搞定了。然后拿着自己的“杰作”去师傅看，师傅瞄了一眼说，你这函数简直是一坨shi(和乔老爷当年骂另外一个程序员的用词、语气差不多)，谁让你函数入参传个三级指针进去的？这段代码TM能维护么？谁看得懂？完了之后感觉自己还受了莫大的委屈一样，不过谁的人生没有那么点波澜壮阔的过往呢，就像有句名言说的：程序写出来是给人看的，顺带能在机器上运行。OK，那这个故事跟我们要介绍的哈希节点的关系在哪儿呢？没错，就是struct hlist_node{}里那个前向的两级指针的存在意义。

    关于两级指针的目的与意义，让我们采用反证法来看看，如果structhlist_node{}被设计成如下一级指针的样子，会发生什么：

点击(此处)折叠或打开

1. struct hlist_node {
   
2.     struct hlist_node *next, *pprev;
   
3. };

    假如我们现在已经有一个哈希链表了myhlist(先别管这个链表是怎么来的)，链表里有4个节点node1~node4：

    
   然后就有以下两个问题跟着冒出来：
   1)、在往哈希链myhlist里插入node1时必须这么写：

点击(此处)折叠或打开

1. mylist.first = node1;
   
2. node1->pprev=( struct hlist_node*)&mylist;

   除此之外，在插入node2~node4以及后续其他节点时(假如按顺序插入的话)，写法如下（X>=2）：

点击(此处)折叠或打开

1. node[X]->next = node[X+1];
   
2. node[X]->pprev = node[X-1];

简而言之啥意思呢？往哈希链表里插入元素时，如果在表头的第一个位置上插入元素，和插入在哈希链表的其他位置上的代码处理逻辑是不一样的。因为哈希表头是list_head类型，而其他节点都是list_node类型。

   2)、同样，如果删除节点时，对于非首节点，以node2为例：

点击(此处)折叠或打开

1. node2->pprev->next = node2->next;
   
2. node2->next->pprev = node2->pprev;

    如果要删除首节点node1呢，则写法如下：

点击(此处)折叠或打开

1. ((struct hlist_head*)(node1->pprev))->first = node1->next;
   
2. node1->next->pprev = ( struct hlist_node*)&mylist; 或者 node1->next->pprev = node1->pprev;

    很明显，内核开发者们怎么会容许这样的代码存在，而且还要充分考虑效率的问题。那么，当hlist_node.pprev被设计成两级指针后有啥好处？

    还是以删除节点为例，如果要删除首节点，因为node1->pprev里保存的是myhlist的地址，而myhlist.first永远都指向哈希链表的第一个节点，我们要间接改变表头里的hlist_node类型的first指针的值，能想到的最直接的办法当然是二级指针，这是两级指针的宿命所决定的，为了间接改变一级指针所指的内存地址的场景。这样一来，node节点里的pprev其实指向的是其前一个节点里的第一个指针元素的地址。对于hlist_head来说，它里面只有一个指针元素，就是first指针；而对于hlist_node来说，第一个指针元素就是next。具体如下所示：

所以，记住，当我们在代码中看到类似与*(hlist_node->pprev)这样的代码时，我们心里应该清楚，此时正在哈希表里操作当前节点前一个节点里的第一个指针元素所指向的内存地址，只是以间接的方式实现罢了。那么回到删除哈希链表节点的场景，当删除首节点时，此时情况就变成了：

点击(此处)折叠或打开

1. *(node1->pprev) = node1->next;
   
2. node1->next->pprev = node1->pprev;

    删除非首节点的情况也一样：

点击(此处)折叠或打开

1. *(node2->pprev) = node2->next;
   
2. node2->next->pprev = node2->pprev;

    这样一来，我们对hlist_node里的谅解指针pprev的存在价值与意义应该很明白了，以后不至于再被眼花缭乱的取地址操作符给弄晕了。OK，扯了这么多，让我们看看内核是如何实现删除哈希链表里的节点的__hlist_del()：

   
   大家自行将上述函数里的入参n换成node2，最终和我们上面推断的结果是一致的：

   

    在标准的哈希链表里，因为最后一个节点的next=NULL，所以在执行第二句有效代码前首先要对当前节点的next值进行判断才行。

   内核提供了hlist_add_head()，用于实现向哈希链表里插入节点：

点击(此处)折叠或打开

1. hlist_add_head(struct hlist_node *n, struct hlist_head *h)

    其中n表示待插入的节点，h表示哈希链表表头。在刚初始化完哈希表myhlist的情况下，依次调用四次hlist_add_head()，每次调用后myhlist哈希表的情况如下：

   (备注：双箭头表示两级指针，单箭头表示一级指针)
   理论上说，内核应该再提供一个对称的方法hlist_add_tail()才算完美，用于将哈希链表操作成如下的样子：

   还有hlist_add_behind()和hlist_add_before()，在3.17版本之前hlist_add_behind()的名字还是hlist_add_after()，不过作用都一样。两个函数原型分别如下：

点击(此处)折叠或打开

1. hlist_add_before(struct hlist_node *n,struct hlist_node *next);
   
2. hlist_add_behind(struct hlist_node *n,struct hlist_node *prev);

    其中n是待插入的节点，next或者prev都是n的相对位置参考节点，其作用分别是：
   hlist_add_before()：在next节点的前面插入n节点；
  hlist_add_behind()：在prev节点的后面插入n节点；

    接下来，让我们…..

   1)、在node4节点的前面插入node3：

   注意hlist_add_before()有个约束条件，那就是next!=NULL。

   2)、在node1的节点后面插入node5：

   同样的约束条件也适用于hlist_add_behind()，即prev!=NULL。
   未完，待续...