关于list和hlist链表的结构比较

testh

在include/Linux/list.h中有list链表与hlist哈希链表结构的定义，下面都列出它们的定义，可以对比一下：

1. struct list_head {
   
2. struct list_head *next, *prev;
   
3. };
   
4. 
   
5. struct hlist_head {
   
6. struct hlist_node *first;
   
7. };
   
8. 
   
9. struct hlist_node {
   
10. struct hlist_node *next, **pprev;
    
11. };

复制代码

双头（next，prev）的双链表对于Hash表来说“过于浪费”，因而另行设计了一套Hash表专用的hlist数据结构——单指针表头双循环 链表，hlist的表头仅有一个指向首节点的指针，而没有指向尾节点的指针，这样在可能是海量的Hash表中存储的表头就能减少一半的空间消耗。
请问上面的蓝色那句话该如何理解吗？
是说，list_head有两个成员next和prev，而hlist_head只有一个成员first，这样就减少一个成员，从而减少一半的空间消耗吗?
当有海量的表头时能减少一半的空间。。。。
本帖自问自答了。。。。

testh

欢迎任何补充，纠正。。。。

testh

一开始的时候确实不太明白为什么有的时候看到list结构把表头和节点用两个不同的结构表示，心想他们不是一样的吗？为什么还要区别对待，分别用不用的结构表示，感觉没有必要，但是在上面说的那种情况下，确实是有必要。但这是所有原因吗?

cdtits

貌似 hash 表头用 next & prev 确实没有太大必要，改用 hlist_head 作为表头确实可以减少一半的内存占用率，但 node 应该是一样的

pitonas

确实lol

captivated

是的. hash表因为解决冲突的原因, 其结构是:

hash table
     |
     |
    \ /
-------------
hlist_head
-------------
hlist_head    --> hlist_node --> hlist_node
-------------
hlist_head
-------------
hlist_head    --> hlist_node --> hlist_node --> hlist_node
-------------
hlist_head
-------------
...
-------------

就是说最后的结构是类似一个广义表的样子.

说减少存储空间, 其实是减少那个hash table的空间, 因为表头只占用一个指针空间而不是两个.

--------------------------------------------------------------------------------------------


以上. 砖轻拍.

testh

回复 6# captivated

你画的这个图让我想起了《黑衣人2》里面的桥段，史密斯的新搭档在一个下水道的井盖前，弯下腰抓住一朵长出来的小花，然后一直揪，一直揪。。。还用脚踹。最后突然整个马路断裂，从下水道里站起来一个庞然大物，而那朵小花正是这个怪物脑袋上的一朵小花。。。
   

captivated

回复 7# testh


    哦, 前辈的描述很有趣, 确实很像, 哈哈. 不过这电影我没看过, 回去补一下. 好看吗?

testh

回复 8# captivated
还行吧，当娱乐片看
别叫前辈啊。。。

captivated

回复 9# testh


    哈哈. 看你注册时间比我早, 所以就那么叫了. 嗯, 07年的时候, 我才C语言入门...
    现在对内核方面的理解也是菜鸟, 所以叫前辈也是应该的.