8--哈希表Hash的相关操作

哈希表（Hash table）是一种数据结构，用于实现键值对的存储和查找。其中直接地址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法都可以作为哈希表的散列函数。

直接地址法是唯一一个不会产生冲突的方法，因为它是线性的，每一个数都有对应的地址，所有就不会产生冲突，但是空间利用率低，它是典型的用空间换时间。而除留余数法是最常用的一种方法。

哈希表的查找、插入和删除操作的时间复杂度通常为O(1)，但在极端情况下，可能会出现冲突（多个键映射到同一个索引位置），这时需要解决冲突的方法，比如开地址法、链地址法、再散列法（双散列函数法）、建立一个公共溢出区。

开地址法中又包含了线性探测法（常用）、二次探测法、伪随机探测法。

线性探测法：下一个下一个

二次探测法：左一个右一个（一直循环直到找到空位置）

伪随机探测法：生成随机数，随机存储。每次都得从头遍历，不建议使用

此处我们就用除留余数法和开地址法中的线性探测法来实现哈希表，代码如下：

#include<stdio.h>

#define NONE -1 //将哈希表内初始成-1
#define p 13 //p一般取小于等于m且为质数
#define m 16 //哈希表的长度

//定义Hash结构体
typedef struct Hash
{
	int key;//关键字项;
	//InfoType otherinfo;//其他数据项
}Hash, HashTable[m]; //定义了一个长度为m的Hash数组

//初始化哈希表
void InitHashTable(HashTable  ht)
{
	for (int i = 0; i < m; i++)
	{
		ht[i].key = NONE;
	}
}

//将关键字映射到哈希表的索引位置
//得到key对p取模的结果
static int H(int key)
{
	return key % p;
}

//将key插入到哈希表ht中,成功返回true,失败返回false;
bool Insert(HashTable ht, int key)
{
	int hi = H(key);//得到key的哈希值;

	//当前哈希表没有被使用,将key直接存储;
	if (ht[hi].key == NONE)
	{
		ht[hi].key = key;
		return true;
	}
	
	else//在其他地方找合适的位置,使用线性探测法;
	{
		int i = (hi + 1) % m;//新的位置
		while (i != hi)
		{
			if (ht[i].key == NONE)
			{
				ht[i].key = key;
				return true;
			}
			i = (i + 1) % m;//更新i的位置，即向后移动一个位置
		}
		return false;
	}
}

//在哈希表中查找key,找到返回下标,失败返回-1
int Search(HashTable ht, int key)
{
	int hi = H(key);
	int i = hi;
	while (ht[i].key != NONE)
	{
		if (ht[i].key == key)
		{
			return i;
		}
		i = (i + 1) % m;

		if (i == hi)
		{
			break;
		}
	}
	return -1;
}

//从头到尾输出哈希表中的所有的值
void Show(HashTable ht)
{
	for (int i = 0; i < m; i++)
	{
		printf("%d ", ht[i].key);
	}
	printf("\n");
}

int main()
{
	HashTable ht;//ht指向哈希表
	InitHashTable(ht);//初始化哈希表
	int arr[16] = { 3,5,7,1,2,9,28,25,6,11,10,15,17,23,34,19 };

	//测试插入后得到的哈希表
	for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++)
	{
		Insert(ht, arr[i]);
	}
	Show(ht);//输出哈希表

	//测试查找
	int key = 2;
	int index = Search(ht, key);
	if (index != -1)
	{
		printf("关键字%d找到了！\n",key);
	}
	else
	{
		printf("关键字%d没有找到！\n",key);
	}

	return 0;
}