哈希表(散列表)C/C++代码实现

哈希表(散列表)：

一，构造散列函数

最常用的方法是除留余数法：

H(key) = key%p

这个方法的关键是选取适当的p, 一般情况下，可以选p为小于表长的最大质数。例如表长m=100, 可取p=97。

二，处理冲突

选择一个 “好” 的散列函数可以在一定程度上减少冲突，但在实际应用中，很难完全避免发生冲突

1，开放地址法

（1）线性勘测法

（2）二次探测法

（3）伪随机探测法

线性探测法的优点是：只要散列表未填满，总能 找到一个不发生冲突的地址。缺点是：会产生 ”二次聚集“ 现象。而二次探测法和伪随机探测法 的优点是：可以避免 “二次聚集“ 现象。缺点也很显然：不能保证一定找到不发生冲突的地址。

2，链地址法

把具有相同散列地址的记录链在同一个单链表中，称为同义词链表。

哈希表(散列表)的查找：

代码以该图为例：

代码如下：

#include<stdio.h>
#include<stdlib.h>

#define m 16	//  哈希表/散列表长度
typedef int KeyType;
typedef int InfoType;
//散列表定义
typedef struct
{
	KeyType key;
	InfoType otherinfo;
}HashTable[m];

//散列表的查找
int SearchHash(HashTable HT, KeyType key)
{
	int HO = key % 13;  //根据散列函数计算散列地址
	if (HT[HO].key == 0)  return -1;		// 若单元为空， 则所查元素不存在
	else if (HT[HO].key == key) return HO;
	else
	{
		//按照线性探测法计算下一个散列地址Hi
		for (int i = 1; i < m; i++)
		{
			int Hi = (HO + i) % m;
			if (HT[Hi].key == 0)  return -1;		// 若单元为空， 则所查元素不存在
			else if (HT[Hi].key == key) return Hi;
		}
		return -1;
	}
}

//散列表的插入
int InsertHash(HashTable HT, KeyType key)
{
	int HO = key % 13;		//根据散列函数计算散列地址
	if (HT[HO].key == 0)	// 若单元为空， 则所查元素不存在
	{
		HT[HO].key = key;
		return 0;
	}
	else
	{
		//按照线性探测法计算下一个散列地址Hi
		for (int i = 1; i < m; i++)
		{
			int Hi = (HO + i) % m;
			if (HT[Hi].key == 0) 	// 若单元为空， 则所查元素不存在
			{
				HT[Hi].key = key;
				return 0;
			}
		}
		return -1;					//散列表已满
	}
}


int main()
{
	//初始化
	HashTable HT;
	for (int i = 0; i < m; i++)
	{
		HT[i].key = 0;
	}

	//插入
	InsertHash(HT, 19);
	InsertHash(HT, 14);
	InsertHash(HT, 23);
	InsertHash(HT, 1);
	InsertHash(HT, 68);
	InsertHash(HT, 20);
	InsertHash(HT, 84);
	InsertHash(HT, 27);
	InsertHash(HT, 55);
	InsertHash(HT, 11);
	InsertHash(HT, 10);
	InsertHash(HT, 79);

	//遍历散列表
	printf("按散列地址排列：");
	for (int i = 1; i <m; i++)
	{
		printf("%d,", HT[i].key);
	}

	//查找
	int n;
	printf("\n请输入要查找的数：");
	scanf("%d", &n);
	int result = SearchHash(HT, n);
	printf("\n要查找的数在散列表中的地址为：%d  \n", result);
}


           

运行结果：