网站建设费用归类,网页游戏平台制作,自己来建网站,搜索引擎营销简称为1、散列表数据结构 在Linux内核中#xff0c;散列表#xff08;哈希表#xff09;使用非常广泛。本文将对其数据结构和核心函数进行分析。和散列表相关的数据结构有两个#xff1a;hlist_head 和 hlist_node //hash桶的头结点
struct hlist_head {struct hlist_node *first…1、散列表数据结构 在Linux内核中散列表哈希表使用非常广泛。本文将对其数据结构和核心函数进行分析。和散列表相关的数据结构有两个hlist_head 和 hlist_node //hash桶的头结点
struct hlist_head {struct hlist_node *first;//指向每一个hash桶的第一个结点的指针
};
//hash桶的普通结点
struct hlist_node {struct hlist_node *next;//指向下一个结点的指针struct hlist_node **pprev;//指向上一个结点的next指针的地址
};对应的结构如下 hash_table 为散列表数组其中的元素类型为 struct hlist_head 。以 hlist_head 为链表头的链表其中的节点hash值是相同的也叫冲突。first指针指向链表中的节点①然后节点①的 pprev 指针指向 hlist_head 中 的 first 节点①的 next 指针指向节点②以此类推。hash_table 的列表头仅存放一个指针,也就是 first 指针,指向的是对应链表的头结点,没有tail指针,也就是指向链表尾节点的指针,这样的考虑是为了节省空间——尤其在 hash bucket (数组size)很大的情况下可以节省一半的指针空间。pprev是一个二级指针 它指向前一个节点的next指针的地址 。为什么我们需要这样一个指针呢它的好处是什么 哈希表的目的是为了方便快速的查找所以哈希表中hash桶的数量通常比较大否则“冲突”的概率会非常大这样也就失去了哈希表的意义。如何做到既能维护一张大表又能不使用过多的内存呢就只能从数据结构上下功夫了。所以对于哈希表的每个hash桶它的结构体中只存放一个指针解决了占用空间的问题。现在又出现了另一个问题数据结构不一致。显然如果hlist_node采用传统的nextprev指针对于第一个节点和后面其他节点的处理会不一致。hlist_node巧妙地将pprev指向上一个节点的next指针的地址由于hlist_head的first域指向的结点类型和hlist_node指向的下一个结点的结点类型相同这样就解决了通用性下面讲解结点相关操作的时候会有更详细的解释。
2、散列表删除结点 如果要删除hash桶对应链表中的第一个普通结点 对应的程序代码如下 static inline void __hlist_del(struct hlist_node *n)
{ struct hlist_node *next n-next;//获取指向第二个普通结点的指针 struct hlist_node **pprev n-pprev;//保留待删除的第一个结点的pprev域即头结点first域的地址此时 pprev first *pprev next; /*因为pprev first所以*pprev next相当于 first next即将hash桶的头结点指针指向原来的第二个结点如上图中的黑线1*/if (next) //如果第二个结点不为空next-pprev pprev;//将第二个结点的pprev域设置为头结点first域的地址如上图中的黑线2
}如果要删除hash桶对应链表中的非第一个结点 对应的程序代码如下 static inline void __hlist_del(struct hlist_node *n)
{ struct hlist_node *next n-next;//获取指向待删除结点的下一个普通结点的指针 struct hlist_node **pprev n-pprev;//获取待删除结点的pprev域 *pprev next; //修改待删除结点的pprev域逻辑上使待删除结点的前驱结点指向待删除结点的后继结点如上图中的黑线1if (next) //如果待删除结点的下一个普通结点不为空next-pprev pprev;//设置下一个结点的pprev域如上图中的黑线2保持hlist的结构
}可以看到删除第一个普通结点和删除非第一个普通结点的代码是一样的。 下面再来看看如果hlist_node中包含两个分别指向前驱结点和后继结点的指针。 很明显删除hash桶对应链表中的非第一个普通结点只需要如下两行代码 n-next-prev n-prev;
n-prev-next n-next;可是如果是删除的hash桶对应链表中的第一个普通结点此时 n-prev-next n-next 就会出问题因为hash桶的表头结点没有next域所以明显在这种情况下删除hash桶对应链表的第一个普通结点和非第一个普通结点的代码是不一样的。 同理结点插入操作也存在同样的问题。
