LINUX内核数据结构-HASHTABLE

LINUX内核数据结构-HASHTABLE

1.前言

在读这篇文章之前,建议您先读一下上一篇介绍linux内核list实现的文章,链接在此。由于很多原理性的东西已经在上述文章中进行了阐释,因此这篇文章中不再重复描述。

Linux kernel 3.7 之后采用了由Sasha Levin设计的通用型 hashtable(代码在这里),为了方便大家理解hashtable的原理,我们并没有直接使用Sasha Levin的代码,而是把核心代码摘录了出来,这样看起来会更清晰。

本篇中的完整示例代码已经上传至我的github仓库,供您参考。

2.原理

大家都知道,hashtable的两个要点是散列函数冲突处理方法(如果不知道建议先读下之前写的这篇文章)。linux内核的hashtable,要求用户自己实现散列函数,冲突处理方法为拉链法。

拉链法的链表,用的是hashlist(下面的篇幅会详细介绍);hashtable的桶,其实就是hashlist的数组;用户提供的散列函数,作用就是把hashtable的key映射为hashlist数组的下标。

3.hashlist

hashlist的代码与普通list的代码位于同一文件中,实现方式也是比较类似的。

定义头结点和普通节点:

// copy from kernel/include/linux/types.h
struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;
};

注意,普通链表是双向链表,因此不区分头结点和普通节点,他们使用同样的结构体,且同样只包含prev和next两个指向自己的指针。

hash链表则不同,他是单向链表,因此头结点中只包含一个指向第一个节点的指针。普通节点则包含两个字段,next字段指向下一个元素,pprev则是个指针的指针,指向前一个元素的next/first指针。之所以这样设计,是因为链表的第一个元素的prev与其他节点的prev的结构体不一样(一个是hlist_head,一个是hlist_node),但是他们的prev节点的next/first指针指向的结构体是一样的,因此可以统一用一个指向hlist_node的指针的指针来保存。

链表的初始化过程如下,其实就是把指针置空而已:

#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)

static inline void INIT_HLIST_NODE(struct hlist_node *h)
{
	h->next = NULL;
	h->pprev = NULL;
}

增加链表节点的函数如下:

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
	struct hlist_node *first = h->first;
	n->next = first;
	if (first)
		first->pprev = &n->next;
	h->first = n;
	n->pprev = &h->first;
}

该函数是从头部插入,具体操作也很简单,主要提醒一点,即pprev指针是指向前一个节点的next/first指针。

遍历过程如下:

#define hlist_entry(ptr, type, member) container_of(ptr,type,member)

#define hlist_entry_safe(ptr, type, member) \
	({ typeof(ptr) ____ptr = (ptr); \
	   ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
	})

#define hlist_for_each_entry(pos, head, member)	\
	for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
	     pos; \
	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))

hlist_for_each_entry中多次调用了hlist_entry_safe宏定义,hlist_entry_safe则是在普通的hlist_entry上包了一层,对指针做了下判空。

for循环本体也比较好理解,起始节点是head节点的first指针,即链表的第一个节点,终止条件是指针非空,取下一个节点时,取用户自定义结构体内嵌的hlist节点的next指针即可。

4.初始化

首先得定义一个结构体,嵌入hlist_node结构体:

struct order_node_t
{
    long hkey;
    long order_ref;
    struct hlist_node hnode;
};

在这里,我们以保存订单结构为例。其中hkey字段保存的是该订单结构体的hashkey,在发生散列冲突时,利用hashkey字段是否相同可判断我们是否找到了想要的订单结构体

然后,我们需要定义hash函数:

#define HTBL_BKT_CNT 7

static inline int hash_func(int order_no)
{
    return order_no % HTBL_BKT_CNT;
}

这里为了方便理解,我们直接用订单号与hashtable桶的个数(本例中为8)取模,这样就能根据订单号,把订单结构体映射到其中一个桶(即hashlist)中。

然后我们定义并初始化hashtable:

//hashtable buckets
struct hlist_head h_ord_tbl[HTBL_BKT_CNT];

for (i = 0 ; i < HTBL_BKT_CNT ; i++) 
{
    INIT_HLIST_HEAD(&h_ord_tbl[i]);
}

定义hashtable其实就是定义一个hashlist的数组,每个hashlist都是hashtable的一个桶。初始化也很简单,就是对每个hashlist调用INIT_HLIST_HEAD,把头结点的first指针置空。

5.增加元素

增加元素的示例代码如下:

//add elements to table
for (ord_no = 0 ; ord_no < ORDER_CNT ; ord_no++) 
{
	p_ord = (struct order_node_t *)malloc(sizeof(struct order_node_t));
	p_ord->hkey = ord_no;
	p_ord->order_ref = ord_no;
	INIT_HLIST_NODE(&p_ord->hnode);

	bkt_idx = hash_func(ord_no);
	hlist_add_head(&p_ord->hnode, &h_ord_tbl[bkt_idx]);
}
  • 新建一个用户自定义的结构体
  • 初始化他的hashlist节点字段
  • 调用自定义的hash函数,将订单号映射为hashtable桶数组的一个下标,从而找到了对应的hashlist
  • 然后将自己插入该hashlist即可

6.查找

查找数据的示例代码如下:

//search from hashtable
for (ord_no = 0 ; ord_no < ORDER_CNT ; ord_no++) 
{
	bkt_idx = hash_func(ord_no);
	hlist_for_each_entry(p_ord, &h_ord_tbl[bkt_idx], hnode)
	{
		if (p_ord->hkey == ord_no)
			printf("%ld, %ld\n", ord_no, p_ord->order_ref);
	}
}
  • 仍然是先调用自定义的hash函数,将订单号映射为hashtable桶数组的一个下标,从而找到了对应的hashlist
  • 然后遍历该hashlist,找到与要查找的元素hashkey相同的那个

注意,如果hash桶中的hashlist的长度大于1,那么就是发生了冲突,发生冲突时要对hashlist进行遍历,因此冲突过多是会影响hashtable的性能的,用户可通过合理的设计hash函数来降低冲突概率,进而提高hashtable的性能。

7.遍历

hashtable的遍历代码如下:

//hashtable foreach
for (bkt_idx = 0 ; bkt_idx < HTBL_BKT_CNT ; bkt_idx++) 
{
	hlist_for_each_entry(p_ord, &h_ord_tbl[bkt_idx], hnode)
		printf("%ld\n", p_ord->order_ref);
}

其实就是遍历桶,然后遍历桶中(hashlist)的元素,运行效果如下:

散列函数的存在,会导致hashtable中的元素大致均匀且分散地存储在hashtable的每个桶(hashlist)中,因此按照上述过程进行遍历时,你会发现数据似乎是无序,这也就是stl的hash容器为什么都叫unordered_xxx的原因。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注