上一篇中介绍了双链表的实现,现在来看下hash链表是如何实现的。注意这里所说的“hash链表”和“hash表”的不同,hash链表是指映射到hash表中同一位置的所有元素组成的溢出链表。

hash链表的结构和双链表一样,也是内嵌到需要作为hash链表表元素的结构中。不同的是,双链表的表头和表元素是用相同的结构表示的(struct list_head),hash链表使用了不同的结构:

因为hash链表没有要求在O(1)时间内访问表尾,所以表头只需要一个指针,这样就节省了一个指针的空间。 hash表的特点是查找快速,前提是“冲突”概率很小,所以hash表通常是一个较大的数组,所以即使是节约一个指针的空间,也就节约了一半的空间,在hash表很大的时候是非常可观的。

表元素还是双联的,不同是表元素的 prev 指针变成了 pprev,是个二维指针,它指向前一个元素的 next 指针。下面是这种结构的图示:

Linux中的hash表

结点的初始化工作也不相同,hash链表中不再将两个指针都指向自身:

为什么要使用二维指针呢?在双链表中表头和表元素的类型是相同的,一维指针就够了。但hash链表的表头是 struct hlist_head 类型,如果 pprev 是一维的,它无法指向 struct hlist_head 类型的表头,只能指向表头的first成员。考虑在这种情况下如何删除一个元素?你不得不判断要删除的元素是不是第一个元素,如果不是,可以像在双链表中那样删除;如果是,表头只需要重设 first 指针。为了做这种判断,删除函数需要两个参数,一个待删除的结点,一个表头指针。使用内核中的这种实现后,就不要考虑各种情况。可以通过表元素 node->pprev 指针访问和修改前一个元素的 next 指针,而不用管它指向的是一个结点还是表头的 first 成员:

hlist_del 只需要一个参数。它把删除任务转交给 __hlist_del 函数,因为 pprev 是指向前一个元素的 next 指针的指针,所以 *pprev 就是前一个元素的 next(或 first)的值,可以直接访问和修改。如果待删除元素不是最后一个元素,就将它的 pprev 的值赋给后面元素的 pprev。

判断一个hash链表是否为空可以调用 hlist_empty:

hlist_unhashed 可以判断一个结点是否被hash过,未被hash的结点的 pprev 指针为空,但 next 指针为空的结点不一定未被hash,因为hash链表的最后一个元素的 next 指针也为空:

内核也提供了和双链表类似的添加操作:

比较奇怪的是 hlist_add_fake,它将 pprev 指针指向了自己的 next 指针,实现了虚假添加操作。这样的结点会被 hlist_unhashed 判为已 hash。也可以对它调用 hlist_del 函数。

hlist_move_list 用于将一个hash链表移动到另一个表头上:

hash 链表的遍历操作和双链表也是类似的:

它的实现与双链表稍有不同,但原理都是一样的。在安全版本中的 ({ n = pos->member.next; 1; }) 的结果保证为1。hlist_entry_safe 和 list_entry 也稍有不同:

双链表的删除操作不会把指针设置为NULL,但hash链表可能,如果给 container_of 传递的 ptr 是空指针,那么 container_of 返回的指针将是一个大整数(0减去无符号整数的offset并将结果当作无符号的地址)。hlist_entry_safe 可以避免这种错误。

我们说过hash链表的表尾的next是NULL指针,内核也提供了自定义结尾值的方法,可以使用其他值来表示链表的结束。它在 <list_nulls.h>中实现。

可以看出,初始化工作不再是将指针值设为NULL,而是将自定义的nulls值左移一位再将最后一位设置为1,这样就可以根据最后一位是否是1来判断一个指针指向普通的对象还是一个结尾指针(普通对象的地址是按4或8对齐的,所以它们地址的最后一位一定是0):