羊村懒王

这个屌丝很懒，什么也没留下！

热门标签

Linux下~Hash表的构建与应用（包括内核文件list.h分析）_hash表linux

作者：羊村懒王 | 2024-04-12 13:09:59

踩

hash表linux

1、问题：什么是哈希表？怎么使用哈希查找？

哈希表也叫做散列表，通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

哈希查找的操作步骤：⑴用给定的哈希函数构造哈希表；⑵根据选择的冲突处理方法解决地址冲突；⑶在哈希表的基础上执行哈希查找。

具体操作步骤：step1 取数据元素的关键字key，计算其哈希函数值。若该地址对应的存储空间还没有被占用，则将该元素存入；否则执行step2解决冲突。step2 根据选择的冲突处理方法，计算关键字key的下一个存储地址。若下一个存储地址仍被占用，则继续执行step2，直到找到能用的存储地址为止。

即：设哈希表为HST[0~M-1]，哈希函数取H（key），解决冲突的方法为R（x）；Step1 对给定k值，计算哈希地址 Di=H（k）；若HST为空，则查找失败；若HST=k，则查找成功；否则，执行step2（处理冲突）。Step2 重复计算处理冲突的下一个存储地址 Dk=R（Dk-1），直到HST[Dk]为空，HST[Dk]=k为止。若HST[Dk]=K，则查找成功，否则查找失败。

哈希查找的本质是先将数据映射成它的哈希值。哈希查找的核心是构造一个哈希函数，它将原来直观、整洁的数据映射为看上去似乎是随机的一些整数。

因此构建一个好的哈希表的关键是：选择一个好的的哈希函数与合适的冲突处理方法；

哈希函数：http://blog.csdn.net/mycomputerxiaomei/article/details/7641221

一些哈希函数的效率对比：http://blog.csdn.net/djinglan/article/details/8812934

处理冲突的方法：http://blog.sina.com.cn/s/blog_6fd335bb0100v1ks.html

Linux内核哈希表的构建与实现：http://www.cnblogs.com/wanghetao/archive/2013/04/13/3019156.html

Linux内核，list.h文件详解： http://blog.csdn.net/ggxxkkll/article/details/7591766

-----------------------------------------------------------------------一条华丽的分割线------------------------------------------------------------------------------------

2、使用Linux内核2.6.32中的list.h文件，linux通用链表list.h：

常用接口：

INIT_LIST_HEAD(&g_list_head);

list_add(&test[cnt].list, &g_list_head);

list_add_tail(&test[cnt].list, &g_list_head);

list_del(&test[2].list);

list_del_init(&test[2].list);

list_for_each (pos, &g_list_head)

list_for_each_entry(pos, &g_list_head, list)

list_for_each_entry_safe(pos, n, &g_list_head, list)

list_emtry(&g_list_head)

List_entry(&test[2].list,structtest_list_t, list);

1、双向链表：struct list_head {struct list_head *next, *prev; };

2、用同一对象初始化next 和prev：#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

当我们用LIST_HEAD(nf_sockopts)声明一个名为nf_sockopts的链表头时，它的next、prev指针都初始化为指向自己，这样，我们就有了一个空链表，因为Linux用头指针的next是否指向自己来判断链表是否为空。

3、初始化就是把指针指向自己：#define INIT_LIST_HEAD(ptr) do { (ptr)->next = (ptr);

(ptr)->prev = (ptr); } while (0)

除了用LIST_HEAD()宏在声明的时候初始化一个链表以外，Linux还提供了一个INIT_LIST_HEAD宏用于运行时初始化链表。

4、插入新条目,插在prev与next中间：

static inline void __list_add(struct list_head *new1,

struct list_head *prev, struct list_head *next)

{

next->prev = new1;

new1->next = next;

new1->prev = prev;

prev->next = new1;

}

static inline void list_add(struct list_head *new1,

struct list_head *head)

{ __list_add(new1, head, head->next); }

5、尾部插法：

static inline void list_add_tail(struct list_head *new1,

struct list_head *head)

{ __list_add(new1, head->prev, head); }

6、删除一个结点entry，并将删除结点地址置为0：

static inline void __list_del(struct list_head * prev,

struct list_head * next)

{ next->prev = prev; prev->next = next; }

static inline void list_del(struct list_head *entry)

{

__list_del(entry->prev, entry->next);

entry->next = LIST_POISON1; //指针清除0

entry->prev = LIST_POISON2; //指针清除0

}

7.从链表中删除元素entry,并将其初始化为新的链表

static inline void list_del_init(struct list_head *entry)

{

__list_del(entry->prev, entry->next);

INIT_LIST_HEAD(entry);

}

8、实际上是一个for循环，利用传入的pos作为循环变量，从表头head开始，逐项向后（next方向）移动pos，

直至又回到head：

#define list_for_each(pos, head)

for (pos = (head)->next; pos != (head); pos = pos->next)

9、list_for_each_safe 也是链表顺序遍历，只是更加安全。即使在遍历过程中，当前节点从链表中删除，也不会影响链表的遍历
参数上需要加一个暂存的链表节点指针n。
这个宏中使用了n这个struct list_head类型的临时变量，每次迭代之后pos的下一个节点储存在临时变量n中，则在迭代中删除pos节点后，下一次迭代会重新给pos赋值为临时变量n，然后再做迭代。这样在迭代的过程中就可以安全地删除节点pos了。

#define list_for_each_safe(pos, n, head)

for (pos = (head)->next, n = pos->next; pos != (head);

pos = n, n = pos->next)

10.循环遍历每一个pos中的member子项

#define list_for_each_entry(pos, head, member)

\ for (pos = list_entry((head)->next, typeof(*pos), member);

\ prefetch(pos->member.next), &pos->member != (head);

\ pos = list_entry(pos->member.next, typeof(*pos), member))

11.要求调用者另外提供一个与pos同类型的指针n，在for循环中暂存pos下一个节点的地址，避免因pos节点被释放而造成的断链

#define list_for_each_entry_safe(pos, n, head, member)

\ for (pos = list_entry((head)->next, typeof(*pos), member), n = list_entry(pos->member.next, typeof(*pos), member);

\ &pos->member != (head);

\ pos = n, n = list_entry(n->member.next, typeof(*n), member))

12、测试链表是否为空，以头指针的next是否指向自己来判断链表是否为空：

static inline int list_empty(const struct list_head *head)

{ return head->next == head; }

13、使用list_entry()宏在linux链表中访问链表数据。原理为指针ptr指向结构体type中的成员member；通过指针ptr，返回结构体type的起始地址。

定义中((unsigned long) &((type *)0)->member)意为：把0地址转化为type结构的指针，然后获取该结构中member成员的指针，并将其强制转换为unsigned long类型：

#define list_entry(ptr, type, member) ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

Linux链表设计者（认为双头（next、prev）的双链表对于HASH表来说"过于浪费"，因而另行设计了一套用于HASH表应用的hlist数据结构--单指针表头双循环链表，hlist的表头仅有一个指向首节点的指针，而没有指向尾节点的指针，这样在可能是海量的HASH表中存储的表头就能减少一半的空间消耗。

3、使用list.h文件，构建哈希表：

list.h


#ifndef _LIST_H
#define _LIST_H
 
struct list_head {
	struct list_head *next, *prev;
};
 
#define LIST_HEAD_INIT(name)   {&(name), &(name)} 
 
#define LIST_HEAD(name)    struct list_head name = LIST_HEAD_INIT(name)
 
#define INIT_LIST_HEAD(ptr)  do{(ptr)->next = (ptr); (ptr)->prev = (ptr);} while(0)
 
#define list_entry(ptr, type, member)   ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))
 
#define list_for_each(pos, head)    for (pos = (head)->next; pos != (head); pos = pos->next)
 
#define list_for_each_safe(pos, pnext, head)   for (pos = (head)->next, pnext = pos->next; pos != (head); pos = pnext, pnext = pos->next)
 
void __list_add(struct list_head *add,struct list_head *prev,struct list_head *next);
 
void list_add(struct list_head *add, struct list_head *head);
 
void list_add_tail(struct list_head *add, struct list_head *head);
 
void __list_del(struct list_head *prev, struct list_head *next);
 
void list_del(struct list_head *entry);
 
void list_del_init(struct list_head *entry);
 
int list_empty(struct list_head *head);
 
void list_splice(struct list_head *list, struct list_head *head);
 
#endif	/* list.h */

list.c


#include "list.h"
 
void __list_add(struct list_head *add,struct list_head *prev,struct list_head *next)
{
	next->prev = add;
	add->next = next;
	add->prev = prev;
	prev->next = add;
}
 
void list_add(struct list_head *add, struct list_head *head)//每次添加节点到head之后，始终都是添加到头结点之后
{
	__list_add(add, head, head->next);
}
 
void list_add_tail(struct list_head *add, struct list_head *head)//每次添加节点都是头结点之前，由于是循环链表，就是说添加到链表尾部
{
	__list_add(add, head->prev, head);
}
 
void __list_del(struct list_head *prev, struct list_head *next)
{
	next->prev = prev;
	prev->next = next;
}
 
void list_del(struct list_head *entry)//删除节点
{
	__list_del(entry->prev, entry->next);
}
 
void list_del_init(struct list_head *entry)
	//删除节点，并初始化被删除的结点（也就是使被删除的结点的prev和next都指向自己）
{
	__list_del(entry->prev, entry->next);
	INIT_LIST_HEAD(entry);
}
 
int list_empty(struct list_head *head)//判断链表是否为空
{
	return head->next == head;
}
 
void list_splice(struct list_head *list, struct list_head *head)
	//通过两个链表的head，进行连接
{
	struct list_head *first = list->next;
 
	if (first != list) {
		struct list_head *last = list->prev;
		struct list_head *at = head->next;
 
		first->prev = head;
		head->next = first;
 
		last->next = at;
		at->prev = last;
	}
}

hash.h


#include "list.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
 
/*	定义哈希表大小  */
#define HASH_SIZE  2
/*	定义大小为HASH_SIZE的哈希表  */
struct list_head hash_array[HASH_SIZE];
 
 /* 自定义数据结构，仅供于测试 */
typedef struct
{
	struct list_head lst;
	int lable;
	//其他数据
}lable_t;
 
void init_hashMap();
int get_hash_index(char *key, int len);
int creat_new_node(int lable);
lable_t  *search_lable(int lable);
void del_lable(int lable);
void free_hashMap();
void print_hashMap();

hash.c


#include "HashMap.h"
 
/* 初始化哈希表 */
void init_hashMap()
{
	int i;
	for(i = 0; i < HASH_SIZE; i++)
		INIT_LIST_HEAD(&hash_array[i]);
}
 
/* 获取哈希表位置索引,使用 BKDR算法 */
int get_hash_index(char *key, int len)
{
	int hash = len,i;
	for(i=0; i < len; i++)
	{
		hash = hash * 131 + key[i];
	}
	return (hash % HASH_SIZE);
}
 
/* 创建新的节点 */
int creat_new_node(int lable)
{
	int index;
	lable_t *node;
	//获取哈希表位置索引
	index = get_hash_index((char *)&lable, sizeof(lable));
	node = search_lable(lable);
	if(node == NULL)
	{
		//为新节点分配存储空间
		node = (lable_t *)malloc(sizeof(lable_t)); 
		node->lable = lable;
		//添加到哈希表index单元中
		list_add_tail(&node->lst,&hash_array[index]);
		return 1;
	}
	printf("该键值已存在！不能再次添加！\n");
	return 0;
}
 
/* 哈希表中查找值为lable的节点 */
lable_t  *search_lable(int lable)
{
	int index;
	struct list_head *pos;
	lable_t *node;
	index = get_hash_index((char * )&lable, sizeof(lable));
	//判断表中该单元是否为空
	if( list_empty(&hash_array[index]) )
		return NULL;
	//查找lable
	list_for_each(pos, &hash_array[index])
	{
		node = list_entry(pos, lable_t, lst);
		if(node->lable == lable)
			return node;
	}
	return NULL;
}
 
/* 删除哈希表中的某个节点 */
void del_lable(int lable)
{
	int index;
	struct list_head *pos;
	lable_t *node;
	index = get_hash_index((char * )&lable, sizeof(lable));
	//判断表中该单元是否为空
	if( list_empty(&hash_array[index]) )
	{
		printf("没有该节点！\n");
		return;
	}
	//查找lable
	list_for_each(pos, &hash_array[index])
	{
		node = list_entry(pos, lable_t, lst);
		if(node->lable == lable)
			list_del(&node->lst);
	}
	return;
		
}
 
/* 释放哈希表 */
void free_hashMap()
{
	int i;
	struct list_head *pos, *n;
	lable_t *node;
	//判断表中该单元是否为空
	for(i = 0; i < HASH_SIZE; i++)
	{
		if( list_empty(&hash_array[i]) )
			continue;
		list_for_each_safe(pos,n,&hash_array[i])
		{
			node = list_entry(pos,lable_t,lst);
			list_del(&node->lst);
			free(node);
		}
	}
 
}
 
/* 打印哈希表中的所有数据 */
void print_hashMap()
{
	int i;
	struct list_head *pos, *n;
	lable_t *node;
 
	for(i = 0; i < HASH_SIZE; i++)
	{
		if( list_empty(&hash_array[i]) )
			continue;
		list_for_each_safe(pos,n,&hash_array[i])
		{
			node = list_entry(pos,lable_t,lst);
			printf("hash_array[%d] = %d\n",i,node->lable);
		}
	}
}

main.c


#include <stdio.h>
#include "list.h"
#include "HashMap.h"
 
void main()
{
	int index,i,lable[5] = {5,15,25,35,2};
	lable_t *lab = NULL;
	init_hashMap();
 
	for(i = 0; i < 5; i++)
	{
		creat_new_node(lable[i]);
	}
 
	lab = search_lable(lable[3]);
	if(lab == NULL)
		printf("查询结果lable[3] = NULL!\n");
	else
		printf("查询结果lable[3] = %d\n",lab->lable);
 
	printf("删除lable[3]!\n");
	del_lable(lable[3]);
	
	printf("读取哈希表所有数据：\n");
	print_hashMap();
 
	free_hashMap();
 
	return ;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/410780