双向循环链表如何快速遍历

yuexiaduzhuo_cu

从双向循环链表中查找一个节点，这部分代码需要优化，源代码是用list_for_each_entry_rcu宏遍历查找的，循环体中通过比较关键字查询结果，但是这样需要遍历到每个节点，有没有快速查找的办法呢，请高手指点

Godbach

回复 1# yuexiaduzhuo_cu

一般情况下，如果表项较多的话，都会结合 hash + 链表的。
通过合理的算法，避免链表的表项过多。

因此，想了解一下，你所谓的快速遍历，是基于什么前提？ 就单单用一个双向链表存储所有内容吗？


   

yuexiaduzhuo_cu

这个说起来比较复杂，我有一个结构体，里面包含mac地址，通过比较mac地址得到这个结构体指针，由于是项目代码，我不能贴上来，只能简单描述一下回复 2# Godbach


   

yuexiaduzhuo_cu

刚刚发现节点里有这样两个结构体，struct list_head node;struct hlist_node hash_node;这是否你说的hash＋链表，对应的函数有哪些呢，谢谢！回复 2# Godbach


   

wangjianchangdx

这是个吊诡的问题

既然是遍历，那时间复杂度必然是O(n)，还怎么快呢？

Godbach

回复 4# yuexiaduzhuo_cu

应该差不多吧，结合一下代码的功能。

   

瀚海书香

回复 4# yuexiaduzhuo_cu

hlist_for_each_entry类的函数。
   

yuexiaduzhuo_cu

这位大哥能否提供一些关于哈希链表的资料，我查了一下，哈希链表的查找还是用hlist_for_each逐个查找，好像哈希表没起到作用啊，还有就是hlist_node里的**prev二级指针好像没起到哈希表的作用啊回复 6# Godbach