Hash table in Linux kernel

Question

Does the Linux kernel have a generic hash table implementation for use in kernel code? I know that linked lists, red-black trees, and radix trees are available, but haven't found reference to a generic hash table implementation, although I know hash tables are heavily used in the core kernel.

Answer 1

At the risk of looking like a reputation whore, let me summarize the answers I've acquired so far.

---

Kernel 3.7+

A generic implementation was introduced by Sasha Levin in 2012 and merged for the 3.7 kernel.

---

Older Kernels

The kernel (as of 2.6.38) does not include a generic hash table implementation, but does include some pieces:

• hlist_*/HLIST_* in list.h are single-pointer-head doubly-linked list structs and macros useful for hash buckets. (answer below from adobriyan)
• hash.h includes hashing routines for ints, longs, and pointers. This article by Chuck Lever studies the performance of these routines.
• See pid_hash in pid.c for an example constructed from these primitives.

uthash is a generic hash table for C implemented as macros defined in a single header file. This solution may be appropriate for many third-party kernel modules (e.g., device drivers). However, reliance on uthash might impede mainlining of a module.