哈希查找(按个位取余的方式)

步骤：

1.构建哈希表进行分类

2.进行哈希查找(算法)

处理冲突：

按个位取余发现有两个或多个数重复，如：

会发现15，25，55，重叠了，对此进行冲突处理，冲突处理有三种：

1.地址偏移法

以上图为例，将和25按个位取余后重复的数填到25后面的位置，如果相邻的位置满了，在向后填。

2.再哈希法 

再次使用哈希法，直至填充完毕。

3.拉链法

以上图为例，像拉链一样将重叠数据以拉链形式挂在下面，示例代码

#include <iostream>
using namespace std;

struct Hash
{
	int nVal;
	int nIndex;//在原数组的元素下标
	Hash* pNext;
};

//每个元素是一个Hash*,所以这个函数的返回值是Hash**
Hash** CreateHashTable(int nLen, int arr[])
{
	if (arr == nullptr||nLen<=0)
	{
		return nullptr;
	}

	//创建哈希表的数组，一个表内有10个数字的大小
	Hash** pHash = new Hash*[10];
	//每一个元素都是个指针，所以要对其赋空
	memset(pHash, 0, sizeof(Hash*) * 10);
	//遍历数组，对每一个元素归位
	for (int i = 0; i < nLen; i++)
	{
		//创建元素的下标key
		int key = arr[i] % 10;
		//先创建节点pTemp
		Hash* pTemp = new Hash;
		pTemp->nVal = arr[i];
		pTemp->nIndex = i;
		pTemp->pNext = nullptr;
		//头部添加，类似于入栈
		pTemp->pNext = pHash[key];
		//将pHash指针指向新建的节点
		pHash[key] = pTemp;
	}
	return pHash;
}
int HashSearch(Hash** pHash, int nVal)
{
	if (pHash == nullptr || *pHash == nullptr)
		return -1;

	//创建元素的下标key，用来找位置
	int key= nVal % 10;

	Hash* pMark = pHash[key];
	//遍历链表
	while (pMark!=nullptr)
	{
		if (pMark->nVal ==nVal)
		{
			return pMark->nIndex;
		}
		pMark = pMark->pNext;
	}
}
int main()
{
	int arr[] = {10,23,45,67,99,69,46};
	Hash** pHash = CreateHashTable(7,arr);
	cout << HashSearch(pHash, 23) << endl;
	return 0;
}