data-structures - Linux内核中的哈希表

Question

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

Answer 1

冒着看起来像名声妓女的风险，让我总结一下我迄今为止获得的答案。

内核 3.7+

一个通用的实现是 introduced由 Sasha Levin 于 2012 年和 merged对于 3.7 内核。

较旧的内核

内核(从 2.6.38 开始)不包括通用哈希表实现，但确实包括一些部分:

hlist_*/HLIST_*在 list.h是对哈希桶有用的单指针头双向链表结构和宏。 ( answer below 来自 adobriyan )

hash.h包括整数、长整数和指针的散列例程。 This article Chuck Lever 研究了这些套路的表现。

见 pid_hash在 pid.c对于从这些原语构造的示例。

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