数据结构学习,哈希表(开放定址法)

这个就真的是再数组层面上的操作了。直接上代码

目录

预先要引用的头文件以及宏定义

所使用哈希表的结构

所选取的哈希函数和处理冲突的函数

其基本操作接口

初始化哈希表

销毁哈希表

在哈希表中查找关键字为Key的记录

在哈希表H中插入e

在哈希表中删除关键字为Key的记录

哈希表的遍历

一些接口的测试


预先要引用的头文件以及宏定义

#include<stdio.h>
#include<iostream>
//
//using namespace std;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define UNSUCCESS 0
#define SUCCESS 1
typedef int ElemType;
typedef int Status;
typedef int KeyType;

所使用哈希表的结构


typedef struct {
	KeyType Key;
	//这里可以存放其他数据
}RecordType, RcdType;
typedef struct {
	RcdType* rcd;									//记录存储基址,动态分配数组
	int size;										//哈希表容量
	int count;										//当前表中含有的记录个数
	int* tag;										//标记,0空,1有效,-1已删除
	int(*hash)(KeyType key, int hashSize);			//函数指针变量,选取的哈希函数
	void(*collision)(int& hashValuue, int hashSize);//函数指针变量,用于处理冲突的函数
}HashTable_k;

所选取的哈希函数和处理冲突的函数

int hash(int key, int hashSize)
{//哈希函数,hashSize为地址空间长度
	return (3 * key) % hashSize;
}
void collision_1(int& hashValue, int hashSize)//线性探测
{
	hashValue = (hashValue + 1) % hashSize;
}

哈希函数我之前的文章有提,现在讲的是处理冲突的函数

1,线性探测法 H = (H(key)+i)%m,i<=m<=m-1

m是哈希表的长度,

H(key)的意思是你要对关键字做何种处理。

i棵表示为第i次冲突时探测的地址空间。

如图

数据结构学习,哈希表(开放定址法)

假定我有这么个哈希表,我现在要将2插入进这个表里,而2用哈希函数所求的哈希值为0,冲突,则哈希值加1,变为1,还是冲突,继续加,一直加到能插进去这个表里。(这只是个比方,数值什么的不要在意)

可以看出,其探测地址是连续的

2,二次探测法 H = (H(key)+di)%m.i<=m<=m-1,探测地址是跳跃式的

m是哈希表的长度,

H(key)的意思是你要对关键字做何种处理。

求得哈希值,

第一次冲突,+ (1的平方)

第二次冲突,-  (1的平方)

第三次冲突,+ (2的平方)

第四次冲突,-  (2的平方)

第五次冲突,+ (3的平方)

第六次冲突,-  (3的平方)

数据结构学习,哈希表(开放定址法)

数字2,求得的哈希值为1,冲突,处理后为2,冲突,再次处理后为0,还是冲突,再次处理后为5

插入,完成,这就是二次探测法。

本人本次用的是线性探测法

其基本操作接口

Status InitHash_k(HashTable_k& H, int size, int(*hash)(KeyType, int),
					void(*collision)(int&, int));					//初始化哈希表
Status DestroyHash_k(HashTable_k& H);								//销毁哈希表													
//Status CreateHash_k(HashTable_k& H);								//构造哈希表
Status SearchHash_k(HashTable_k H, KeyType key, int& p, int& c);	//在哈希表中查找关键字为Key的记录
int InsertHash_k(HashTable_k& H, RcdType e);						//在哈希表H中插入e;
Status DeleteHash_k(HashTable_k& H, KeyType key, RcdType& e);		//在哈希表中删除关键字为Key的记录
void Hash_KTraverse(HashTable_k& H);								//哈希表的遍历

初始化哈希表

Status InitHash_k(HashTable_k& H, int size, int(*hash)(KeyType, int), void(*collision)(int&, int))
{//构造一个初始容量为size的哈希表H,hash为哈希函数,collision为冲突处理函数
	H.rcd = (RcdType*)malloc(size * sizeof(RcdType));
	H.tag = (int*)malloc(size * sizeof(int));
	if (H.rcd == NULL || H.tag == NULL)
	{
		return OVERFLOW;
	}
	else
	{
		for (int i = 0; i < size; i++)
		{
			H.tag[i] = 0;
		}
		H.size = size;
		H.hash = hash;
		H.collision = collision;
		H.count = 0;
		return OK;
	}
}

销毁哈希表

Status DestroyHash_k(HashTable_k& H)
{
	if (H.rcd != NULL && H.tag != NULL)
	{
		free(H.rcd);
		free(H.tag);
		H.collision = NULL;
		H.hash = NULL;
		H.count = 0;
		H.size = 0;
		return OK;
	}
	else
	{
		return OVERFLOW;
	}
}

在哈希表中查找关键字为Key的记录

Status SearchHash_k(HashTable_k H, KeyType key, int& p, int& c)
{
	p = H.hash(key, H.size);//求得哈希地址
	while ((H.tag[p] == 1) && H.rcd[p].Key != key || H.tag[p] == -1)//判断是否有冲突,若有,执行冲突函数,取得对应地址,并用c记录冲突次数。
	{
		H.collision(p, H.size);
		c++;
	}
	if (H.rcd[p].Key == key && H.tag[p] == 1)//找到
	{
		return SUCCESS;
	}
	else//没有找到
	{
		return UNSUCCESS;
	}
}

在哈希表H中插入e

int InsertHash_k(HashTable_k& H, RcdType e)
{
	int c = 0, j = 0;
	if (SearchHash_k(H, e.Key, j, c) == SUCCESS)
	{
		return -1;
	}
	else
	{
		H.rcd[j] = e;
		H.tag[j] = 1;
		++H.count;
		return c;
	}
}

在哈希表中删除关键字为Key的记录

Status DeleteHash_k(HashTable_k& H, KeyType key, RcdType& e)
{
	int j, c = 0;
	if (SearchHash_k(H, key, j, c) == UNSUCCESS)
	{
		return UNSUCCESS;
	}
	else
	{
		e = H.rcd[j];
		H.tag[j] = -1;
		H.count--;
		return SUCCESS;
	}
}

哈希表的遍历

void Hash_KTraverse(HashTable_k& H)
{
	if (H.tag != NULL && H.rcd != NULL)
	{
		for (int i = 0; i < H.size; i++)
		{
			if (H.tag[i] == 0 || H.tag[i] == -1)
			{
				printf("#\n");
			}
			else if (H.tag[i] == -1)
			{
				printf("!#\n");
			}
			else
			{
				printf("%d\n", H.rcd[i].Key);
			}
		}
	}
}

一些接口的测试

int main()
{
	// 开放定址
	HashTable_k H;
	InitHash_k(H, 5, hash, collision_1);
	//构造你所要插入的数据
	KeyType E[10] = { 0,1,2,3,4,5,6,7,8,9 };
	RcdType EE[10];
	for (int i = 0; i < 5; i++)
	{
		EE[i].Key = E[i];
	}
	for (int i = 0; i < 5; i++)
	{
		InsertHash_k(H, EE[i]);
	}
	Hash_KTraverse(H);
	RcdType e;
	printf("--------%d\n", DeleteHash_k(H, 2, e));
	Hash_KTraverse(H);
	DestroyHash_k(H);
}

数据结构学习,哈希表(开放定址法)

 

上一篇:SpringBoot:静态资源映射规则解析


下一篇:rebase合并完之后,切换分支报错