https://github.com/wdfk-prog/linux-study

lib/hashtable.h & include/linux/hash.h 哈希表与哈希函数(Hash Table & Hash Functions) 内核中快速数据查找的基础设施

历史与背景

这项技术是为了解决什么特定问题而诞生的？

哈希表（Hash Table）和哈希函数（Hash Functions）是为了解决一个计算机科学中的基础问题而诞生的：如何实现高效的数据查找、插入和删除。在操作系统内核中，需要管理大量的对象，例如进程、打开的文件、内存页面、缓存的数据块（inodes, dentries）等。对这些对象进行快速访问是保证系统整体性能的关键。

具体来说，这项技术解决了以下问题：

• 性能瓶OT颈：如果使用简单的链表来管理这些对象，那么每次查找都需要遍历整个列表，其时间复杂度为O(n)，当对象数量n巨大时，性能会急剧下降。
• 代码重复：在哈希表通用框架出现之前，内核中有数十个甚至更多的子系统都各自实现了自己的哈希表逻辑。 这导致了大量的代码重复、不一致的实现和潜在的bug分散在各处。
• 可扩展性：随着硬件的发展，内存容量不断增大，内核需要管理的对象数量也随之增加。一个高效、可扩展的数据结构对于适应这种变化至关重要。
• 确定性与随机性：需要一种方法能将任意类型的键（key），如内存地址、inode号、网络连接的四元组等，均匀地、看似随机地分布到一个固定大小的数组中，以便快速定位。

它的发展经历了哪些重要的里程碑或版本迭代？

内核中的哈希技术经历了从分散实现到通用框架的演进：

• 早期分散实现：早期的内核版本中没有通用的哈希表实现。 各个子系统根据自己的需求，使用基本的C语言数组和链表（主要是内核提供的hlist，一种为哈希表场景优化的单指针头双向链表）来构建私有的哈希表。 哈希函数也比较零散，如jhash()等被广泛使用。
• 通用哈希函数的出现 (hash.h)：内核首先对哈希函数进行了统一，在 include/linux/hash.h 中提供了如 hash_ptr()、hash_long() 等一系列高质量的、针对不同输入类型优化的哈希函数。特别是引入了基于黄金分割率常数的哈希函数 hash_min()，它能将任意整数键很好地随机分布到2的幂次大小的数组中。
• 通用哈希表框架 (hashtable.h)：为了解决代码重复问题，Sasha Levin在2012年引入了一个通用的、基于宏的哈希表API，并最终合并到了内核3.7版本中，位于 lib/hashtable.h。 这个框架提供了一套标准的API（如DEFINE_HASHTABLE, hash_init, hash_add, hash_for_each等），使得开发者可以方便地创建和使用一个固定大小的哈希表。
• 可变大小哈希表：对于大小难以在编译时确定的场景，内核也支持动态分配的哈希表。 更进一步，为了解决在不阻塞并发读访问的情况下调整哈希表大小的难题，内核引入了“相对论哈希表”（Relativistic Hash Tables），允许在不加锁的情况下进行扩容。
• 安全哈希函数的引入：为了应对可预测哈希值可能导致的拒绝服务攻击（Hash Collision DoS），内核引入了SipHash等具备密码学安全特性的伪随机函数，用于对外部输入进行哈希的场景。

目前该技术的社区活跃度和主流应用情况如何？

哈希表是Linux内核中最基础、使用最广泛的数据结构之一。 通用的哈希表框架已经非常成熟和稳定。内核中几乎所有需要快速键值查找的场景都在使用它，例如：

• 进程管理：通过PID哈希表快速查找task_struct。
• 内存管理：页缓存（Page Cache）使用哈希表来快速定位一个文件中的特定数据页。
• 文件系统：dcache（目录项缓存）和inode缓存都重度依赖哈希表。
• 网络：用于管理TCP/UDP连接、路由表等。

核心原理与设计

它的核心工作原理是什么？

Linux内核的通用哈希表采用的是**拉链法（Chaining）**来解决哈希冲突。

1. 数据结构：
   • 桶数组（Bucket Array）：哈希表本身是一个数组，数组的每个元素被称为一个“桶”（Bucket）。在内核中，这是一个struct hlist_head类型的数组。 hlist是一种特殊的双向链表，其头部只有一个指针，比标准的list_head更节省空间，非常适合用作哈希表的桶头。
   • 哈希节点（Hash Node）：任何希望被放入哈希表的数据结构，都必须内嵌一个struct hlist_node成员。这个成员就是将该数据结构链接到桶链表中的“钩子”。
2. 哈希函数：
   • 这是一个接受键（key）作为输入，输出一个整数（哈希值）的函数。内核在hash.h中提供了多种哈希函数。
3. 映射过程：
   • 当需要将一个对象存入哈希表时，内核首先使用哈希函数计算其键的哈希值。
   • 然后，通过取模运算（通常是与数组大小减1进行按位与，因为大小总是2的幂），将哈希值转换为数组的索引，确定该对象应该放入哪个桶。
4. 操作流程：
   • 插入 (hash_add)：根据键计算出桶索引，然后将对象的hlist_node添加到对应桶的hlist_head所指向的链表的头部。这是一个O(1)操作。
   • 查找 (hash_for_each_possible)：根据键计算出桶索引，然后只遍历该桶对应的链表，逐个比较链表上对象的键是否与要查找的键匹配。理想情况下，如果哈希函数分布均匀且哈希表足够大，每个链表的长度接近于1，查找操作的时间复杂度也接近O(1)。
   • 删除 (hash_del)：这是一个两步过程。首先需要查找到目标对象，然后将其hlist_node从链表中移除。

它的主要优势体现在哪些方面？

• 极高的平均性能：对于插入、删除和查找操作，其平均时间复杂度都接近O(1)。
• 内存效率：通过将hlist_node内嵌到业务数据结构中，避免了为指针和数据分别进行内存分配的开销。
• 通用性和易用性：hashtable.h提供的宏极大地简化了哈希表的使用，开发者无需关心实现细节。

它存在哪些已知的劣势、局-限性或在特定场景下的不适用性？

• 最坏情况性能：如果哈希函数选择不当，或者恶意构造的输入导致大量对象被哈希到同一个桶中，哈希表会退化成一个链表，其操作时间复杂度将下降到O(n)。
• 固定大小：DEFINE_HASHTABLE创建的哈希表是固定大小的，无法动态扩容。 在对象数量波动很大的场景下，这可能导致空间浪费或性能下降。
• 无序性：哈希表不保证元素的任何顺序。如果需要按顺序遍历元素，则不应使用哈希表。
• 键类型限制：内核的通用哈希表API原生只处理整数类型的键。 如果要使用字符串或其他复杂结构作为键，开发者需要自己先将键哈希成一个整数，然后再将这个整数作为键传给哈希表API。

使用场景

在哪些具体的业务或技术场景下，它是首选解决方案？请举例说明。

在内核中，任何需要根据一个唯一的键快速定位到一个数据结构实例的场景，哈希表都是首选。

• dcache（目录项缓存）：当内核需要查找一个路径名，如/home/user/file.txt时，VFS会逐级查找。为了查找user这个目录项，它会计算父目录（/home）的inode地址和字符串"user"组合的哈希值，然后在dcache哈希表中快速定位到可能匹配的dentry对象，避免了慢速的磁盘访问。
• PID管理：当需要根据一个进程ID（PID）号找到对应的task_struct时，内核会使用PID在PID哈希表中进行查找，这是一个典型的整数键查找场景。
• 网络连接跟踪（conntrack）：防火墙和NAT需要快速查找一个网络包属于哪个已建立的连接。它会使用数据包的源/目的IP、源/目的端口和协议组成的四/五元组作为键，在连接跟踪哈希表中查找对应的连接状态。

是否有不推荐使用该技术的场景？为什么？

• 需要有序数据：如果需要按键的顺序遍历数据，或者需要快速找到最大/最小值，应该使用红黑树（Red-Black Tree）或基数树（Radix Tree）。
• 数据量极小：如果管理的对-象数量非常少（例如，少于十几个），使用简单的链表可能更简单，代码开销也更小。
• 需要范围查找：如果需要查找某个范围内的所有键，哈希表无法高效完成，而树形结构（如红黑树、B树）则非常适合。
• 键的分布非常不均匀：如果键的分布本身就存在很大偏斜，且无法通过哈-希函数来打散，那么哈希表的性能会很差。

对比分析

请将其 与 其他相似技术 进行详细对比。

特性	哈希表 (Hash Table)	链表 (Linked List)	红黑树 (Red-Black Tree)	基数树 (Radix Tree)
核心功能	快速的键值精确匹配查找	简单的线性数据序列存储	有序的键值映射	针对整数/指针键的快速、空间优化的有序映射
实现方式	数组 + 链表（拉链法）	节点通过指针前后相连	自平衡的二叉搜索树	多级数组（Trie树的变种）
查找性能	平均: O(1), 最坏: O(n)	O(n)	O(log n)	O(k) (k为键的位数)
插入/删除性能	平均: O(1), 最坏: O(n)	O(1) (如果已知节点) / O(n) (需查找)	O(log n)	O(k) (k为键的位数)
内存占用	中等（数组开销 + 节点开销）	低（只有节点开销）	高（每个节点有颜色、父子指针等额外开销）	可能很高，取决于键的稀疏度
数据顺序	无序	插入顺序	有序	有序
范围查找	不支持	O(n)	高效支持	高效支持
典型用途	dcache, PID表, 连接跟踪	管理少量对象，如任务队列	内存区域管理(vm_area_struct), 文件描述符管理, 高精度定时器	页缓存（将文件偏移映射到物理页）, 内存映射

include/linux/stringhash.h

name_hash

/*
 * 用于将字节字符串哈希为32位哈希值的例程。
 *
 * 这些哈希函数在不同的内核版本、架构，甚至同一内核的多次启动之间都**不保证稳定**。
 * （例如，它们可能依赖于启动时的硬件检测，或者被故意随机化。）
 *
 * 它们也**不适合防止恶意输入导致的哈希碰撞**；为此需要更慢的哈希函数。
 *
 * 这些函数针对路径名组件进行了优化，即针对较短的字符串。
 * 即使大多数文件名较长，由于目录名较短，路径名组件的动态分布也偏向于短字符串。
 * （例如：/usr/lib/libsesquipedalianism.so.3.141。）
 */

/*
 * 版本1：一次处理一个字节。用法示例：
 *
 * unsigned long hash = init_name_hash;
 * while (*p)
 *	hash = partial_name_hash(tolower(*p++), hash);
 * hash = end_name_hash(hash);
 *
 * 虽然这个函数是为字节设计的，但 fs/hfsplus/unicode.c
 * 滥用它来哈希16位值。
 */

/* 哈希源于ReiserFS中的R5哈希，取模符号位*/
/* 使用 salt 初始化哈希值。salt 是一个种子值，可以为哈希计算提供初始状态 */
#define init_name_hash(salt)		(unsigned long)(salt)

/* 部分哈希更新功能。假设每个字符大约占 4 位。*/
static inline unsigned long
partial_name_hash(unsigned long c, unsigned long prevhash)
{
	return (prevhash + (c << 4) + (c >> 4)) * 11;
}

/*
 * 最后：将位数减少到一个 int 值（并尽量避免丢失位）。
 * 这还具有一个特性（dcache 所需），即最高位可以作为一个良好的哈希表索引。
 */
static inline unsigned int end_name_hash(unsigned long hash)
{
	return hash_long(hash, 32);
}