Menu
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.
819
A hash table is a data structure that stores one or more key and value pairs. A hash table can store keys of any type. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found. Ideally, the hash function will assign each key to a unique bucket.
Hash Table is a data structure which stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data.
A hash table is a data structure that you can use to store data in key-value format with direct access to its items in constant time. Hash tables are said to be associative, which means that for each key, data occurs at most once.
Hash tables are a type of data structure in which the address/ index value of the data element is generated from a hash function. This enables very fast data access as the index value behaves as a key for the data value.
At the risk of looking like a reputation whore, let me summarize the answers I've acquired so far.
A generic implementation was introduced by Sasha Levin in 2012 and merged for the 3.7 kernel.
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)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.
182
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With