哈希表详解

这里分享一篇关于哈希表的文章吧。

因为博主最近需要使用这个收益就简单的总结了一下和大家分享。

这里就不通过大量的文字叙述来解释哈希表的一些定义了哈（网上有许多的介绍哈希表_百度百科 (baidu.com)），这里博主就简单的给一篇代码来解释和实现哈希表，相信我写的这个看了的小伙伴去简单的操作哈希表应该是没有问题的。

//哈希表的初步使用

//这里先给一个表长
#include <stdio.h>
#define HASHSIZE 10

// 这里再给一个 删除的标志位 ,因为这里博主解决冲突的方法是开放地址法当中的线性探测法,所以不能真的删除里面的数据只能说是给一个标志
#define DELEFLAG -1

//首先 构建哈希表的存储结构
typedef struct {
	int key; // 哈希表中的关键字(也就是那些需要存储的数据)
} HashTable[HASHSIZE];

// 第二步实现 哈希函数,这里博主使用的是 除留余数的思想创建哈希函数
int HashFunc(int key) {
	// 参数是关键字

	return key % HASHSIZE;
}

// 第三步实现 处理冲突函数 , 博主使用的是开放地址法当中的线性探测法

int Collision(int addr) {
	//参数是冲突的地址

	return (addr + 1) % HASHSIZE;
}

// 第三步实现哈希搜索函数
int HashSearch(HashTable hs, int key) {
	// 参数一个是哈希表,另外一个是待搜索的关键字

	int addr;

	// 获取哈希地址
	addr = HashFunc(key);

	// 判断是否该关键字能找到
		// 该地址不为空并且 该处的关键字与待查找的关键字不相等

	while (hs[addr].key != NULL && hs[addr].key != key) {
		// 根据冲突查找该关键字的下一个地址
		addr = Collision(addr);
	}

	// 如果该关键字与哈希表中的关键字相等则返回该关键字再表中的地址
	if (hs[addr].key == key) {
		return addr;
	}
	// 如果该关键字与哈希表的关键字不相等,则返回一个空的哈希地址正好用来存放元素
	else {
		return -addr;
	}
}

// 第四步实现哈希表的插入函数
int HashInsert(HashTable hs, int key) {
	int addr;

	addr = HashSearch(hs, key);
	if (addr > 0) {
		return 0;
	}
	hs[-addr].key = key;
	return 1;
}

// 第五步实现哈希表的创建函数
int HashCreate(HashTable hs, int key, int count) {
	// 这里的count是起一个计数的作用

	// 将哈希表清零
	if (count == 0) {
		for (int i = 0; i < HASHSIZE; i++) {
			hs[i].key = NULL;
		}
	}
	count++;
	HashInsert(hs, key);
	return count;
}

// 第六步,实现哈希表的遍历

void HashDisplay(HashTable hs) {
	int i;
	printf("\n哈希表\n哈希地址:\t");
	for (i = 0; i < HASHSIZE; i++) {
		printf("%d\t", i);
	}
	printf("\n关键字: \t");
	for (i = 0; i < HASHSIZE; i++) {
		if (hs[i].key != NULL) {
			printf("%d\t", hs[i].key);
		}
		else
		{
			printf("\t");
		}
	}
	printf("\n");
}

// 实现哈希删除函数

void HashDelete(HashTable hs, int key) {
	int addr;
	addr = HashSearch(hs, key);
	if (addr >= 0) {
		hs[addr].key = DELEFLAG;
		printf("关键字%d的地址为[%d]\n", hs[addr].key, addr);
	}
	else {
		printf("关键字%d的地址不存在\n", hs[addr].key);
	}
}

int main() {
	HashTable hs;
	int count = 0;
	int items[7] = { 12,34,23,54,6,7,45 };

	//创建哈希表

	for (int i = 0; i < 7; i++) {
		count = HashCreate(hs, items[i], count);
	}

	// 显示删除前的哈希表
	printf("删除前的哈希表:\n");
	HashDisplay(hs);

	// 显示删除后的哈希表
	//要删除的关键字

	int key;
	printf("请输入要删除的关键字: ");
	scanf_s("%d", &key);
	HashDelete(hs, key);
	printf("删除后的哈希表:\n");
	HashDisplay(hs);
}

源码有不明白的小伙伴可以dd博主。