Linux内核中的哈希表

Question

Linux内核是否具有用于内核代码的通用哈希表实现？我知道可以使用链表,红黑树和基数树,但是没有找到对通用哈希表实现的引用,尽管我知道哈希表在核心内核中大量使用.

Answer 1

冒着看起来像妓女的风险,让我总结一下迄今为止我所获得的答案.

内核3.7+

Sasha Levin在2012 年引入了一个通用实现,并合并为3.7内核.

较旧的内核

内核(截至2.6.38)不包含通用哈希表实现,但确实包含一些部分:

• hlist_*/HLIST_*在list.h中是单指针头双向链表结构和对哈希桶有用的宏.(以下来自adobriyan的回答)
• hash.h包括int,long和指针的散列例程.Chuck Lever的这篇文章研究了这些例程的表现.
• 看到pid_hash在pid.c从这些原语构造的示例.

uthash是C的通用哈希表,实现为在单个头文件中定义的宏.该解决方案可能适用于许多第三方内核模块(例如,设备驱动程序).但是,依赖uthash可能会阻碍模块的主线化.