漫谈Linux内核哈希表(1)

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

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

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

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

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

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

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

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

让我们…..