数据结构值哈希表-EW帮帮网

文章目录

- 哈希表

哈希表

哈希表的原理精讲

哈希表 - 散列表，它是基于快速存取的角度设计的，也是一种典型的“空间换时间”的做法

需求：实现一种算法可以根据宠物编号快速找到宠物，并且获取宠物信息

先按照宠物编号给宠物有规律的分组（下方利用的是编号%5）
访问的时候，先找到组，再根据组找宠物，这样可以提高搜索效率

键(key)：	宠物的编号如， 1 、 5 、 19 。。。
值(value)：	宠物的其它信息（包含性别、年龄和战斗力等）
索引(index):	数组的下标(0,1,2,3,4) ，用以快速定位和检索数据
哈希桶:	保存索引的数组(链表或数组)，数组成员为每一个索引值相同的多个元素
哈希函数:	将宠物编号映射到索引上，采用求余法，如：组员编号 19

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5YCVWnqP-1666352735604)(D:\冲击offer\博客\数据结构\assets\clip_image002-16662691695151.jpg)]$

0 1 2 3 4 :从纵向看是二级指针数组保存了一级指针,每一个一级指针都是一个链表的队头
即 : 二级指针保存了链表的队头

哈希链表的算法实现

哈希链表数据结构的定义

//哈希表实现
struct MyHash
{
	int key;
	void * data;
	MyHash *next;
};

struct MyHashList
{
	//索引数目
	int indexNum;
	//保存索引的队头
	//MyHash *myHashArr[];数组是不可以改变指向,所以不能接受开辟的内存
	MyHash **myHashArr;
};

哈希链表初始化

//改变一级指针保存的值,需要使用二级指针
bool initMyHashList(MyHashList * myHashList, int indexNum)
{
	if (myHashList == NULL)return false;
	myHashList->indexNum = indexNum;

	myHashList->myHashArr = new MyHash*[myHashList->indexNum];
	if (myHashList->myHashArr == NULL)return false;

	for (int i = 0; i < indexNum; i++)
	{
		int temp = i;
		myHashList->myHashArr[i] = new MyHash;

		//分配内存成功,就至0
		if (myHashList->myHashArr[i] != NULL)
		{
			memset(myHashList->myHashArr[i], 0, sizeof(MyHash));
		}
		else
		{
			//分配内存失败,释放之前所有分配的内存
			for (int j = 0; j < temp - 1; j++)
			{
				delete myHashList->myHashArr[j];
			}
			delete myHashList->myHashArr;
			return false;
		}
	}

	return true;
}

哈希函数

//获取哈希索引
int getHashIndex(int key, int indexNum)
{
	return key % indexNum;
}

哈希链表插入元素

//插入元素
void insertHashCode(MyHashList * hashList, int key, void * data)
{
	if (hashList == NULL)return;

	if (data == NULL)return;
	//创建节点并且初始化节点
	MyHash * code = new MyHash;
	if (code == NULL)return;
	code->data = data;
	code->key = key;
	code->next = NULL;

	//获取哈希索引
	int index = getHashIndex(key, hashList->indexNum);

	//插入:头插法
	MyHash * temp = hashList->myHashArr[index]->next;
	hashList->myHashArr[index]->next = code;
	code->next = temp;

	MyHash * temp2 = hashList->myHashArr[1]->next;
}

哈希链表删除元素

//删除元素
void deleteHashCode(MyHashList * hashList, int key)
{
	if (hashList == NULL)return;

	//获取哈希索引
	int index = getHashIndex(key,hashList->indexNum);

	MyHash * pre = hashList->myHashArr[index];
	MyHash * cur = pre->next;
	while (cur)
	{
		if (cur->key == key)
		{
			pre->next = cur->next;
			delete cur;
			cur = NULL;

			break;
		}
		pre = cur;
		cur = pre->next;
	}
}

哈希链表销毁

//销毁哈希链表
void destoryMyHashList(MyHashList * hashList)
{
	if (hashList == NULL)return;

	for (int i = 0; i < hashList->indexNum; i++)
	{
		MyHash * temp = hashList->myHashArr[i];
		MyHash * temp1 = temp->next;
		while (temp1 != NULL)
		{
			temp->next = temp1->next;
			delete temp1;

			temp1 = temp->next;
		}

		delete hashList->myHashArr[i];
	}
	delete[] hashList->myHashArr;
}

哈希链表查找元素

//查找元素
MyHash * searchHashCode(MyHashList * hashList, int key)
{
	if (hashList == NULL)return NULL;

	//获取哈希索引
	int index = getHashIndex(key, hashList->indexNum);

	MyHash * cur = hashList->myHashArr[index]->next;
	while (cur)
	{
		if (cur->key == key)
		{
			return cur;
			break;
		}
		cur = cur->next;
	}
}

哈希链表实现完整代码(相对常用):

#include<iostream>
using namespace std;

//哈希表实现
struct MyHash
{
	int key;
	void * data;
	MyHash *next;
};

struct MyHashList
{
	//索引数目
	int indexNum;
	//保存索引的队头
	//MyHash *myHashArr[];数组是不可以改变指向,所以不能接受开辟的内存
	MyHash **myHashArr;
};


//改变一级指针保存的值,需要使用二级指针
bool initMyHashList(MyHashList * myHashList, int indexNum)
{
	if (myHashList == NULL)return false;
	myHashList->indexNum = indexNum;

	myHashList->myHashArr = new MyHash*[myHashList->indexNum];
	if (myHashList->myHashArr == NULL)return false;

	for (int i = 0; i < indexNum; i++)
	{
		int temp = i;
		myHashList->myHashArr[i] = new MyHash;

		//分配内存成功,就至0
		if (myHashList->myHashArr[i] != NULL)
		{
			memset(myHashList->myHashArr[i], 0, sizeof(MyHash));
		}
		else
		{
			//分配内存失败,释放之前所有分配的内存
			for (int j = 0; j < temp - 1; j++)
			{
				delete myHashList->myHashArr[j];
			}
			delete myHashList->myHashArr;
			return false;
		}
	}

	return true;
}


//获取哈希索引
int getHashIndex(int key, int indexNum)
{
	return key % indexNum;
}

//插入元素
void insertHashCode(MyHashList * hashList, int key, void * data)
{
	if (hashList == NULL)return;

	if (data == NULL)return;
	//创建节点并且初始化节点
	MyHash * code = new MyHash;
	if (code == NULL)return;
	code->data = data;
	code->key = key;
	code->next = NULL;

	//获取哈希索引
	int index = getHashIndex(key, hashList->indexNum);

	//插入:头插法
	MyHash * temp = hashList->myHashArr[index]->next;
	hashList->myHashArr[index]->next = code;
	code->next = temp;

	MyHash * temp2 = hashList->myHashArr[1]->next;
}

//删除元素
void deleteHashCode(MyHashList * hashList, int key)
{
	if (hashList == NULL)return;

	//获取哈希索引
	int index = getHashIndex(key,hashList->indexNum);

	MyHash * pre = hashList->myHashArr[index];
	MyHash * cur = pre->next;
	while (cur)
	{
		if (cur->key == key)
		{
			pre->next = cur->next;
			delete cur;
			cur = NULL;

			break;
		}
		pre = cur;
		cur = pre->next;
	}
}

//查找元素
MyHash * searchHashCode(MyHashList * hashList, int key)
{
	if (hashList == NULL)return NULL;

	//获取哈希索引
	int index = getHashIndex(key, hashList->indexNum);

	MyHash * cur = hashList->myHashArr[index]->next;
	while (cur)
	{
		if (cur->key == key)
		{
			return cur;
			break;
		}
		cur = cur->next;
	}
}

//遍历元素
void printHashList(MyHashList *hashList)
{
	if (hashList == NULL)return;

	for (int i = 0; i < hashList->indexNum; i++)
	{
		MyHash * temp = hashList->myHashArr[i]->next;
		cout << "key % hashList.indexNum = " << i  << endl;
		while (temp != NULL)
		{
			cout << "key = " << temp->key << "  " << "data = " << *((char*)(temp->data)) << endl;
			temp = temp->next;
		}
		cout << endl;
	}
}

//销毁哈希链表
void destoryMyHashList(MyHashList * hashList)
{
	if (hashList == NULL)return;

	for (int i = 0; i < hashList->indexNum; i++)
	{
		MyHash * temp = hashList->myHashArr[i];
		MyHash * temp1 = temp->next;
		while (temp1 != NULL)
		{
			temp->next = temp1->next;
			delete temp1;

			temp1 = temp->next;
		}

		delete hashList->myHashArr[i];
	}
	delete hashList->myHashArr;
}

int main()
{
	//初始化
	MyHashList * hashList = new MyHashList;
	initMyHashList(hashList, 5);

	char arr[25];
	for (int i = 0; i < 25; i++)
	{
		arr[i] = (i + 'A');
	}
	//插入元素
	for (int i = 0; i < 25; i++)
	{
		insertHashCode(hashList, i + 1, &arr[i]);
	}

	//删除元素
	deleteHashCode(hashList, 10);

	//查找元素
	MyHash * myHashCode = searchHashCode(hashList, 25);
	cout << "key = 25   " << "data = " << *((char*)myHashCode->data) << endl << endl;

	//打印元素
	printHashList(hashList);

	//销毁
	destoryMyHashList(hashList);

	delete hashList;
	hashList = NULL;

	system("pause");
	return 0;
}

哈希数组实现完整代码:

这里使用了三级指针，第一次使用，确实刺激

#include<iostream>
using namespace std;

//哈希表实现
struct MyHash
{
	int key;
	void * data;
};
struct MyHashArr
{
	MyHash ** *hashArr;//这是一个保存*hashArr类型的二维数组
	int *arr;//用于记录每一个桶所保存的元素

	int size;
	int IndexNum;
};

//初始化
void initMyHashArr(MyHashArr * myHashArr, int size, int indexNum)
{
	if (myHashArr == NULL || size < 0 || indexNum < 0)return;
	myHashArr->size = size;
	myHashArr->IndexNum = indexNum;

	myHashArr->hashArr = new MyHash**[indexNum];
	myHashArr->arr = new int[indexNum];
	memset(myHashArr->arr, 0, sizeof(int)*indexNum);

	for (int i = 0; i < indexNum; i++)
	{
		int temp = i;
		myHashArr->hashArr[i] = new MyHash*[size];

		//分配内存成功,就至0
		if (myHashArr->hashArr[i] != NULL)
		{
			memset(myHashArr->hashArr[i], 0, sizeof(MyHash));
		}
		else
		{
			//分配内存失败,释放之前所有分配的内存
			for (int j = 0; j < temp - 1; j++)
			{
				delete myHashArr->hashArr[j];
			}
			delete myHashArr->hashArr;
			delete myHashArr->arr;
			return;
		}
	}
}
//获取哈希索引
int getHashIndex(MyHashArr * myHashArr, int key)
{
	if (myHashArr == NULL || key < 0)return 0;
	return key % myHashArr->IndexNum;
}

//插入元素
void insertHashIndex(MyHashArr * myHashArr, int key, void * data)
{
	if (myHashArr == NULL || key < 0 || data == NULL)return;


	//创建结构体
	MyHash * code = new MyHash;
	if (code == NULL)return;
	code->data = data;
	code->key = key;

	int index = getHashIndex(myHashArr, key);
	//判断索引为index的数组有没有满,如果满了直接退出
	if (myHashArr->size == myHashArr->arr[index])return;

	myHashArr->hashArr[index][myHashArr->arr[index]] = code;
	myHashArr->arr[index]++;
}

//打印哈希
void printHashArr(MyHashArr * myHashArr)
{
	if (myHashArr == NULL)return;

	for (int i = 0; i < myHashArr->IndexNum; i++)
	{
		cout << "------------------" << i  << "--------------------" << endl;
		for (int j = 0; j < myHashArr->arr[i]; j++)
		{
			cout << "key = " << myHashArr->hashArr[i][j]->key << "  data=" << *((char *)(myHashArr->hashArr[i][j]->data)) << endl;
		}
	}
}

//删除元素
void deleteHashCode(MyHashArr * myHashArr, int key)
{
	if (myHashArr == NULL || key < 0)return;
	int index = getHashIndex(myHashArr, key);

	for (int i = 0; i < myHashArr->arr[index]; i++)
	{
		int temp = i;
		if (myHashArr->hashArr[index][i]->key == key)
		{
			for (int j = i + 1; j < myHashArr->arr[index]; j++)
			{
				myHashArr->hashArr[index][j - 1] = myHashArr->hashArr[index][j];
			}
			myHashArr->arr[index]--;
			return;
		}
	}

	return;
}

//搜索元素
MyHash * findHashIndex(MyHashArr * myHashArr, int key)
{
	if (myHashArr == NULL || key < 0)return NULL;
	int index = getHashIndex(myHashArr, key);

	for (int i = 0; i < myHashArr->arr[index]; i++)
	{
		int temp = i;
		if (myHashArr->hashArr[index][i]->key == key)
		{
			return myHashArr->hashArr[index][i];
		}
	}
	return NULL;
}

//销毁哈希
void destoryHashIndex(MyHashArr * myHashArr)
{
	if (myHashArr == NULL)return;


	for (int i = 0; i < myHashArr->IndexNum; i++)
	{
		delete[] myHashArr->hashArr[i];
		myHashArr->hashArr[i] = NULL;
	}
	delete[] myHashArr->arr;
	delete[] myHashArr->hashArr;
	myHashArr->arr = NULL;
	myHashArr->hashArr = NULL;
}

int main()
{
	MyHashArr * myHashArr = new MyHashArr;
	initMyHashArr(myHashArr,5,5);

	char arr[25];
	for (int i = 0; i < 19; i++)
	{
		arr[i] = ('A' + i);
		insertHashIndex(myHashArr, i + 1, &arr[i]);
	}

	//删除元素
	deleteHashCode(myHashArr, 16);

	//查找元素
	MyHash * code = findHashIndex(myHashArr, 7);
	cout << "key = " << code ->key << "  data=" << *((char *)(code->data)) << endl;

	printHashArr(myHashArr);

	//销毁
	destoryHashIndex(myHashArr);
	delete myHashArr;

	system("pause");
	return 0;
}

在这里插入图片描述

本文含有隐藏内容，请开通VIP 后查看

数据结构值哈希表

文章目录

哈希表

哈希表的原理精讲

哈希链表的算法实现

哈希链表实现完整代码(相对常用):

哈希数组实现完整代码:

网站公告

今日签到

热门文章

最新发布